Google's search algorithm / page rank

Introduction

구글 검색 시, 엄청난 수의 정보 속에서 어떤 알고리즘으로 자료의 우선 순위를 매겨 사용자에게 보여주는지 궁금하여 알아보다가 좋은 포스트를 발견하여 나름대로 정리해보았다.

 

PageRank

구글이 검색 엔진에서 정보의 우선 순위를 할당하는 방식이다. 결과부터 말하면, 페이지의 우선도는 해당 페이지를 링크하고 있는 페이지들의 우선도 값으로 결정된다. 사람을 평가하기 위해, 잘 어울려다니는 친구들을 평가하는 느낌이다.

 

세르게이 브린과 래리 페이지는 웹 안에서 인덱싱을 통한 기존의 검색 방식이 문제가 있고, 텍스트 그 자체를 통한 검색이 아닌, 하이퍼텍스트를 이용하여 링크 구조와 링크 텍스트를 이용하면 보다 유용한 정보를 제공할 수 있다고 생각하였다. 이 구조를 이용하면 페이지 마다의 영향력을 확인 할 수 있고, 보다 높은 영향력을 갖는 페이지를 우선 출력하는 것이다.

 

PageRank 식

d는 damping factor으로, 사용자가 다른 링크로 이동하지 않고 해당 페이지에 남아있을 확률이고, C(t)는 t 페이지가 갖고 있는 전체 링크 개수, Tx는 page를 링크하고 있는 다른 페이지들이다. 예를 들면, d=0일 경우 해당 페이지의 pageRank는 1/n이 되고, 마찬가지로 모든 링크되어 있는 페이지 n 개의 pageRank 값도 1/n이므로 이를 모두 더하면 1, 즉 사용자가 정착하지 않고 이동만 한다면, 한 페이지의 페이지 랭크는 1/n 된다. 

 

페이지에서 이동하는 확률 (1-d)의 사건은 1/n이고, 해당 페이지에 남아있는 사건은 페이지를 링크하고 있는 페이지의 페이지 랭크를 링크 개수로 나눈 값들의 합으로 한다. 예를 들면 페이지 랭크가 같은 두 페이지에서, A 페이지는 딱 하나의 페이지만 링크하고, B 페이지는 10000개의 페이지를 링크한다고 치자. 당연히 A 페이지의 하나 링크된 페이지가 그만큼 신뢰를 얻는 것처럼, 링크한 페이지 랭크 각각에 그 페이지의 총 링크 갯수를 나눠 더하는 것이다.  

 

참고

정보는 아래 조성문님의 블로그와 이명헌 경영스쿨, 위키피디아 PageRank을 통해 공부하였다.

 

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

‘쉽게 설명한’ 구글의 페이지 랭크 알고리즘

https://en.wikipedia.org/wiki/PageRank

PageRank - Wikipedia

http://www.emh.co.kr/content.pl?google_pagerank_citation_ranking

이명헌 경영스쿨: [텍스트마이닝] 구글 페이지랭크(PageRank) 알고리듬