검색엔진의 역사를 바꾼 pagerank 알고리즘 파헤치기

1. 그래프로 표현하는 웹

 

웹은 웹페이지와 하이퍼링크로 포함된 거대한 방향성 그래프다

 

웹페이지를 node, 하이퍼링크를 다음 웹페이지를 향하는 link로 볼 수 있다.

 

물론 웹페이지는 하이퍼링크와 무관한 keyword정보를 포함한다

 

 

웹페이지의 하이퍼링크를 클릭하여 링크가 가리키는 다음 웹페이지로 이동할 수 있다

 

 

2. pagerank는 왜 등장했을까

 

2-1) 거대한 디렉토리

 

수십억에서 수백억개가 있을 것이라고 추측하는 웹페이지에서 원하는 정보를 어떻게 찾을 수 있을까?

 

먼저 전 세계에 존재하는 모든 웹을 카테고리로 구분하여 하나의 디렉토리로 저장했다.

 

https://photohistory.tistory.com/2323

 

97년도의 네이버 모습으로 카테고리로 웹을 저장했다는 것이 보인다

 

시간이 흐르면서 카테고리 수와 깊이는 무한정 증가할 것이고 심지어 카테고리 구분은 모호해지므로 관리하기가 어렵다.

 

 

2-2) keyword 검색엔진

 

사용자가 입력한 keyword를 여러번 포함하는 웹페이지를 반환

 

그러나 성인 사이트에 ‘롤’이라는 단어를 보이지 않도록 해서 여러번 포함시키면 ‘롤’을 검색했을 때

 

성인 사이트를 반환할 수도 있다는 약점이 있다

 

사용자가 검색한 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 어떻게 찾을까?

 

구글의 창업자 Larry Page, Sergey Brin은 "The PageRank Citation Ranking: Bringing Order to the Web"에서 웹페이지의 상대적 중요성을 측정하기 위해 PageRank를 제안했다.

 

 

3. PageRank

 

3-1) motivation

 

Generally, highly linked pages are more “important" than pages with few links.

 

하이퍼링크를 많이 받은 페이지는 하이퍼링크를 덜 받은 페이지보다 중요하다.

 

 

3-2) rank system

 

웹페이지가 하이퍼링크를 통해 다른 웹페이지로 ‘투표’를 하여

 

‘투표’를 많이 받은 웹페이지를 사용자 키워드와 관련성이 높고 신뢰성이 높은 웹페이지라고 생각한다.

 

사용자 키워드를 포함하는 두 웹페이지 u,v를 생각하자.

 

u가 v로의 하이퍼링크를 포함한다면 u의 작성자가 생각하기에 v가 관련성이 높다고 생각해서 링크를 달아둔 것일 가능성이 높다.

 

논문을 예로 생각하면 사람들은 인용을 많이 한 논문을 더욱 신뢰한다.

 

그래프의 관점에서 생각하면 incoming link가 많을수록 해당 웹페이지는 신뢰성이 높다는 것이다.

 

 

3-3) the problem of simple counting system

 

there are many cases where simple citation counting does not correspond to our common sense notion of importance.

 

단순히 link(citation,인용)를 세는 것은 우리가 생각하는 중요성과 맞지 않을 때가 많다

 

돈 주고 팔로워를 사는 경우

 

전혀 쓸모없는 웹페이지를 여러개 만들어서 link를 부풀릴수 있다. 그래서 관련성과 신뢰도를 조작할 수 있다는 것.

 

반대로 link가 별로 없지만 굉장히 중요한 웹페이지는 얼마든지 존재할 수 있다.

 

link가 많지만 완벽하게 대칭성을 보여 인위적이라고 생각되는 웹그래프

 

 

3-4) solution of simple counting

 

그래서 관련성과 신뢰성이 높은 웹페이지의 투표를 더욱 중시하는 가중투표방식을 생각했다.

 

반대로 그렇지 않은 웹페이지의 투표는 가중치를 낮춰 덜 중요하게 간주했다.

 

악용이 전혀 없더라도 관련성이 높은 웹페이지에 더 높은 점수를 부여하는 투표 시스템은 합리적이다.

 

 

3-5) pagerank value computation

 

각 웹페이지는 outcoming neighbor에 (자신의 페이지랭크 점수/outcoming degree) 가중치로 투표를 한다.

 

 

 

$i$의 경우 페이지랭크 점수가 $r_{i}$라고 가정하면 웹페이지 $i$는 자신의 나가는 이웃들에게 $\frac{r_{i}}{3}$로 투표한다.

 

그래서 $j$ 웹사이트에 $\frac{r_{i}}{3}$로 투표했다.

 

각 웹페이지 j의 페이지랭크 점수는 j가 받은 모든 가중치 투표의 총합이다.

 

 

 

 

j로 들어오는 neighbor인 모든 i에 대하여 i의 페이지랭크 점수를 i의 나가는 연결성으로 나눈다.

 

j로 들어온다는 것이 확실하기 때문에 $d_{OUT}(i)$는 0이 아니다.

 

 

3-6) example of pagerank value

 

 

 

a가 받은 가중치 투표는 위에서 $r_{m}$과 $\frac{r_{y}}{2}$이므로

 

a의 페이지랭크 점수는 $r_{a} = r_{m} + \frac{r_{y}}{2}$

 

y는 자기 자신으로 들어오는 link를 포함한다는 점은 특이하다

 

3개의 식이고 3개의 변수를 가지는 연립방정식으로 각 페이지랭크를 구할 수 있다.

 

 

3-7) random surfer model

 

The “random surfer" simply keeps clicking on successive links at random.

 

현재 웹페이지에서 동일한 확률로 어떤 하이퍼링크를 클릭해 다음 웹페이지로 이동하는 random surfer을 가정

 

쉽게 말해 random walk를 통해 surfer는 현재 웹페이지에서 다음 웹페이지로 이동함

 

t시점에 random surfer가 웹페이지 i=1,2,3,...에 있을 확률을 하나의 확률벡터 p(t)로 나타낼 수 있다.

 

 

 

그렇다면 t+1시점에 random surfer가 웹페이지 j에 있을 확률은 얼마일까?

 

t시점에 웹페이지 i에 있을 확률과 1시점 건너서 j로 갈 확률을 곱하면 t시점에 i에 있고 t+1시점에 j에 있을 확률이 된다.

 

조건부확률을 이용해 t시점에 i에 있고 t+1시점에 j에 있을 확률을 구할 수 있다.

 

문제는 현재 t시점에 i에 random surfer이 있을 때 바로 다음시점에 j로 이동할 확률이다.

 

동일한 확률로 다음 웹페이지로 이동하는 random walk를 가정했으므로 i의 나가는 이웃 모두에 대해 균등한 확률로 나갈 수 있다.

 

 

i에 나가는 이웃의 수는 $d_{OUT}(i)$이고 모두 균등한 확률로 나가므로 j로 나갈 확률은 $\frac{1}{d_{OUT}(i)}$

 

이것이 바로 $P(X(t+1) = j | X(t) = i) = \frac{1}{d_{OUT}(i)}$

 

위 식과 전확률법칙을 이용해 모든 i에 대해 더해주면 (이전시점과는 무관하게) t+1시점에 j에 있을 확률을 얻는다.

 

 

위와 같은 random surfer model은 사실 Markov chain의 아주 특별한 형태이다.

 

조금만 생각해봐도 t시점 이전에 어떤 웹페이지에 있든간에 t+1시점에 j에 있을 확률분포를 단 1시점 이전인 t시점에서만 고려했기 때문이다.

 

Markov chain에서 t가 충분히 크면, 즉 random surfer가 충분히 탐색을 한다면

 

t에 무관하게 각 웹페이지 i=1,2,3,...에 도달할 확률이 수렴하는 하나의 확률분포를 생각할 수 있는데, 이것을 stationary distribution이라고 부른다.

 

Markov chain의 stationary distribution

 

그렇다면 우리는 random surfer가 충분히 탐색을 한다고 했을 때 random surfer이 j에 있을 확률을 다음과 같이 구할 수 있다.

 

random surfer가 충분히 탐색을 했을 때 웹페이지 j에 있을 확률

 

 

페이지랭크점수는 random surfer가 충분히 탐색했을 때 j에 있을 확률과 동일하다.

 

조금만 생각해봐도 충분히 탐색했을때 높은확률로 j에 있다면 높은 신뢰성 점수를 받을 것이다.

 

 

3-8) computation algorithm of pagerank value

 

t시점의 웹페이지들의 페이지랭크 점수

 

t=0시점에서 웹페이지들의 페이지랭크 점수를 1/(모든 웹페이지 수)로 초기화함

 

 

위에서 정의한 페이지랭크 점수 구하는 공식을 이용하여 t+1시점의 페이지랭크 점수를 갱신

 

 

 

페이지랭크 점수가 수렴하면 반복을 종료한다.

 

수렴한다는 뜻은 t시점의 페이지랭크점수가 t+1시점의 페이지랭크점수와 충분히 비슷하다는 뜻이다.

 

그러니까 두 벡터사이의 거리가 충분히 작으면 반복을 종료한다.

 

 

 

3-9) 예시로 알아보는 반복곱 계산

 

 

 

$r_{y}^{(0)} = \frac{1}{3}$이고$r_{a}^{(0)} = \frac{1}{3}$이며 $d_{out}(a) = d_{out}(y) = 2$이므로,

 

 

$$r_{y}^{(1)} = \frac{r_{y}^{(0)}}{d_{out}(y)} + \frac{r_{a}^{(0)}}{d_{out}(a)} = \frac{1}{3}$$

 

 

3-10) the problem of random surfer model

 

앞에서 random surfer가 충분히 탐색을 할 때 웹페이지 j에 있을 확률이 j의 페이지랭크 점수와 동일함을 보였다.

 

사실 Markov chain이 수렴하는  stationary distribution을 가질려면 특별한 조건들을 만족해야한다.

 

 

1. spider trap

 

위에서 제시한 random surfer model의 Markov chain은 항상 수렴하는 stationary distribution을 갖지 않는다.

 

 

spider trap형태의 Markov chain은 random surfer가 탐색하다가 시간이 흘러 spider trap b,c에 빠지면 a로 도달하지 못하므로 확률분포가 수렴하지 않는다

 

 

2. dead end

 

random surfer model의 Markov chain이 수렴하는 stationary distribution을 가질 수 있지만 그 값이 합리적인 값으로 수렴하지 않을 수 있다.

 

 

위와 같은 dead end가 있는 경우 0으로 수렴하는 상황이 발생한다

 

그런데 b는 a로부터 1표를 받았으므로 b의 페이지랭크 점수를 0이라고 하기에는 조금 아쉽다.

 

 

3. disconnected graph

 

random surfer model의 Markov chain이 수렴하는 stationary distribution을 가진다고 해도 유일(unique)하지 않을 수 있다.

 

 

 

위와 같이 연결이 끊긴 Markov chain에서 stationary distribution이 여러개일 수 있다.

 

 

3-11) Teleport

 

However, if a real Web surfer ever gets into a small loop of web pages, it is unlikely that the surfer will continue in the loop forever. Instead, the surfer will jump to some other page.

 

논문에서는 실제 사람이 웹 탐색을 하다보면 loop에 빠질 수 있는데 그 loop에 영원히 있지는 않는다는 점을 주목했다.

 

나만해도 loop에 빠지면 그냥 다른 웹페이지로 순간이동해버린다..

 

그래서 수정된 방식으로 만약 웹페이지 i에서 어떠한 곳으로도 갈 수 없다면 임의로 어느 하나의 웹페이지로 동등한 확률로 순간이동할 수 있다고 생각을 한다

 

만약 웹페이지 i에서 j로 가는 하이퍼링크가 있다면 앞면이 나올 확률이 $\alpha$인 동전던지기를 수행합니다.

 

앞면이 나온다면 균일한 확률로 다음 링크로 이동합니다.

 

뒷면이 나온다면 임의의 웹페이지로 순간이동합니다.

 

두 상황을 하나의 상황으로 나타내면 균일한 확률로 다음 링크로 이동할 확률과 임의의 웹페이지로 순간이동할 확률의 가중평균으로 구할 수 있습니다.

 

이렇게 순간이동을 도입하면, random surfer는 충분한 시간으로 탐색을 할 때 모든 웹페이지에 도달 할 수 있습니다.

 

Markov chain은 이러한 경우 시간이 충분히 흐를 때 유일한(unique) stationary distribution을 가진다고 알려져있습니다.

 

 

i에서 j로 도달할 수 있는 경우는 파란부분 확률(균일한 확률로 다음 링크로 이동)과 빨간 부분의 확률(임의의 지점으로 순간이동할 확률)의 가중평균으로 계산된다

 

i에서 j로 도달할 수 없는 경우는 j의 들어오는 이웃 $N_{IN}(j)$가 존재하지않으므로 파란부분이 0이다

 

그래서 빨간부분의 확률로 페이지랭크를 구한다.

 

$\alpha$는 감폭 비율(damping factor)이라고 부르는데 보통 0.8정도로 높은 값을 사용한다. 구글은 0.85를 사용했다고 한다.

 

왜냐하면 i에서 j로 갈 수 있는 경우에 빨간 부분의 확률이 더해져 stationary distribution이 변할 수 있기 때문에 이 영향력을 최대한 줄이고자 그랬다고 한다.

 

 

 

3-12) example of pagerank computation result

 

 

 

각 node의 페이지랭크 점수에 100을 곱하여 그림으로 나타냄

 

B가 다른 node들로부터 투표를 많이 받았으니 제일 높은 것이 당연

 

그런데 C는 오직 1표만 받았는데도 페이지랭크 점수가 대단히 높다

 

가장 점수가 높아 정말로 신뢰할 수 있는 B로부터 받았기 때문에 그렇다

 

 

 

 

prpaperdraft.dvi (stanford.edu)