Chapter11. Link Analysis: PageRank

투빅스 12기 배유나

Web as a Graph

web graph look like:

web

-> directed graph로 표현된다.

-> strongly connected components 그래프 이론 사용

-> computational experiment : in- out components of given node v

-> structure of the web : BOWTIE

web as a graph:

Nodes = web pages
Edges = hyperlinks

초기 웹 링크는 방향을 알려주는 역할(navigational)이었다.

오늘날 많은 링크는 교류하는 역할(transactional)이다.

Web as a directed graph

노드 v가 주어졌을 때 들어오는 링크는 incoming link, 나가는 링크는 outcoming link로 정의된다.

Directed Graph

Strongly connected:

어떤 노드도 다른 노드에 도달할 수 있는 path가 존재

In(A)=Out(A)={A,B,C,D,E}

2. Directed Acyclic Graph(DAG):

사이클이 없는 그래프, 노드 u는 v에 도달해도 노드 v는 u에 도달하지 않음

Strongly Connected Component (SCC)

- 집합 S에서 노드들의 모든 쌍이 서로 도달할 수 있다.

- SCC이면서 집합 S를 포함하는 더 큰 집합은 존재하지 않는다.

예제: {A, B, C}는 첫번째 조건을 만족하나, {A, B, C, G}가 존재하므로 두번째 조건은 만족하지 못한다. (not SCC)

" Fact: Every directed graph is a DAG on its SCCs "

모든 directed graph 는 SCC들의 DAG이다.

즉, 모든 쌍들이 서로 도달할 수 있는 작은 그래프들이 모인 것이라고 볼 수 있다.

SCC는 그래프 G의 노드들을 분할한다.(partition) → 각 SCC를 노드로 본다.
SCC를 노드로 보는 그래프 G`이 있을 때, G`은 DAG 이다.

Graph Structure of the Web

웹의 큰 스냅샷을 살펴보면, 어떻게 SCC들이 DAG로 서로 맞춰있는지 이해할 수 있다.

Computational Issues:

SCC가 노드 v를 포함하는 것을 어떻게 발견?

In(v): 노드 v로 들어오는 노드들의 집합
Out(v): 노드 v로부터 도달가능한 노드들의 집합
SCC 에 노드 v가 포함되면, Out(v)와 In(v)의 교집합에 노드 v가 있다.
위 방법은 연산이 많이 걸리므로 Out(v,G)와 Out(v, 방향을 뒤집은 G)의 교집합으로 노드 v를 찾는다.

따라서, 웹은 매우 큰 SCC 이다.

Structure of the Web

초기 웹은 데이터베이스에 링크나 url을 저장해둔 형태로 서버는 12GB의 메모리를 가졌었다.

Directed version of the Web graph

랜덤 노드 v 에서 In(v), Out(v) 계산. 결과

가장 큰 SCC: 노드들 중 28%가 해당된다. (56 million)
랜덤으로 노드 v를 가져오는 것은 Out(v) ~ 50% (100 million), In(v) ~ 50% (100 million) 이 되게 한다.

How to Organize the web PageRank (aka the Google Algorithm)

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

- 검색 엔진의 2가지 난제

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

Ranking Nodes on the Graph

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

-> So, let’s rank the pages using the web graph link structure!

Link Analysis Algorithms

그래프에서 노드의 중요도(importances or score)를 계산하기 위한 접근법

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

" Links as Votes "

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

Page-Rank : The "Flow" Model

A “vote” from an important page is worth more:

각 링크의 투표(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)이 된다.

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

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

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

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이다.

페이지 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이다.
그러나 이 방법은 느리기 때문에 보다 효율적으로 벡터 r을 구해야 한다.
- 그 방법을 Power Iteration이라고 한다.

Power Iteration Method

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

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

N = 웹 페이지 개수

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

Power iteration은 가장 큰 eigenvalue에 대응하는 벡터인, dominant 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?)

문제점

1.Dead end: 어떤 페이지들은 out-links를 갖지 않아, random walk는 갈 곳이 없다.

r 벡터는 모두 0이 되는 현상
이런 페이지들은 중요도를 누출시킨다. (leak out)

2.Spider trap: random walk가 트랩에 빠지는 현상

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

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

- 해결책: Teleports

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

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

- 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 이다.

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-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌)