[Social Network] PageRank

PageRank

Link-based object ranking(LBR)의 방법 중 하나이다.

Object = 1종류, link = 1종류

 

페이지에 대한 중요도를 결정하는데,

여러 페이지가 가리키는 페이지를 중요하게 생각하고 페이지를 순서화한다.

다만 간접적으로 가리킴을 받는 것도 고려하였으며, smoothing of citation을 통해 cycle이나 self-citation 등의 문제를 해결하였다.

 

Page의 중요도

• in-link가 많은 페이지가 important하다.
• important한 페이지로부터의 in-link가 많은 페이지는 더 important하다.

 

---

알고리즘

1. 모든 페이지에 대해 같은 score를 부여한다.
2. 각 페이지 별로
   1. out-link를 따라 fair하게 나눠서 score를 넘겨준다.
   2. in-link로 들어오는 score를 합쳐서 페이지의 score를 업데이트한다.

 

문제

그러나 이런 방식으로 수행하게 되면 dangling node와 cyclic citation으로 인해 문제가 발생한다.

• dangling node : iteration이 지날수록 점수가 한 페이지로 몰린다.
• cyclic citation : iteration이 지나도 계속해서 반복되는 현상이 발생한다.

 

해결

이를 해결하기 위해 random surfer의 동작 방식을 도입한다.

웹 페이지를 자유롭게 이동하는 이용자를 random surfer라고 한다.

 

Random walk의 방식으로 인해 dangling node의 문제를 해결할 수 있고, restart의 방식을 통해 cyclic citation 문제를 해결할 수 있다.

• random walk : $\alpha$의 확률로 현재 페이지의 out-link 중 하나를 선택해서 이동한다.
• restart : $1-\alpha$의 확률로 전체 페이지 중 하나를 선택해서 이동한다.

 

결론

1. Initial : $r_0 = 1/N$ 
2. $r_i$가 수렴하거나 $r_i - r_{i-1} < \epsilon$이 될 때 까지 아래 과정을 반복한다.

* $M$ = Transition matrix

* $d$ = dangling node인지 아닌지

* $w$ = 공평하게 나눈 점수

 

예시