페이지 랭크 알고리즘(Page Rank Algorithm)
- PageRank was used to simulate where Web surfers, starting at a random page, would tend to congregate if they followed randomly chosen outlinks from the page at which they were currently located, and this process were allowed to iterate many times. Pages that would have a large number of surfers were considered more “important” than pages that would rarely be visited. Google prefers important pages to unimportant pages when deciding which pages to show first in response to a search query.
- The content of a page was judged not only by the terms appearing on that page, but by the terms used in or near the links to that page. Note that while it is easy for a spammer to add false terms to a page they control, they cannot as easily get false terms added to the pages that link to their own page, if they do not control those pages.
PageRank Algorithm은 페이지의 중요성을 측정하는 알고리즘으로서 페이지간의 Link를 분석하는 알고리즘이다. 이렇게 페이지간의 Link를 분석함으로서 Spam Page를 걸러낼 수 있다.
These two techniques together make it very hard for the hypothetical shirt vendor to fool Google. While the shirt-seller can still add “movie” to his page, the fact that Google believed what other pages say about him, over what he says about himself would negate the use of false terms. The obvious countermeasure is for the shirt seller to create many pages of his own, and link to his shirtselling page with a link that says “movie.” But those pages would not be given much importance by PageRank, since other pages would not link to them. The shirt-seller could create many links among his own pages, but none of these pages would get much importance according to the PageRank algorithm, and therefore, he still would not be able to fool Google into thinking his page was about movies.
Spam Page를 만들고, 해당 Spam Page로 향하는 수 없이 많은 Link가 있는 Page를 만들 수는 있을 것이다. 하지만 그렇게 한다고 하더라도, 그 Spam Page Link를 가지는 Page를 가리키는 Link는 없으므로 그렇게 큰 중요도를 차지할 수 없다.
Random Surfer와 Distribution
페이지와 Surfer 간의 관계를 모델링 하기 위한 제약사항이 존재한다. 항상 임의의 페이지에서 임의의 페이지로 링크 할 수 있어야 한다.
위의 예제(Figure 5.1) 에서 Graph는 다음과 같은 Transition Matrix로 표현될 수 있다.
이 때에 임의의 한 Web Surfer 가 i 번 링크를 이동을 했을 때에 최종적으로 어느 페이지에 있을지에 대한 확률을 계산을 하면 다음과 같다.
이를 통하여 우리는 i 번 링크를 탐색했을 때, Web Surfer가 해당 Page에 있을 확률분포를 구하는 식을 일반화 시킬 수 있다.
i가 충분히 클 때, 일정한 값으로 수렴하는걸 알 수 있다.. 하지만 이런 유의미한 값으로 수렴하는 것은 Figure 5.1 에서 적용된 가정이 존재해야만 한다. “어떤 임의의 링크에서도, 다른 임의의 링크로 이동할 수 있다.” 이러한 가정을 만족하는 것을 책에서는 Strongly Connected Component(SCC) 라고 부른다. 웹에서의 모든 페이지 링크가 SCC 가정을 따른다면 좋겠지만. 아무것도 하지 않은 RAW한 현실에서는 그렇지 않다.
페이지 링킹 관계
SCC를 중심으로 웹페이지의 링킹관계를 분류하면 Figure 5.2와 같다.
In-Component: In-Component -> SCC 일방통행인 페이지들.
Out-Component: SCC -> Out-Component 일방통행인 페이지들.
SCC: SCC -> SCC 가 가능한 페이지들.
Tendrils Out : Out-Component -> Tendrils-Out 일방통행인 페이지들.
Tendrils In : Tendrils-In -> In-Component 일방통행인 페이지들
Tube : In-Componet -> Tube -> Out-Componet 일방통행인 페이지들.
깊이 생각해볼만한 문제다. 책에서는 내용이 간단하게 서술되어 있지만 그렇게 간단하게 서술되어 있음으로서 정의된다. Tendrils 를 In과 Out를 위와같이 정의함으로서 In-Component와 Out-Component를 특별한것으로 제약한다. In-Component는 다시는 되돌아갈 수 없는 시작지점으로. Out-Component는 SCC로 되돌아갈 수 없게 만드는 종착역으로.
Dead Ends
Tendrils-Out과 Out-Component 같은, SCC를 벗어나게 만드는 종착역같은 Pages들은 Random Surfer를 SCC내에서 탈출시키고 이후로 다시는 돌아갈 수 없게 만들어버려 제약된 SCC 구조에서는 잘 작동하던 알고리즘을 파괴시켜버린다.
Figure 5.1 에서, C가 가지고 있는 링크를 수정해 C 페이지를 Dead End로 만들었다. 이것을 가지고 SCC에서 돌아가던 알고리즘을 시행하면 다음과 같이 된다.
Random Link를 클릭하는 Surfer는 무한히 링크를 탐색하다보면 최종적으로 C로 수렴하게 될 것이라고 우리는 쉽게 예측할 수 있다. 하지만 위의 그림에서 볼 수 있다 싶이 C는 1이 아니다. 그것은 애초에 SCC의 제약조건을 가정하고 세워진 식이기 때문이다. 마치 잘작동하던 함수가 예외가 발생한 경우 미쳐날뛰는 것과 같다. 그렇기에 우리는 Dead-End 에 대한 예외 처리를 해줄 필요가 있다.
책에서는 어떻게 Dead End를 일반적으로 제거하는지 보여주기 위해서 Figure 5.4 와 같은 예제를 준비했다. 페이지의 링크 가중치를 나타내는 Transition Matrix인 M의 원소를 살펴보면 Dead-End인 노드는 모든 값이 0이다. 따라서 첫회차에 E가 Dead End 임을 알 수 있다. 두번 째에 C가 Dead End임을 알 수 있다.
이 새로운 그래프는 SCC 이다. 따라서 기존의 알고리즘에서 문제없이 작동한다.
하지만 아직, C와 E에 대한 Page Rank 값을 구하지 않았다. C와 E 또한 구해져야한다. 다음과 같다.
(Page Rank of C) = (A => C) * (Page Rank of A) + (D => C) * (Page Rank of D) = 1/3*2/9 + 1/2*3/9 = 13/54
E의 Page Rank는 C와 같다.
이제 더 이상, 각 Page Rank의 합이 1이 되지 않는다.
Spider Traps
Spider Traps은 Dead Ends는 아니지만, 일부 노드들로만 순환을 이루게 만들어진 것을 말한다. 이러한 Spider Traps의 특징은, 충분히 직관적으로 봐도 Page Rank가 높은 페이지들또한 Page Rank의 값을 0으로 수렴하게 만든다는 것이다. 그것은 자명하다.
책에서는 이를해결하기위헤 임의의 페이지로 Random하게 Teleporting 한다고 가정한다.
e는 모든 항의 값이 1인 Vector를 말한다. βMv 로 나온 결과값에 Random 하게 Teleporting 하는 값을 넣어주는 것이다. 우리는 여기에서 Mv의 모든 항의 값을 더하면 1이 된다는걸 알고있다. 그 값에 β 을 곱하고 (1-β)한 값을 더해준다면, 새로나오는 v’ 백터또한 마찬가지로 모든 항의 값을 더하면 1이 된다는걸 알 수 있다.
Figure 5.6에서 β의 값을 0.8로 설정하여 Random Teleporting을 가정하여 계산을 진행하면 일정한 값으로 수렴하는걸 알 수 있다. Teleporting에 의해서 SCC구조가 되기 때문이다.
Dead Ends는 노드를 삭제해서 계산하고. Spider Traps 같은 경우에는 Random Teleporting을 넣는다. 왜 전자에서 Random Teleporting 가정을 사용하지 않은가? 그렇게 해도 되지만, Dead End는 쉽게 알아낼 수 있지만, Spider Traps 같은 경우에는 순환이 클 경우에 쉽게 알아낼 수 없기 때문이라고 생각한다.(이 부분은 나의 가정이고 생각이다. 따라서 틀릴 수 있다. 만약에 틀렸다면 코멘트를 남겨주면 고맙겠다.)
참고
