Introduction

검색 엔진에서 무언가를 검색해 본 적 있는가? 그렇다면 하나의 검색어에 수많은 문서들이 대응된다는 것도 알 것이다. 어떤 문서를 가장 위에 보여줘야 할까? 그 순위를 정하는 알고리즘이 바로 '페이지랭크 알고리즘' 이다. 가끔씩 인터넷에서 문서를 보다 보면 다른 문서로 가는 링크를 가진 경우가 있다. 후술할 페이지랭크 알고리즘은 이 링크 들을 이용해 페이지들의 우선순위를 결정한다.

Very Simple Method

먼저 간단하게 시작해 보자. \(n\)은 페이지의 총 수로, \(v_i\)는 페이지 \(i\)의 선호도로, 그리고 \(a_{ij}\)는 페이지 \(j\)가 \(i\)를 링크하면 1, 그렇지 않으면 0의 값을 가지는 값으로 정의하자. 다른 페이지들이 자신을 링크하면 좋다는 것은 쉽게 알 수 있다. 따라서 어느 페이지 \(i\)의 선호도는 \(i\)를 링크하는 다른 페이지들의 수라고 할 수 있다.

\[v_i=\sum_{j=1}^{n}a_{ij}\]

Simple Method

하지만 위 방법은 자신을 링크하는 페이지가 얼마나 많은 페이지들을 링크하는지는 알지 못한다. 페이지 \(j\)가 \(i\)를 링크하고 \(j\)에서 다른 페이지로 가는 링크의 개수가 \(d_j\)라 하면 사용자들이 \(j\)에서 \(i\)로 갈 확률은 \(d_j\)에 반비례한다. 자신이 페이지 \(j\)를 보고 있다고 생각해보자. 그 페이지가 \(d_j\)만큼 다른 페이지를 링크하고 있다면 각각의 페이지로 들어갈 확률은 \(\frac{1}{d_j}\)일 것이다.

\[v_i=\sum_{j=1}^{n}\frac{a_{ij}}{d_j}\]

Improved Method

하지만 각각의 링크는 영향력이 다르다. 일반인의 페이지가 자신의 페이지를 링크한 것과 유명인의 페이지가 자신의 페이지를 링크한 것을 비교해보자. 이 둘은 똑같은 링크 하나지만, 유명인의 링크가 선호도에 더욱 큰 영향을 미칠 것이다. 그러면 페이지 \(j\)가 페이지 \(i\)를 링크한다면 그 영향은 \(v_j\)에 비례할 것이다.

\[v_i=\sum_{j=1}^{n}\frac{a_{ij}v_j}{d_j}\]

\(P_{ij}\)를 \(\frac{a_{ij}}{d_j}\)로 정의하면 \(P\)는 \(n\times n\) 크기의 행렬이 될 것이다. 위 식을 더욱 간단하게 표현하면,

\[v=Pv\]

How to Compute?

행렬 \(P\)를 알 때 위 식을 풀어 해를 얻기 위해서는 Random Surfer Model을 사용해야 한다. Random Surfer Model은 어느 페이지에 있는 Random Surfer가 다른 페이지로 링크를 타고 들어갈 가능성을 계산한 것을 바탕으로 선호도 벡터 \(v\)를 계산하는 방법이다.

물론 우리가 실제로 Random Surfer을 구현해서 몬테 카를로 방법으로 선호도를 계산하지는 않을 것이다. Random Surfer은 단지 알고리즘이 어떻게 작동하는지를 알려주는 장치일 뿐이다. 초기 선호도를 전부 \(\frac{1}{n}\)으로 하고, 이를 \(n\times 1\) 크기의 행렬 \(w\)라 하자. 그리고 Random Surfer가 항상 링크만 따라가는 것은 아니다. 링크를 따라갈 확률을 \(r(0< r< 1)\)이라 하면 아무 페이지나 랜덤으로 갈 확률은 \(1-r\)이다. \(T\)를 모든 원소가 \(\frac{1}{n}\)인 \(n\times n\) 크기의 행렬이라 정의하면 최종적으로 페이지 \(j\)에 있는 Random Surfer가 페이지 \(i\)로 갈 확률은 \(r\times P_{ij} + (1-r)\times T_{ij}\)이다. 최종적으로 페이지 \(j\)에서 페이지 \(i\)로 갈 확률을 \(Q_{ij}\)라 하면

\[Q = rP + (1-r)T\]

그러면 충분히 큰 수 \(k\)를 잡고 선호도 벡터 \(v\)가 항상 수렴한다고 가정하면

\[v=Q^{k}w\]

행렬 곱셈을 앞에서부터 하고 분할 정복을 사용하면 \(O(n^{2.38}\log{k})\), 뒤에서부터 차례대로 하면 \(O(n^{2}k)\)이다. 보통 \(n\)에 비해 \(k\)는 매우 작기 때문에 대부분 후자의 알고리즘이 더욱 효율적이다. 링크의 개수를 \(e\)라고 하면 모든 링크에 대해 선호도를 한 번씩만 갱신하는 작업을 \(k\)번 반복함으로써 \(v\)를 구할 수 있다. 그러면 시간복잡도는 \(O((n+e)k)\)으로, 페이지가 수십조개에 이르고 링크 수가 별로 많지 않은 구글같은 검색엔진에서 사용하기 적합하다.

Does it converge?

진짜로 적당히 큰 수 \(k\)를 잡으면 \(v\)가 수렴할까? \(v^k=Q^{k}w\)라고 가정하자.

그러면 \(v^{k}=QQ^{k-1}w=Qv^{k-1}\) 이기 때문에

\[v^{k}_{i}=r(\sum\limits_{j}\frac{a_{ij}v^{k-1}_j}{d_j}) + \frac{1-r}{n}\]

그리고 \(v=Qv\) 이기 때문에

\[v_{i}=r(\sum\limits_{j}\frac{a_{ij}v_j}{d_j}) + \frac{1-r}{n}\]

\(Error(k)=\sum\limits_{i}\vert v^k_i-v_i\vert\) 라고 가정하자.

\[\vert v^k_i-v_i\vert = \vert r(\sum\limits_{j}\frac{a_{ij}(v^{k-1}_j-v_j)}{d_j})\vert \le r(\sum\limits_{j}\frac{a_{ij}\vert (v^{k-1}_j-v_j)\vert}{d_j})\]

최종적으로,

\[Error(k)=\sum\limits_{i}\vert v^k_i-v_i\vert \le \sum\limits_{i}r\sum\limits_{j}\frac{a_{ij}\vert (v^{k-1}_j-v_j)\vert}{d_j}\\ = \sum\limits_{j}r\sum\limits_{i}\frac{a_{ij}\vert (v^{k-1}_j-v_j)\vert}{d_j} = r\sum\limits_{j}\vert (v^{k-1}_j-v_j)\vert = rError(k-1) \]

\(r<1\)이기 때문에 충분히 큰 \(k\)에 대해서 \(Error(k)\)는 0으로 수렴한다.

Conclusion

오늘은 우리가 체감하지는 못하지만 매일 사용하는 알고리즘인 PageRank Algorithm에 대하여 간단하게나마 알아보았다. 이 알고리즘은 단순한 인터넷 검색을 넘어서, 유튜브, 인스타그램, 등 대부분의 SNS나 웹사이트에 사용된다. 정말 신기하지 않은가?