간단한 예를 통해 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

+ Recent posts