[paper review] The PageRank Citation Ranking: Bringing Order to the Web

date

Dec 30, 2023

slug

The-PageRank-Citation-Ranking

author

status

Public

Introduction

그래프 기반의 랭킹 알고리즘은 자료구조의 한 종류인 그래프를 기반으로 합니다.

이 알고리즘은 vertex(정점)의 local한 정보만을 반영하지 않고, 전체 그래프의 global information을 재귀적으로 반영하여 vertex(정점)의 중요도를 결정하는 방법론 입니다.

(vetex == Node 입니다. 본 논문의 표현을 그대로 빌리겠습니다.)

그래프 기반의 랭킹 모델은 쉽게 설명하면 voting혹은 recommendation과 같습니다.

그래프의 vertex가 다른 vertex와 연결되어 있다면, 이는 서로에게 voting했음을 의미합니다. 더 많은 연결은 갖는 vertex는 많은 voting을 받은 것으로 간주할 수 있습니다.

또한 voting자체의 중요도는 voting을 행사하는 vertex의 중요도에 의해 결정됩니다.

따라서 vertex의 중요도는 "얼마나 중요한 vertex들로 부터 voting을 받았는가"로 부터 판단이 가능합니다.

그리고 이러한 중요도는 vertex의 랭킹을 결정할 수 있는 요소가 됩니다.

구글의 PageRank 알고리즘<그림1>은 대표적인 그래프 기반의 랭킹 알고리즘 입니다.

PageRank는 directed graph 로 부터 아래의 식을 통해 vertex(의 중요도를 계산합니다.

는 vertex 로 향하는 이웃 vertex의 집합을 의미하며,

는 vertex 가 가르키는 이웃 vertex의 집합을 의미합니다.

따라서 기본적으로 vertex 의 중요도는 에 속하는 vertex의 중요도를 더하는 방법으로 구한다고 생각할 수 있습니다.

은 의 Edge가 많을수록 그 중요도를 감소시켜 반영해주기 위한 term 입니다. <그림 2>를 통해 잘 확인할 수 있습니다.

마지막으로, 는 damping factor를 의미합니다.

PageRank는 기본적으로 웹 페이지의 중요도를 고려하기 위해 만들어진 모델입니다. 따라서 edge는 웹 페이지 내의 링크를 통한 인접한 웹 페이지로의 이동을 의미합니다.

damping factor 는 바로 이런 이동 확률을 모델링해 줍니다.

추가적으로 웹 서핑을 할 때에는 기존에 고려하지 않은 새로운 페이지로의 이동 확률 또한 존재합니다.

수식의 는 이러한 "random surfing" 확률을 모델링 한 것 입니다.

는 확률값으로 0~1의 값을 가질 수 있는데, PageRank에서는 0.85를 damping factor로 사용하였습니다.

PageRank의 학습은 임의의 Vertex 중요도값에서 시작하여 기준치를 달성할 때 까지 재귀적으로 진행됩니다.

iteration 에서의 Error 는 다음과 같이 매우 단순합니다.

이 때 중요한 것은 그래프의 수렴이 중요도의 초기값에는 영향을 받지 않고, 오로지 반복 횟수에만 영향을 받게 됩니다.

directed/undirected, weighted/unweighted를 모두 고려한 다음 4가지 모델의 결과가 이러한 사실을 잘 보여주고 있습니다.