PageRank 알고리즘 이해하기

간단한 예를 통해 page rank 알고리즘을 이해해보기로 한다.

위와 같은 A,B,C,D 라는 인터넷 페이지가 있고,

각각의 페이지마다 서로를 향한 링크를 갖고 있다고 하자.

예를 들어 A 사이트에서는 B와 C로 가는 링크가 있고

C 사이트에서는 A,B,D 로 가는 링크가 있다.

page rank 알고리즘에서 rank 값을 계산하는 함수를 pr 라고 하자.

초기 pr 값은 1/(전체 페이지 개수) 로 정한다.

즉 

pr(A) = 1/4

pr(B) = 1/4

pr(C) = 1/4

pr(D) = 1/4

가 된다.

page의 rank를 갱신하는 방법은 이렇다.

< A 페이지의 rank 값을 갱신 > 

pr(A) 를 갱신해보자.

pr(A) = (1-DF)/(페이지 전체 개수) + DF * ((A로 향하는 페이지의 현재 pr 값 / A로 향하는 페이지의 out link 개수) 들의 합)

pr(A) = ( 1-DF ) / 4 + DF * ( pr(C) / 3 )

pr(A) = ( 1-0.85 ) / 4 + 0.85 * ( (1/4) / 3)

페이지는 모두 4 이므로 페이지의 전체 개수로써 사용되는 분모는 4이다.

A로 향하는 페이지는 C 하나 뿐이다.

C의 현재 pr 값은 초기에 정해두었던 1/4 이므로 pr(C) = 1/4 이다.

C 에서 뻗어나가는 링크가 총 3개(A,B,D 로 뻗음)이므로 마지막 분모는 3이 된다.

DF 가 뭔지 궁금할 것 같은데

DF는 Damping Factor의 약자이며 설명은 아래와 같다.

damping factor란 "어떤 마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률" 이다.  즉, damping factor가 1이면, 무한히 링크를 클릭한다는 뜻이고, 0이면 처음 방문한 페이지에서 무조건 멈추고 더 이상 클릭하지 않는다는 뜻이다.  0.85이면, 85%의 확률로 다른 페이지를 클릭해볼 것이라는 뜻이다. 이 경우 15%의 확률에 걸리는 순간 클릭을 멈추고 그 페이지를 살펴본다.

따라서 pr(A) 를 계산해보면 0.108333333가 된다.

pr(A) = 0.108333333

이 갱신 값은 다른 페이지들의 rank 값이 갱신될 때 한꺼번에 갱신된다.

< B 페이지의 rank 값을 갱신 > 

pr(B) 를 갱신해보자.

방법은 A를 갱신했을 때와 같다.

pr(B) = (1-DF)/(페이지 전체 개수) + DF * ((B로 향하는 페이지의 현재 pr 값 / B로 향하는 페이지의 out link 개수) 들의 합)

pr(B) = ( 1-DF ) / 4 + DF * ( pr(A) / 2 + pr(C) / 3 )

pr(B) = ( 1-0.85 ) / 4 + 0.85 * ( (1/4) / 2 + (1/4) / 3)

B로 향하는 링크를 갖는 페이지는 A와 C 두 개이다.

A의 pr(A) 값은 초기값인 1/4 이다(위에서 갱신값을 구하긴 했지만 실제 갱신은 한꺼번에 이루어지므로 초기값이 사용됨)

A에서 뻗어나가는 링크의 개수가 2개(B,C로) 이므로 (1/4)/2 가 된다.

C의 pr(C) 값은 초기값인 1/4이다.

C에서 뻗어나가는 링크의 개수가 3개(A,B,D로) 이므로 (1/4)/3 이 된다.

위에서 구한 (1/4)/2 와 (1/4)/3을 모두 더한 값을 식에 적용하면 된다.

계산하면 pr(B)의 rank 값은 0.214583333 가 된다.

pr(B) = 0.214583333

< C 페이지의 rank 값을 갱신 >  

pr(C) 를 갱신해보자.

방법은 위와 같다.

pr(C) = (1-DF)/(페이지 전체 개수) + DF * ((C로 향하는 페이지의 현재 pr 값 / C로 향하는 페이지의 out link 개수) 들의 합)

pr(C) = ( 1-DF ) / 4 + DF * ( pr(A) / 2 + pr(D) / 1 )

pr(C) = ( 1-0.85 ) / 4 + 0.85 * ( (1/4) / 2 + (1/4) / 1)

C로 향하는 링크를 갖는 페이지는 A와 D 두 개이다.

A의 pr(A) 값은 초기값인 1/4 이다.

A에서 뻗어나가는 링크의 개수가 2개(B,C로) 이므로 (1/4)/2 가 된다.

D의 pr(D) 값은 초기값인 1/4이다.

D에서 뻗어나가는 링크의 개수가 1개(C로) 이므로 (1/4)/1 이 된다.

위에서 구한 (1/4)/2 와 (1/4)/1을 모두 더한 값을 식에 적용하면 된다.

계산하면 pr(C)의 rank 값은 0.35625 가 된다.

pr(C) = 0.35625

< D 페이지의 rank 값을 갱신 >  

pr(D) 를 갱신해보자.

방법은 위와 같다.

pr(D) = (1-DF)/(페이지 전체 개수) + DF * ((D로 향하는 페이지의 현재 pr 값 / D로 향하는 페이지의 out link 개수) 들의 합)

pr(D) = ( 1-DF ) / 4 + DF * ( pr(B) / 1 + pr(C) / 3 )

pr(D) = ( 1-0.85 ) / 4 + 0.85 * ( (1/4) / 1 + (1/4) / 3)

D로 향하는 링크를 갖는 페이지는 B와 C 두 개이다.

B의 pr(B) 값은 초기값인 1/4 이다.

B에서 뻗어나가는 링크의 개수가 1개(D로) 이므로 (1/4)/1 가 된다.

C의 pr(C) 값은 초기값인 1/4이다.

C에서 뻗어나가는 링크의 개수가 3개(A,B,D로) 이므로 (1/4)/3 이 된다.

위에서 구한 (1/4)/1 과 (1/4)/3을 모두 더한 값을 식에 적용하면 된다.

계산하면 pr(D)의 rank 값은 0.320833333 가 된다.

pr(D) = 0.320833333

이렇게 한 번 pr 값을 갱신하였다.

위에서는 초기값인 계산할 때 1/4를 계속 사용하였는데,

두번째로 rank를 갱신할 때는,

같은 계산식 안에, 위에서 새롭게 만든 rank 값들을 대신 사용한다.

즉, A의 rank 값을 두 번째로 갱신 할 때는 아래와 같은 식이 된다는 말이다.

pr(A) = ( 1-0.85 ) / 4 + 0.85 * ( 0.35625 / 3)

(C의 초기값인 1/4 대신, 새롭게 갱신된 rank 값인 0.35625 가 들어갔다.)

pr(A) = 0.108333333

pr(B) = 0.214583333

pr(C) = 0.35625

pr(D) = 0.320833333

rank 값이 높을수록 중요한 페이지가 된다.

여기선 C - D - B - A 순으로 rank 값이 높으므로 이 순서로 중요한 페이지가 된다.

즉 C가 가장 중요하고 A가 가장 덜 중요한 페이지가 된다.

참고한 곳 : 

https://sungmooncho.com/2012/08/26/pagerank/

https://www.youtube.com/watch?v=P8Kt6Abq_rM

http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

matrix 연산을 통해 페이지랭크 구현 참고 링크들

https://www.slideshare.net/ChenGengMa/a-hadoop-implementation-of-pagerank

https://www.cs.utah.edu/~jeffp/teaching/cs5140-S15/cs5140/L24-MR+PR.pdf

https://github.com/zonagit/MapReduceAndHadoop

https://www.youtube.com/watch?v=3_1h13PJkUs

http://www.dcs.bbk.ac.uk/~dell/teaching/cc/book/mmds/mmds_ch5_2.pdf

https://stanford.edu/~rezab/amdm/notes/lecture4.pdf

https://github.com/guillaume6pl/mr_pagerank