링크 분석(Link Analysis), 페이지 랭크(PageRank)

r4v3n-k 2019. 12. 23. 11:53

2019. 12. 23. 11:53

개요

- 그래프 데이터를 처리하는 알고리즘: PageRank, SimRank, 커뮤니티 탐지, 스팸 탐지

- Web as a directed graph

Nodes = Webpages
Edges = Hyperlinks

- 웹을 체계화(organize)하는 방법

First try: 인간이 직접 분류하는 것(Human curated)
- Web directories: Yahoo, DMOZ, Looksmart
Second try: 웹 검색 엔진(Web search)
- Information Retrieval investigates: 작고 신뢰있는 집합에서 관련 문헌을 어떻게 잘 찾아내는지 연구하는 학문
  - Newspaper articles, Patents, etc.

- 실제 웹은 너무 거대하며, 신뢰되지 않는 문서들이 매우 많다. 스팸도 그러하다.

- 검색 엔진의 2가지 난제

웹은 많은 정보를 포함한다. 신뢰(trust)에 대한 정보를 어떻게 알 수 있나?
- 신뢰있는 페이지들은 서로서로 참조할 것이다.
(키워드)“newspaper”를 질의할 때 최고의 대답(검색결과)는 무엇인가?
- newspaper에 대해 실제로 아는 페이지들은 많은 newspaper들을 참조하고 있을 것이다.

- 그래프에서 노드(웹 페이지)를 등급 매기는 방법

모든 웹 페이지는 동등하게 중요하지 않다.
웹 그래프 노드 연결성에 대해 많은 다양성이 있다.
링크 구조에 따라 페이지들에 등급을 매길 수 있다.

- 링크 분석 알고리즘(Link Analysis Algorithms): 그래프에서 노드의 중요도(importances or score)를 계산하기 위한 접근법

Page-Rank
Topic-Specific (Personalized) Page-Rank
Web Spam Detection Algorithms

PageRank: The “Flow” Formulation

- 투표로 보는 링크(Links as Votes)

페이지는 많은 링크를 가질수록 중요해진다.
- In-coming links: 노드로 들어오는 링크
- Out-going links: 노드에서 나가는 링크
in-links를 (다른 페이지로부터 받는) 투표로 보기
- 예를 들어, 스탠포드 대학 사이트는 23,400 의 in-links를 가진다.
- in-links가 많은 노드로부터 in-links를 받는 노드는 중요도가 더 높은 링크를 갖는다.
  - 인기있는 웹페이지로부터 참조를 받으면 다른 링크보다 중요도가 더 높아진다.
재귀적으로 in-links의 근원지(source)를 찾아 링크마다 scoring
- 아래 노드들의 점수는 다른 노드에서 들어오는 score와 나가는 score가 동일할 때의 값이다. (a.k.a 동적 평형)

- 단순 재귀 공식화(Simple Recursive Formulation)

각 링크의 투표(vote)는 들어오는 페이지의 중요도에 비례한다. (중요도만큼 투표를 받은 것으로 간주)
중요도 rj를 가지는 페이지 j가 n개의 out-links를 가진다면, 각 out-links는 rj/n 만큼의 중요도를 다른 노드에게 준다.
페이지 j의 중요도는 모든 in-links의 값들의 합이다.
즉, 노드는 자신의 score에서 out-links의 개수만큼 나눈 값을 다른 노드로 전달한다.

노드 k에 out-links의 개수는 4이기 때문에, 노드 k의 각 out-links의 값은 노드 k의 중요도 / 4 이다.

노드 i에서 out-links의 개수는 3이기 때문에, 노드 i의 각 out-links의 값은 노드 i의 중요도 / 3 이다.

노드 j에서 in-links는 노드 i와 k에서 오는 것만 있으므로, 중요도는 (노드 k의 중요도 / 4) + (노드 i의 중요도 / 3)이 된다.

PageRank: The “Flow” Model

- 중요한 페이지에서 투표값(score or vote)은 더욱 가치가 있다. 한 페이지는 다른 중요한 페이지들로부터 참조되면 더욱 중요해진다.

- 페이지 j에 대한 rank rj 의 정의

di 는 노드 i의 out-degree (나가는 링크의 개수)이다.
노드 i에서 노드 j로 나가는 링크가 존재한다고 가정

- Flow 수식 풀기

3개의 수식, 3개의 미지수, 상수는 없을 때, 유일해는 없다.
모든 해는 scale factor를 나머지 연산한 것과 동일하다.
추가적인 제약이 유일해를 이끌어낸다.

- 가우시안 소거법은 작은 예제에서는 잘 동작하지만, 매우 큰 웹 그래프에 대해서는 더 나은 방법이 필요하다.

PageRank: Matrix Formulation

- 확률론적 인접 행렬(Stochastic adjacency matrix)

페이지 i가 di 값의 out-links 를 가질 때, 페이지 i에서 j로 링크가 있다면 인접행렬 M의 원소 Mij=1/di가 되며, 링크가 없다면 해당 원소는 0이 된다.
행렬 M은 column stochastic matrix 로 열 벡터의 합은 1이다.

- Rank Vector r: 원소가 페이지당 rank 에 해당되는 벡터

ri 는 페이지 i의 중요도 점수이다.
벡터의 원소의 합은 1이다.

- Flow 수식은 아래와 같다.

페이지 i의 score 를 페이지 i에서 j로 이동한 out-going link 의 개수로 나누면 노드 j의 score를 구할 수 있다.

- Eigenvector Formulation: rank vector r은 학률론적 웹 행렬(stochastic web matrix) M 의 eigenvector 이다.

행렬 M은 모두 양수인 원소를 갖는 column stochastic이기 때문에 가장 큰 eigenvalue는 1이다.

벡터 r의 길이는 1이며, 행렬 M의 각 컬럼의 합도 1이다. M*r <= 1
그러나 이 방법은 느리기 때문에 보다 효율적으로 벡터 r을 구해야 한다.
- 그 방법을 Power Iteration이라고 한다.

Power Iteration Method

- n개의 노드를 갖는 웹 그래프가 주어질 때, 노드들은 페이지를 의미하고 간선은 하이퍼링크를 의미한다.

- Power iteration: 단순 반복 계획(a simple iterative scheme)

N = 웹 페이지 개수

초기화 단계에서 N으로 나누는 것은 모든 페이지들이 평등하단 의미이다.

- 각 노드에 들어오는 score를 연립방정식으로 세우는 것이 중요하다.

- Power iteration은 가장 큰 eigenvalue에 대응하는 벡터인, dominant eigenvector를 찾는 방법

Thus 부분이 중요하다. 결국 M^k*r(0) 는 상수*(첫번째 eigenvalue의 k승 * 첫번째 eigenvector)에 가까워진다.

Random Walk Interpretation

- 랜덤 웹 서퍼(random web surfer)

t 시점에, 어떤 페이지 i를 서핑한다.
t+1 시점에, 서퍼는 랜덤으로 균일하게 페이지 i로부터 out-link를 따라간다.
페이지 i로부터 연결된 페이지 j에서 끝이 난다.
무한하게 위의 과정을 반복한다.

- p(t) = 서퍼가 t 시점에 페이지 i에 있음을 증명하는 i번째 좌표를 가진 벡터

- p(t)는 페이지에 대한 확률 분포이다.

- 고정 분포(The Stationary Distribution)

t+1 시점에 서퍼가 어디 있는가?
- 랜덤으로 균일하게 link를 따른다.
- p(t+1) = M*p(t)

p(t+1) = M*p(t) = p(t) 일 때, p(t)는 random walk의 고정 분포이다. 즉, 어떤 상태(state)에 도달한 것이다.
원래 rank vector r은 r=M*r을 만족한다. 따라서 r은 random walk에 대한 고정 분포이다.

- 존재와 유일함(Existence and Uniqueness)

random walk 이론으로부터 주요 결과는 Markov processes로 알려졌는데, 어떤 조건을 만족시키는 그래프에 대해서 고정 분포는 유일하고 초기 확률 분포가 어떻든지 마침내 어떤 상태에 도달할 것이다.
즉, 무한 루프가 아니다.

PageRank: The Google Formulation

- 3가지 질문

언제 끝나는가? (Does this converge?)
우리가 원할 때 끝나는가? (Does it converge to what we want?)
결과는 합리적인가? (Are results reasonable?)

- 문제점

Dead end: 어떤 페이지들은 out-links를 갖지 않아, random walk는 갈 곳이 없다.
- r 벡터는 모두 0이 되는 현상
- 이런 페이지들은 중요도를 누출시킨다. (leak out)

Spider trap: random walk가 트랩에 빠지는 현상
- 모든 out-links가 그룹 내 에 있어서 외부 링크 벡터가 0이 되는 현상
- 결국 모든 중요도를 없애버린다.

[모든 노드는 m에 도달가능하나, 역은 성립하지 않는다. 즉, m의 중요도만 남고 나머지는 0]

노드 m에 도달하면 계속 m에 대한 링크만 타고 가게 된다. (trapped)

- 해결책: Teleports

구글은 spider trap에 대한 해결책을 제시했다. 각 시점의 스텝마다, 랜덤 서퍼는 2가지 옵션을 갖는 것이다.
- 𝜷 를 가지고 랜덤으로 링크를 따라간다.
- 1-𝜷 를 가지고 랜덤 페이지로 점프한다.
- 𝜷 에 대한 일반적인 값은 0.8 ~ 0.9이다.
서퍼는 몇몇 시점에 스텝 시 spider trap에 걸리면 텔레포트(teleport)할 것이다.

dead-end에서 확률 1을 가지고 랜덤으로 링크를 teleport 한다.
- 이 때 노드의 개수만큼 확률을 나눠갖기 때문에 1이 분산된다.

m이 모두 0이어서 dead-end 상태였으나, random teleport 때문에 m에 ⅓ 씩 값을 갖게 된다.

- Teleport가 문제를 해결하는 이유

Spider-traps 은 문제는 아니지만, 트랩이 있는 PageRank의 score는 원하던 것이 아니다. 유한한 숫자만큼 이동(steps)하면 spider trap 으로부터 teleport 할 수 있다.
Dead-ends 는 문제가 맞다. 행렬은 column stochastic 이 아니어서, 초기 추측값이 다를 수 있다. 항상 갈 곳이 달리 없을 때 teleport해주어서 행렬의 column stochastic을 만들 수 있다.

- Random Teleport: 구글의 해결책

각 단계에서 랜덤 서퍼가 가지는 두 가지 옵션
- 𝜷 를 가지고 랜덤으로 링크를 따라간다.
- 1-𝜷 를 가지고 랜덤 페이지로 점프한다.

- Google Matrix

NxN 행렬은 모든 원소가 1/N 이다.
재귀적인 문제: r = A*r
Power method 가 여전히 잘 동작한다.
𝜷 에 대한 정의
- 실제로 0.8, 0.9 이다.

[ Google Matrix를 활용한 Random Teleports 모델 ]

PageRank 계산하는 방법

- matrix-vector multiplication

- 충분한 메모리를 가진다면 쉬우나, 실제로 행렬 A와 벡터 r은 매우 크다.

N = 1 billion pages
각 원소마다 4바이트가 필요하고, r 벡터가 2 billion 개의 원소를 가진다면 대략 벡터 r 이 2개이므로 8 GB 가 필요하다.
행렬 A 는 N*N 개의 원소를 갖게된다.

- Matrix Formulation: N개의 페이지들이 있을 때, out-links 를 di 개 가지고 있는 페이지 i가 있다면 다음과 같은 공식이 성립한다.

- random teleport

페이지 i에서 모든 다른 페이지까지 teleport link를 추가하고 이동 확률(transition probability)을 (1-𝜷)/N 으로 설정한다.
각 out-link 를 1/|di| 에서 𝜷/|di| 로 확률을 줄인다.
- 전체에서 𝜷를 곱한 게 전체가 되었으므로 그만큼 값이 분산된다.
각 페이지의 점수에 (1-𝜷) 를 곱하고 다시 분배한다.
- 모든 웹페이지의 Rank Score 에서 (1-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌)
- 결국 전체 score는 이전 score의 (1-𝜷) 가 된다.

여기서 행렬 M은 dead-ends가 없다고 가정한다. 벡터 r의 모든 원소의 합은 1이다.

- Sparse Matrix Formulation

행렬 M은 sparse matrix이지만 dead-ends가 없다.
- 각 노드에 10개의 link가 있으면 M의 원소의 개수는 10N 으로 근사한다.
매 반복마다 새로운 벡터 r을 계산해야 하고, 상수값을 새 벡터 r 에 더해주어야 한다.
- 이 방법으로 인해 계산이 빨라진다.

- Sparse Matrix Encoding: 0이 아닌 원소만 사용하는 것

link의 개수가 대략 공간에 비례한다.
10N 개의 원소가 있으면 4*10*1 billion = 40 GB 를 차지
여전히 메모리에는 올리기 힘들며, 오히려 디스크에 맞출 수 있는 크기이다.

위의 행렬 구조를 사용하는 것이다. 첫번째 행은 0번 노드에서는 1번,5번,7번 노드로 가는 out-link만 가지고 있는 걸 의미한다.

- 큰 행렬을 이용하여 계산하는 방법 (Basic Algorithm: Update Step)

새로운 벡터 r을 메모리로 맞추기 위해 충분한 RAM이 있다고 가정하자.
- 오래된 벡터 r과 행렬 M은 디스크에 있다.

위의 중간 행렬이 M인데 여기서 계산이 되는 행과 오래된 벡터 r의 계산이 될 원소만 메모리로 가져와서 연산이 끝나면 다시 한 줄씩 가져오는 것이다. 행렬이 디스크 공간 상에 순차적으로 저장이 되었기 때문에 디스크 연산이 근처 영역만 읽기(linear scan) 때문에 입출력 시간이 비교적 적다. 메모리에는 새로운 벡터 r만 있는데 random access 가 가능하므로 입출력 시간이 비교적 적다.
새로운 벡터 r의 각 원소에는 행렬 M의 첫번째 행에 따라 오래된 벡터의 0번 원소의 score를 ⅓ 씩 나눠준 것이다.

비용이 디스크에 새로운 벡터 r과 오래된 벡터 r을 써야해서 2|r|이 되고 행렬 M은 모든 원소를 한번씩 읽어야 하므로 |M|이 된다.
여기서 비용은 디스크 입출력 연산만 포함한다.
만약 메모리에 올려야 하는 새로운 벡터 r이 너무 크다면, 위의 방법을 사용하기 어렵다.

- 블록 기반의 갱신 알고리즘 (Block-based Update Algorithm)

새로운 벡터 r을 블록 단위로 쪼개서 메모리에 올린다. 그리고 각 블록마다 한 번씩 M과 오래된 벡터 r을 스캔한다.

행렬 M과 오래된 벡터 r을 스캔하는 비용이 커진다. k는 스캔하는 횟수=블록 개수

- 블록 스트라이프 갱신 알고리즘(Block-Stripe Update Algorithm)

행렬 M을 stripe 단위로 나누어서 저장하는데, 연산 시, 필요한 원소만 읽고 쓸 수 있다.

엡실론은 매우 작은 숫자이다. 1+엡실론 < k 라고 가정한다.
벡터 r에 대해 (k+1)번 입출력 연산이 되는 이유는 마지막 1이 새로운 벡터 r을 저장하는데 드는 비용이기 때문이다.

PageRank 에 여전히 존재하는 문제점

- 페이지의 일반적인 인기도 측정

이전까지는 link의 개수에만 영향을 받았다.
그러나 페이지가 담고 있는 내용도 신경 쓸 필요가 있다.
- Topic-Specific PageRank

- 중요도의 단순한 척도를 사용

측정 항목을 늘릴 필요가 있다.
- Hubs-and-Authorities

- 링크 스팸(Link spam)을 허용

의도적으로 page rank 를 올리는 수단(linking 문제)을 방지해야 한다.
- TrustRank

매우 큰 그래프의 분석: TrustRank 와 WebSpam

Topic-Specific PageRank

- 범용적인 인기도 대신에, 주제와 관련된 인기 척도를 사용

- 웹 페이지들이 특정 주제(e.g. “sports” or “history”)와 얼마나 가까운지에 따라 인기도를 계산하는 법

- 검색 요청(search queries)에 대해 사용자의 흥미를 기반으로 응답해줄 필요가 있다.

“Trojan” 이라는 단어를 검색했을 때, 국가 이름인지 사람 이름인지 알 필요가 있다.

- 랜덤 워커(Random walker)는 어떤 단계에서는 teleport를 할 작을 확률을 가진다.

Standard PageRank
- 어떤 페이지든지 동일한 확률을 가진다.
- dead-end와 spider-trap 문제를 피할 수 있다.
Topic Specific PageRank
- 주제 구체적인, 관련 페이지들의 집합 = teleport set

- 기본 아이디어: random walk 마다 bias를 주기

워커가 텔레포트를 할 때, 집합 S로부터 페이지를 선택한다.
집합 S는 해당 주제와 관련된 페이지들만 포함한다.
집합 S로 매 텔레포트가 발생하면, 매 순간 다른 벡터 r을 얻는다.

- Matrix Formulation

잘 동작하게 하려면, PageRank 수식의 teleportation 부분을 갱신해줄 필요가 있다.

A is stochastic! —> 위의 조건은 도착지 노드가 s에 포함되는 경우

teleport set S에 있는 모든 페이지에 동등하게 가중치를 매긴다.
- 페이지에 다른 가중치를 할당할 수도 있다.
표준 PageRank에 대해서 연산
- M으로 곱하고 벡터에 더한다.
- sparseness를 유지한다.

위에 1번 노드로 들어오는 링크의 값은 tax로, 항상 1로 teleport 하므로 추가되는 값이다.

- Topic Vector S

다른 주제에 대한 다른 PageRank를 생성
어떤 주제 랭킹을 사용할 것인가?
- Context: 사용자가 검색한 키워드의 목록 (history of queries)
- 키워드 중 중의적인 의미가 있으면 이전 쿼리를 조회해서 의도를 알아내는 것이 목적
- 사용자는 메뉴로부터 선택할 수 있다.
  - 검색 요청을 주제로 분류한다.
  - 검색 요청의 context를 사용할 수 있다.
  - User Context → 사용자의 북마크 등

그래프에서 근사 측정(measuring proximity)을 응용하기

- 예시: Relevance, Closeness, Similarity

- 좋은 근사 측정 방법

최단 거리는 1개의 out-link만 있는 경우에는 그닥 좋지 않고, 네트워크 흐름도 긴 경로가 있는 경우 감점시키는 것이 없어서 그닥 좋지 않음
다수의 연결
연결의 품질
- Direct & Indirect connections
- Length, Degree, Weight, ...

- SimRank

k-partite 그래프에서 고정된 노드로부터 random walks
설정 사항: k-partite 그래프는 노드의 종류가 k개이다.
- Authors, Conferences, Tags

노드 u로부터 Topic Specific PageRank → teleport set S = {u}
노드 u에서 유사도를 측정해서 score를 낸다.
문제점
- 각 노드 u에 대해 한 번씩 수행되어야 한다.
- 하위 웹 규모의 응용프로그램에 적당하다.

PageRank 요약

- “Normal” PageRank

균일하게 랜덤으로 어떤 노드에 텔레포트 한다.
모든 노드들은 자신에게 도착하는 서퍼의 확률을 동일하게 갖는다.
- S = [0.1, 0.1, 0.1, 0.1, 0.1, 0.1]

- Topic-Specific PageRank (a.k.a. Personalized PageRank)

주제 특화된 집합의 페이지에만 텔레포트 한다.
노드들은 자신에게 도착하는 서퍼의 확률을 달리 갖는다.
- S = [0.1, 0, 0, 0.2, 0, 0, 0.5, 0, 0, 0.2]

- Random Walk with Restarts

같은 노드로 항상 텔레포트하는 Topic-Specific PageRank
그러나, 항상 같은 노드에서 출발하면 비효율적이다.
- S = [0,0,0,0,1,0,0,0,0]

TrustRank: Web spam과의 싸움

- Spamming

검색 엔진 결과에서 페이지의 실제 값과는 어울리지 않게 웹의 페이지 위치를 상승시키기 위한 어떤 교묘한 동작(deliberate action)
in-links 개수 < out-links 개수

- Spam: spamming의 결과가 되는 웹 페이지

- SEO = Search Engine Optimization

- 전체 웹 페이지의 대략 10-15% 는 스팸이다. 많을수록 웹 랭킹이 흐트러진다.

- Web Search

초기 검색 엔진은 웹을 크롤링해놓고 포함된 단어들에 따라 페이지를 인덱싱하였다. 따라서 검색 요청에 따라 해당 키워드를 포함하는 페이지들로 응답하였다.
초기 페이지 랭킹은 중요도에 따라 다른 페이지들이 검색 요청과 매칭되는지 확인하였다.
첫번째 검색 엔진은 (1) 요청 단어의 수 (2) 단어의 위치 e.g. titile, header 만으로 고려되어졌다.

- First Spammers

사람들이 웹에서 무언가를 찾기 위해 검색 엔진을 사용하면서, 상업적인 관심이 사람들을 자신의 사이트로 데려오기 위해 검색 엔진을 악용하는 것에 있었다.
- 특정 사이트의 랭킹을 올리려는 사람들에 의해
- 예제: 영화에 대한 것으로 구실을 삼으나, 셔츠 판매원인 경우
웹 페이지에 대한 관련성/중요도를 높게 이루는 기술이 필요
- 예제: 영화에 대해서 페이지가 어떻게 나타나는가? (스팸 만드는 과정)
  - 페이지에 단어 “movie”를 1000번 추가한 후, 텍스트 색상을 배경색으로 맞추어서 검색 시 사이트가 보이게 하는 방법
  - 대상 검색 엔진에 “move”라는 검색을 수행하면, 처음에 목록에 뜨는 페이지들 중 내용을 복사해서 자신의 페이지에 붙인 뒤 보이지 않는 옵션을 주는 방법
- 이와 유사한 방법을 term spam 이라고 한다.

- term spam 에 대한 구글의 해결책

사이트 주인이 기재한 내용보다 외부로부터의 언급 내용을 참조
- 링크를 표현하는 밑줄 그은 텍스트(anchor text)에서의 단어를 사용한다. 또는 링크 주변의 텍스트를 이용한다.
웹 페이지의 중요도를 측정하기 위한 도구로서의 PageRank
- 중요도는 in-coming link만 고려한다.
해결책이 잘 동작하는 이유 → 예시: 가짜 셔츠 판매자
- 다른 것들이 영화에 대해 이야기하지 않기 때문에, 셔츠 판매자가 페이지에서 영화에 대해 이야기 하는 것이 도움이 되지 않는다.
- 셔츠 판매자의 페이지는 매우 중요하지 않아서, 셔츠나 영화에 대해 높게 등급이 매겨지지 않을 것이다.
- 셔츠 판매자는 1000개의 페이지를 만들고, 각 link는 auchor text에서 “movie” 단어를 가지고 페이지를 참조한다. 이러한 페이지들은 내부에 들어오는 link는 없어서 작은 PageRank를 얻는다. 따라서 셔츠 판매자는 정말로 중요한 영화 페이지 (IMDB같이)를 이길 수 없다.
해결책이 잘 동작하지 않는 이유 → Spam Farming
- 구글이 검색 엔진으로 승승장구하면서, spammer들은 구글을 속이는 방법을 연구하기 시작했다
- Spam farms: 특정 사이트의 PageRank를 올리는 툴
- Link spam: 링크를 올리는 스팸, 특정 페이지의 PageRank를 올리는 링크 구조를 만드는 방법
- spammer의 관점에서는 3가지의 웹 페이지가 존재한다.
  - Inaccessible pages
  - Owned pages → spammer에 의해 완전히 통제되는 자기 페이지
  - Accessible pages → blog comments pages (기사글 댓글에 링크걸기)
- spammer의 목표: 대상 페이지 t의 PageRank를 최대화하는 것
- spammer가 사용한 기술
  - 대상 페이지 t에 가능한 accessible pages로부터 많은 link를 얻는다.
  - PageRank 상승 효과를 얻기 위해 link farm을 구성한다.

𝜷y/M 은 link farm의 빨간 점들에 t가 보낸 link score
(1-𝜷)/N 은 random teleport 로 인한 (1-𝜷) 를 전체 페이지 개수인 N으로 나눈 값

획득한 PageRank에 대한 상승 효과(Multiplier effect) → M(=link farm의 페이지 개수)이 클수록, 대상 페이지 t의 Rank는 원하는 만큼 더 커질 수 있다.

TrustRank

- Combating term spam

통계적 방법을 이용한 텍스트 분석
이메일 스팸 필터링과 유사한 방법 사용
거의 똑같고, 중복되는 페이지들을 탐지하는데 유용한 방법 사용

- Combating link spam

spam farm처럼 보이는 구조를 탐지해서 블랙 리스트에 담는 방법
- 또 다른 전쟁을 이끈다. → spam farm들과 숨바꼭질..
TrustRank = 신뢰되는 페이지들의 teleport set을 가진 topic-specific PageRank
- .edu domains, similar domains for non-US schools

- 주 원리: Approximate isolation

나쁜 페이지를 참조하는 좋은 페이지가 없다는 가정
웹으로부터 seed pages의 집합을 샘플링
seed set에서 좋은 페이지들과 스팸 페이지들을 식별하는 사람(oracle)이 있음
- 단, 비싼 업무라서 가능한 작은 seed set을 만들어야만 한다.

- Trust Propagation

식별되는 seed pages의 부분집합을 좋고 신뢰되는 페이지라고 부름
teleport set = trusted pages 인 topic-sensitive PageRank를 수행
- 링크를 통해서 trust를 전파 → 신뢰되는 페이지들끼리 전파하는 것
- 각 페이지는 trust value과 0또는 1의 값을 갖는다. 여기서 0이면 스팸
해결책
- 임계값을 사용해서, 신뢰도 임계값 이하의 스팸이 되는 모든 페이지들을 표시
알고리즘
- 각각의 신뢰되는 페이지의 신뢰도를 1로 설정
- 페이지 p의 신뢰도를 t_p로 가정할 때, 페이지 p는 out-links의 집합 o_p를 가진다면, o_p에 속하는 각각의 q는 페이지 p의 out-links 중 하나이다.
  - 페이지 p의 out link 로 나가는 신뢰도 =

신뢰도는 추가된다.
- 페이지 p의 신뢰도는 p로 들어오는 링크를 갖는 페이지들의 trust의 합이다.
Topic-Specific PageRank 에서의 유사도
- scaling factor 안에, teleport set으로 신뢰되는 페이지들을 갖는 PageRank 는 TrustRank 이다.

- 장점

신뢰도 감쇠(Trust attenuation): 신뢰되는 페이지들에 의해 모여진 신뢰도는 그래프에서 거리를 감소시킨다.
신뢰도 분할(Trust splitting): 페이지의 out-links 수가 많을수록 페이지 작성자가 각 out-link 별로 정밀도를 떨어뜨린다. 즉, 신뢰도가 out-link를 통해 분할된다.

- Seed Set 선택

두 가지 고려 사항이 충돌한다.
- 사람이 각 seed page를 관찰해야 하므로, seed set은 가능한 작아야만 한다.
- 모든 good page는 적절한 trust rank를 얻도록 보장해야 하므로, 모든 good page가 seed set으로부터 최단 경로에 의해 도달해야 한다.
- 즉, 그래프 크기에 비해 seed set이 너무 작으면 trust를 많이 받지 못한다.
접근법
- PageRank: 상위 k개의 페이지를 선택해서, seed set에 넣는다. 이론적으로 bad page의 rank는 실제로 높은 값을 가질 수 없다.
- Use trusted domains: 신뢰되는 도메인들을 추려서 seed set에 추가하여 크기를 확장한다. 예를 들어, .edu, .mil, .gov 같은 도메인들을 통제할 수 있는 소속력(membership)을 갖는다.
- k 개의 페이지들의 seed set을 선택하는 방법

- Spam Mass

TrustRank 모델에서, 좋은 페이지를 가지고 시작하고 신뢰도를 전파한다.
상호 보완적인 관점에서, 높은 PageRank를 갖는 사이트 중 스팸에서 얻은 스코어가 많은 사이트도 있다.
- 페이지의 PageRank는 얼마만큼 스팸 페이지로부터 받는가?
실제로, 스팸 페이지들을 알지 못하므로 측정할 필요가 있다.
측정방법
- 스팸 페이지에서 얻은 PageRank = 전체 PageRank - 신뢰되는 페이지에서 얻은 PageRank
- Spam mass = 스팸 페이지에서 얻은 PageRank / 전체 PageRank

HITS: Hubs and Authorities

- HITS (Hypertext-Induced Topic Selection)

PageRank와 유사한 문서나 페이지의 중요도를 측정하기 위한 항목
PageRank 와 동일한 시점에 제안되었다.

- 목표

좋은 newspapers를 찾는 것
단순히 찾기 보다는 전문가들을 먼저 찾는다.
여기서 전문가란 조정된 방법 내에서 좋은 newspapers로 링크를 하는 사람 또는 페이지를 의미한다.

- 기본적인 아이디어가 Links as votes 이다. 페이지는 더 많은 링크를 가질수록 중요하다.

In-coming links
Out-going links

- Hubs and Authorities: 각 페이지는 2가지 score를 가진다.

Quality as an expert (hubs): authorities가 참조했던 link의 합
Quality as a content (authority): expert로부터 받은 vote의 합
거듭된 개선의 원칙
- 아래 예시에서 파란 점은 hub이고 초록색은 authority이다.
- authority 값이 클수록 hub들이 좋은 것이며 역도 성립한다.

- 흥미로운 페이지들은 두 가지 클래스로 분류된다.

Authorities: 유용한 정보를 포함하는 페이지들
- Newspaper home pages
- Course home pages
- Home pages of auto manufacturers
Hubs: authorities에 링크를 하는 페이지들
- List of newspapers
- Course bulletin
- List of US auto manufacturers