jihoon's profile image

jihoon

July 21, 2019 23:59

PageRank

페이지랭크(PageRank)는 구글의 설립자로 널리 알려진 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 웹 문서의 중요도를 구할 때 사용합니다. 이 포스트에서는 페이지랭크 알고리즘의 원리와 어떻게 작동하는지에 대해 다룹니다.

웹을 그래프 형태로 나타내기

PageRank 알고리즘에서는 월드 와이드 웹의 문서들을 노드로 대응시키고 문서에서 다른 문서로 넘어가는 하이퍼링크를 간선으로 대응시켜서, 유방향 그래프로 웹을 나타냅니다. 보통 이러한 그래프를 웹 그래프라고 합니다. 예를 들어, 이 글과 이 글이 레퍼런스한 문서들이 그래프의 노드에 해당하고, Reference로 넘어가는 하이퍼링크가 방향이 있는 그래프에서 간선에 해당합니다. 이 때 하이퍼링크는 이 문서 관점에서는 다른 문서로 나가는 아웃링크이면서 동시에 reference 문서 기준으로는 이 문서로부터 들어오는 인링크로 표현할 수 있습니다. 비슷한 방식으로 만들어지는 그래프로 논문을 정점으로 하고, 논문에서의 인용을 간선으로 나타낸 그래프인 Citation 그래프가 있습니다.

노드의 중요도 구하기

위에서 웹을 그래프의 형태로 나타낼 수 있다는 것을 보였으니, PageRank는 이제 그래프 상에서 각 노드의 중요도를 구하는 알고리즘이라고 할 수 있습니다. 그렇다면 노드의 중요도는 어떻게 결정될까요?

먼저 생각해볼 수 있는 것으로 다른 문서로부터 들어오는 인링크가 많을수록 문서의 중요도가 높아진다고 생각할 수 있습니다. 다른 웹 문서가 많이 참조하는 웹 문서는 중요한 웹 문서일 확률이 높기 때문입니다. 반대로 문서의 아웃링크 개수는 그 문서의 중요도에 큰 영향을 미치지 않습니다. 예를 들어 누군가 임의로 네이버, 다음, 구글, 유튜브와 같이 사람들이 많이 이용하는 사이트의 하이퍼링크를 걸어놓은 문서를 만든다 해도 그 문서의 중요도는 높다고 말할 수 없습니다.

그렇다면 인링크가 많은 문서는 무조건 중요도가 높은 문서일까요? 해커가 아무 웹페이지를 1000개 만들고 완전 그래프 형태로 하이퍼링크를 이었다고 가정해봅시다. 이 때 각 문서는 999개의 인링크를 가지게 됩니다. 그러나 이 1000개의 웹 문서들은 해커가 임의로 만든 것들이기 때문에 중요도가 높을 확률은 매우 희박합니다. 그러므로 인링크의 개수가 많다고 무조건 문서의 중요도가 높지는 않습니다. 반대로 인링크의 개수가 많지 않더라도 들어오는 인링크들이 대부분 중요도가 높은 문서로부터 들어오는 인링크라면, 문서의 중요도가 높아야 할 것입니다.

위의 그림은 페이지랭크 알고리즘을 어떤 그래프에 적용한 결과물입니다. 노드 B의 경우에는 인링크가 많아서 중요도가 크게 측정된 반면에, 노드 C의 경우에는 인링크가 하나 뿐이지만, 그 인링크가 중요도가 높은 노드 B로부터 들어오는 링크이기 때문에 중요도가 높아진 것을 확인할 수 있습니다.

페이지랭크 알고리즘

페이지랭크 알고리즘에서는 같은 문서에서 나가는 아웃링크들의 중요도를 모두 같다고 가정합니다. 그러므로 아래의 그래프에서 노드 B에서 A로 나가는 아웃링크와 노드 B에서 C로 나가는 아웃링크의 중요도는 같습니다. 또한 아웃링크의 중요도는 문서의 중요도와 비례하게 정해지고, 노드의 중요도는 그 노드로 들어오는 인링크의 중요도의 합으로 재귀적으로 표현됩니다.

노드 A, B, C의 중요도를 차례대로 $r_{A}$, $r_{B}$, $r_{C}$ 라고 해봅시다. 페이지랭크 알고리즘에서 노드 B에서 A로 나가는 링크의 중요도와 노드 B에서 C로 나가는 링크의 중요도는 모두 $r_{B} / 2$가 됩니다. 그리고 각 노드의 중요도는 다음과 같은 식으로 표현할 수 있습니다:

$r_{A} = r_{A} / 2 + r_{B} / 2$

$r_{B} = r_{A} / 2 + r_{C}$

$r_{C} = r_{B} / 2$

이 식을 풀면 이제 각 노드의 중요도를 구할 수 있습니다! 그러나 이 식의 해는 유일하지 않습니다. $(r_{A}, r_{B}, r_{C}) = (c_{A}, c_{B}, c_{C})$ 가 해라면, $(r_{A}, r_{B}, r_{C}) = (2 \times c_{A}, 2 \times c_{B}, 2 \times c_{C})$ 또한 해가 될 수 있기 때문입니다. 그래서 이 알고리즘에서는 유일성을 확보하기 위해 노드의 중요도의 합을 1로 고정시킵니다. 위의 예시에서는 $(r_{A}, r_{B}, r_{C}) = (2/5, 2/5, 1/5)$가 유일한 해가 됩니다.

그렇다면 일반적인 경우 식의 해를 구할 수 있는 방법에 대해 알아봅시다. 가장 많이 사용하는 방법으로는 행렬과 벡터를 이용한 방법이 있습니다. 위의 식을 행렬과 벡터를 이용하여 나타내면 아래와 같이 나타낼 수 있습니다:

$ \begin{bmatrix} r_{A} \ r_{B} \ r_{C} \end{bmatrix} = \begin{bmatrix} 0.5 & 0.5 & 0.0 \ 0.5 & 0.0 & 1.0 \ 0.0 & 0.5 & 0.0 \end{bmatrix} \begin{bmatrix} r_{A} \ r_{B} \ r_{C} \end{bmatrix} $

맨 처음에 중요도를 모두 $1 / N$으로 놓고, 행렬 곱셈을 계속 반복하면 실제 중요도로 수렴을 하게 됩니다. 이러한 방법을 Power Iteration이라고 부릅니다. 위의 예시에서 Power Iteration을 적용한 결과는 다음과 같고, 실제 중요도로 잘 수렴하는 것을 알 수 있습니다.

문제점

위에서 설명한 페이지랭크 알고리즘은 모든 그래프에서 잘 적용되지는 않습니다. 대표적으로 다음과 같은 두 가지의 경우에 대해서 잘 작동하지 않는다고 알려져 있습니다:

1. 아웃링크가 하나도 없는 노드가 존재하는 경우 (Dead Ends)
2. 전체 그래프보다 작은 어떤 그룹의 모든 아웃링크가 그 그룹 안에만 존재하는 경우 (Spider traps)

먼저 Dead Ends의 경우부터 생각해봅시다. 노드가 A, B로 두 개이고, A에서 B를 잇는 edge만 존재하는 그래프를 생각해봅시다. 이 때, 노드의 중요도는 다음과 같은 식으로 표현됩니다:

$r_{A} = 0$

$r_{B} = r_{A}$

결과적으로 노드의 중요도는 모두 0이 되고, 제대로 노드의 중요도를 구하지 못하게 됩니다.

위의 노드가 세 개인 그래프에서, A에서 B로 가는 간선을 제거했을 때 A의 아웃링크는 자기 자신으로 가는 링크만 남게 됩니다. 그러므로 A 하나로 구성된 그룹이 Spider trap이 됩니다. 이 때, 노드의 중요도는 다음과 같은 식으로 표현됩니다.

$r_{A} = r_{A} + r_{B} / 2$

$r_{B} = r_{C}$

$r_{C} = r_{B} / 2$

결과적으로 $r_{A}$만 1이 되고 나머지 값들은 0이 됩니다. 그러므로 노드의 중요도를 제대로 구했다고 볼 수 없습니다.

해결법: Teleport

이러한 문제를 해결하기 위한 방법으로 Teleport라는 것이 제안되었습니다. Teleport는 아래와 같이 동작합니다.

1. $\beta$의 확률로, 기존 페이지랭크 알고리즘과 동일하게 수행한다.
2. $(1 - \beta)$의 확률로, 완전히 랜덤한 페이지로 이동한다. (Teleport)

이 Teleport 방법을 이용하면, 위의 문제들 중 하나였던 Spider traps 문제를 해결할 수 있습니다. 기존의 알고리즘은 Spider Trap에 한 번 들어가면 빠져나올 수 없었지만, 이제는 일정 확률로 빠져나올 수 있게 되었기 때문입니다. 보통 $\beta$는 0.8 ~ 0.85 정도 값으로 사용됩니다.

Teleport 방법을 적용하면, 노드의 중요도를 구하는 식은 아래와 같이 바뀌게 됩니다:

$r_{A} = (1 - \beta) \times 1 / 3 + \beta \times ( r_{A} + r_{B} / 2)$

$r_{B} = (1 - \beta) \times 1 / 3 + \beta \times ( r_{C})$

$r_{C} = (1 - \beta) \times 1 / 3 + \beta \times ( r_{B} / 2)$

그리고 $\beta = 0.8$일 때, Teleport를 적용한 페이지랭크 알고리즘의 결과는 아래와 같고, 전과 같은 문제가 발생하지 않는 것을 확인할 수 있습니다.

하지만 이 Teleport 방법도 Dead Ends 문제를 완벽하게 해결해주지는 못합니다. $(1 - \beta)$의 확률로 Teleport를 하고 있지만, 여전히 중요도의 합이 1이 되는 해가 존재하지 않기 때문입니다. 다행이게도, 이 경우의 해결법은 간단합니다. 아웃링크가 없는 노드의 경우에는 $(1-\beta)$의 확률로 Teleport하는 대신, 무조건 Teleport만 하도록 하면 문제를 해결할 수 있습니다.

PageRank의 응용

페이지랭크 알고리즘은 웹 문서의 generic한 중요도를 구한다는 특징이 있습니다. 그렇기 때문에 PageRank를 이용하여 개인화된 검색 결과를 얻기는 쉽지 않습니다. 유저마다 선호하는 검색 결과가 다른데, PageRank는 일반적인 상황만 고려하기 때문입니다.

이러한 문제를 해결하기 위해서 Topic-Specific PageRank가 고안되었습니다. 기존의 PageRank의 경우는 모든 노드에 대해서 동일한 확률로 Teleport가 되는 것에 비해서, Topic-Specific PageRank의 경우에는 Teleport가 일어날 때 특정 set에 속한 웹 페이지로만 Teleport가 일어납니다. 그래서 선택된 특정 set의 웹 문서의 중요도가 상대적으로 상승합니다. 예를 들어, 뉴스를 추천하는 경우 스포츠 뉴스를 선호하는 독자에게 추천 리스트를 제공하기 위해서 teleport할 때 스포츠에 해당하는 웹 페이지로만 Teleport가 일어나도록 할 수 있고, 기존 PageRank 알고리즘에 비해서 더 개인화된 결과를 얻을 수 있습니다.

Topic-Specific PageRank 중에서 set의 크기가 1로 고정된 경우를 Random walk with Restart(RWR)라고 부릅니다. Random walk with Restart를 사용하면 어떠한 노드의 관점에서 다른 노드들의 중요도를 나타낼 수 있습니다.

또한, PageRank를 공격하기 위한 여러 수단들이 연구되었습니다. 이러한 것들 중 대표적으로 블로그 댓글과 같이 유저들이 글을 남길 수 있는 곳에 A로 통하는 스팸 아웃링크를 달아놓고 임의로 많은 사이트를 만든 후 그 사이트들과 A 사이에 양방향 링크를 추가하는 방법이 있고, 이론적으로 PageRank 알고리즘이 A의 중요도를 고평가하게 되는 문제가 발생하게 됩니다. 이러한 공격들을 막기 위해 신뢰할 수 있는 사이트로만 Teleport가 일어날 수 있도록 하는 TrustRank 등의 알고리즘이 페이지링크 알고리즘 이후에 고안되었습니다.

마무리

이 포스트에서는 먼저 페이지랭크 알고리즘이 어떻게 작동하는지에 대해서 알아보고, 예외 상황을 처리하기 위한 Teleport 기법 그리고 페이지랭크의 문제점을 해결하기 위해 제안된 여러 알고리즘에 대해 알아보았습니다.

여담으로, 파이썬 패키지인 NetworkX의 경우 이미 구현된 PageRank가 제공되고 있어서, 페이지랭크 알고리즘을 직접 처음부터 구현할 필요 없이 패키지의 내장 함수를 이용하여 알고리즘을 사용할 수 있습니다.

Reference

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets (Chapter 5. Link Analysis)