Pagerank(페이지랭크)

Mining of Massive Datasets의 Link analysis 챕터에서 배운 내용

Pagerank는 웹페이지의 중요도를 구하기 위한 기법으로 어떤  page의 pagerank값은 그 page가 얼마나 중요한 page인지를 나타낸다)

* Web page의 개수를 N개로 가정

1. 행과 열의 개수가 모두 N인 행렬을 만든다.

2. 만약 page j가 page i로 가는 링크를 갖고 있다면  행렬 M(i,j)는 1/c 값을 갖는다. (c는 page j의 outlink 개수)

 이러한 행렬 M은 한 열의 값을 모두 합친 값이 1이 되므로 'column stochastic matrix'라고 부른다.

3. 이제 pagerank를 저장할 벡터 r을 만든다. 모든 page는 각각의 pagerank값을 가지므로 r은 길이가 N인 벡터이다.

위 이미지는 웹페이지의 개수가 4개일 때의 행렬 M의 예시다. 0은 link가 없는 것을 뜻하며 0이 아닌 값을 가진 페이지는 위에서 말했듯이 열값페이지->행값페이지로 가는 링크가 있음을 뜻한다.

또한 앞서 말했듯이 이 행렬은 열값의 합이 1인 column stochastic matrix이다.

위 행렬 M의 web graph를 그려보면 다음과 같이 나온다.

이제 pagerank를 구해 볼 차례다.

우리가 pagerank를 구하는 방법은 'Power Iteration method'라고도 불리는 방법으로 반복적으로 행렬과 벡터를 곱해 수렴하는 값을 찾아내는 방법이다.

이 방법은 Web 분야뿐만이 아니라 graph로 표현할 수 있는 분야에서는 node의 중요도를 구하는 방법으로 유용하게 쓰이는 방법이니 알아두면 정말 좋다.

Power Iteration method

1. 벡터 r을 균등하게 초기화한다 

r = [1/N, ... , 1/N]^T (N개의 webpage가 있으므로 각 값은 1/N이며 이 벡터가 컬럼의 형태가 되도록 transpose)

2. 다음 과정을 반복한다.

* r_k = k번째 iteration의 r

r_(k+1) = M*r_k

즉, r = Mr을 반복하는 것이다.

여기서 곱셈은 행렬곱(matrix multiplication)이다.

3. 이 과정은 | r_(k+1) - r_k | <  을 만족할 때까지 반복한다 (수렴할 때까지)

(은 Hyperparameter로 그때그때 문제에 맞게 적당히 작은 값을 정해준다)

여기서 하나 알아야 할 것은 수렴된 r은 M의 eigenvector(고유벡터)라는 점이다.

이 이미지는 아까 전에 예시로 보여준 웹그래의 행렬 M을 이용해 pagerank 벡터 r을 구하는 과정을 나타낸 것이다.

[1/4, 1/4, 1/4, 1/4]^T 로 초기화된 이후 행렬 M과 반복적으로 행렬곱셈을 하여 수렴값에 점점 다가가게 된다.

( 대부분의 경우 수십~수백회의 iteration 만으로도 수렴이 된다. )

그런데 r 벡터가 항상 같은 값으로 수렴할까? 

즉, 이 행렬의 principal eigenvector가 존재할까?

이와 같이 r벡터가 유일하다는 것을 보장하기 위해서는 다음과 같은 조건을 만족해야 한다.

1. Dead end가 없어야 한다.

 Dead end는 외부로 가는 link가 없는 node를 뜻한다. 즉 그래프에서 모든 노드는 어떤 노드로 향하는 링크를 가져야 한다는 뜻이다.

2. Spider trap이 없어야 한다.

 Dead end와 유사하지만 다른 개념이다. Spider trap은 어떤 노드들의 그룹에서 그룹 외부의 노드로 가는 링크를 갖고 있지 않은 것을 뜻한다.

즉 모든 노드가 dead end가 아니더라도 어떤 그룹 내에서 순환하기만 할 경우를 뜻한다.

이 두 가지 조건을 만족하는 경우에만 pagerank값을 정상적으로 구할 수 있다.

하지만 실제 웹에서는 이상한 페이지들이 참 많다. 

이 문제를 해결하기 위해서는 'Random Teleport' 테크닉을 사용한다.

기회가 된다면 이에 대해서도 다뤄보겠다.

Notions & Images from Mining of Massive Datasets