Contents

  1. 페이지랭크의 배경
    1. 웹과 그래프
    2. 구글 이전의 검색엔진
  2. 페이지랭크의 정의
    1. Voting 관점에서의 PageRank Definition
    2. Random Walk 관점에서의 PageRank Definition
  3. 페이지랭크의 계산
    1. PageRank의 Scoring method : Power Iteration
    2. 문제점과 해결책
      1. 문제점
      2. 해결책
      3. Ranking score with Teleport method

이번 강의에서는 페이지랭크(PageRank) 알고리즘을 배웁니다. 인터넷엔 인터넷 페이지가 셀 수 없이 많습니다. 그리고 네이버나 구글 등의 검색엔진들은 우리가 입력한 키워드에 적합한 페이지들을 보여주죠. 검색엔진들은 어떻게 우리가 원하는 페이지들을 알려줄까요? 페이지들의 우선순위는 어떻게 결정하는 걸까요?

이번 시간에는 구글의 검색 알고리즘인 페이지랭크 알고리즘을 배웁니다. 그리고 페이지랭크 알고리즘에서 발생할 수 있는 문제점과 이를 해결할 수 있는 알고리즘을 추가적으로 배웁니다.

여러분은 과제1-2에서 페이지랭크 알고리즘을 구현해야 합니다. 페이지랭크 알고리즘이 어떻게 동작하는 지 유의깊게 살펴보시면서 강의를 들어보세요 :)


페이지랭크의 배경

웹과 그래프

웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성이 있는 그래프 웹페이지는 정점에 해당 웹페이지가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당 단, 웹페이즈는 추가적으로 키워드 정보를 포함하고 있다.

image


구글 이전의 검색엔진

처음엔 거대한 디렉토리로 정리하려고했음

  • 웹페이지의 수가 증가함에 따라 카테고리 수와 깊이가 무한정 커짐
  • 수십, 수백억 페이지를 저장하기 힘듬

두번째 시도는 키워드에 의존한 검색엔진

  • 사용자가 입력한 키워드에 대해, 해당 키워드를 포함한 웹페이지를 반환함
  • 하지만 악의적 웹페이지에 취약하다는 단점이 있음

그렇다면 관련성 높고 신뢰가능한 웹페이지는 어떻게 만들까? The PageRank Citation Ranking: Bringing Order to the Web라는 논문을 통해서 구글의 창업자 래리페이지와 세르게이 브린이 이를 해결하는 방법을 제안하였다.


페이지랭크의 정의

페이지랭크의 핵심 아이디어는 투표이다. Ranking system을 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이즈를 찾는 것이 목표이다.

image

  • 투표의 주체는 웹페이지이다. 웹페이지는 하이퍼링크를 통해 투표를 한다.

  • 사용자 키워드를 포함한 웹페이즈들을 고려한다.

  • 이때, 웹페이지 $u$가 $v$로의 하이퍼링크를 포함한다면, $u$의 작성자가 판단하기에 $v$가 관련성 높고 신뢰할 수 있다는 것을 의미한다.

  • 즉 $u$가 $v$에게 토표했다고 생각할 수 있다.

    image

즉, 들어오는 in_edge가 많을 수 록 신뢰할 수 있다는 뜻이다.

Q. 그렇다면 들어오는 간선의 수를 세는 것만으로 충분할까?

A. NO!. 악용의 소지가 있다.

  • 웹페이지를 여러개 만들어서 간선의 수를 부풀릴 수 있다. 즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있다.

  • 아래 그림은 인위적으로 만들어진 것으로 의심되는 웹 그래프의 일부이다.

    image

  • 온라인 소셜 네트워크에서도 흔히 발견되는 악용사레는 많다.


Voting 관점에서의 PageRank Definition

Q. 이런 악용을 막으려면?

A. 이런 악용에 의한 효과를 줄이기 위해, 페이지랭크에서는 가중 투표를 진행한다. 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주하게 된다. 반면, 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주한다. 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방식 중 하나이다.

이 같은 투표 자체에 관련성과 신뢰성을 통한 가중치를 부여하는 방식은 일종의 재귀방식으로 생각할 수 있다. 페이지랭크는 측정하고자 하는 웹페이지의 관련성 미 신뢰도를 PageRank Score라고 부른다.

image

  • 각 웹페이지는 각각의 vertex에서 나가는 Neighbor에 \(\frac{자신의~페이지랭크~점수}{나가는~Neighbor의~수}\)만큼의 가중치로 투표한다.
  • 위 그림에서 웹페이지 $j$는 웹페이지 $x,y,z$에게 각각 가중치 $\frac{r_j}{3}$으로 투표한다.
  • $r_j$는 웹페이지 $j$의 페이지랭크 점수를 의미한다.
  • 여기서 $j$는 $r_j=r_i/3 + r_k/4$만큼의 Ranking score를 부여받는다.
  • 이를 일반화하면 결과는 다음과 같다.
\[r_j=\sum_{i\in N_{in}(j)}\frac{r_i}{d_{out}(i)}\]


Random Walk 관점에서의 PageRank Definition

페이지랭크는 임의 보행의 관점에서도 정의할 수 있다.

  • 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정하자
  • 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑한다.

만약 웹서퍼가 $t$번째 방문한 웹페이지가 웹페이지 $i$일 확률을 $p_i(t)$라고 하자. 그러면 $p(t)$는 길이가 웹페이지 수와 같은 확률분포 벡터가 된다. 이 때, 아래의 식이 성립함을 확인할 수 있다.

\[P_i(t+1)=\sum_{i\in N_{in}(j)}\frac{p_i(t)}{d_{out}(i)}\]

이 과정을 무한히 반복하고 나면, 확률분포 $p(t)$는 수렴하게된다. 즉, $p(t)=p(t+1)=p$ 가 성립한다. 수렴한 확률분포 $p$는 정상분포(Stationary Distribution)이라고 부른다. 그러면 앞서 소개한 수식을 아래와 같이 바꿀 수 있다.

\[\begin{align} &P_i(t+1)=\sum_{i\in N_{in}(j)}\frac{p_i(t)}{d_{out}(i)}\\ &\Rightarrow p_j=\sum_{i\in N_{in}(j)}\frac{p_i}{d_{out}(i)} \end{align}\]

이는 앞서 소개한 투표 관점에서의 페이지랭크 점수와 동일한 식임을 확인할 수 있다.


페이지랭크의 계산

페이지 랭크를 계산하는 대표적인 방식을 알아보고, 이 방식의 문제점과 해결 방법에 대해 이야기해보자.


PageRank의 Scoring method : Power Iteration

반복곱(power iteration)은 다음 세 단계로 구성된다.

  1. 각 웹페이지 $i$의 페이지 랭크 점수 $r_i^{(0)}$를 동일하게 \(\frac{1}{\#웹페이지}\)로 초기화한다.

  2. 다음 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신한다

    \[r_j^{(t+1)}=\sum_{i\in N_{in}(j)}\frac{r_i^{(t)}}{d_{out}(i)}\]

  3. 페이지랭크 점수가 수렴하였으면 종료한다. 아닌경우 step 2. 로 돌아간다.

example

image

\[\begin{align} r_y &= 1/3~|~1/3~|~5/12~|~~9/14~~|~ \cdots ~|~ 6/15\\ r_a &= 1/3~|~3/6~|~~1/3 ~~|~ 11/24~|~\cdots~|~6/15\\ r_m &= 1/3~|~1/6~|~3/12~|~~~1/6~~~|~\cdots~|~3/15\\ Iteration &= ~~0~~~|~~~1~~~|~~~~2~~~~|~~~~~3~~~~~| \end{align}\] \[r_j=\sum_{i\in N_{in}(j)}\frac{r_i}{d_{out}(i)}\]

위 식을 계속적으로 반복하면서 수렴시킨다.


문제점과 해결책

문제점

그렇다면 항상 수렴할까?

정답 : NO!

image

위 그래프 구조에서는 항상 수렴하지 않으며, 반복곱을 실행하여도 loop에 빠져 진동발산하게된다.

image

위 예시에서 들어오는 간선은 있지만, 나가는 간선은 없는 정점의 집합(Cycle)인 스파이더 트랩(Spider trap)에 대한 문제이다.

그렇다면 반복곱이 합리적(reasonable)인 점수로 수렴하는 것을 보장할 수 있는가?

정답 : NO!

image

위 그림에서는 들어오는 간선은 있지만, 나가는 간선이 없는 막다른 정점이 존재한다. 이 때 PageRank는 0으로 수렴한다.

image

이처럼 들어오는 간선이 존재하지만, 나가지 못하는 점점을 막다른 정점(Dead End)라고 한다.


해결책

이 같은 두 가지 문제를 해결하기 위해 사용되는 방식은 순간이동(Teleport)방식이다.

Random walk 관점에서, 웹을 서핑하는 웹서퍼의 행동을 다음과 같이 수정한다.

  1. 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동한다.
  2. 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 $\alpha$인 동전을 던진다.
  3. 앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭한다.
  4. 뒷면이라면 임의의 웹페이지로 순간이동한다.

1번과 4번의 임의의 웹페이지는 전체 웹페이지들 중 하나를 균일확률로 선택한다. 순간이동에 의해 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어지게되고, 이때 2번에서의 $\alpha$를 감폭비율(Damping Factor)라고 부르며 값으로 보통 0.8정도를 사용한다.


Ranking score with Teleport method

기존 pagerank scoring 방식을 Teleport 방식으로 바꾸는 과정은 다음과 같다.

  • 각 막다른 정점에서(자신 포함) 모든 다른 정점으로 가는 간선을 추가한다.

  • 아래 수식을 사용하여 반복곱을 수행한다.

    \[r_j=\sum_{i\in N_{in}(j)}\left(\alpha \frac{r_i}{d_{out}(i)}\right)+(1-\alpha)\frac{1}{\vert V\vert}\]
  • 여기서 $\vert V\vert$는 전체 웹페이지의 수를 의미한다.
  • +를 기준으로 좌측 Summation은 하이퍼링크를 따라 정점 $j$에 도착할 확률을 의미한다.
  • +를 기준으로 우측은 순간이동을 통해 정점 $j$에 도달할 확률을 의미한다.

수정된 페이지 랭크 점수 예시

image

B는 가장 많은 간선이 들어오기 때문에 확률이 높다 1.6의 확률을 가지는 보라색 정점은 input 간선이 없음에도 “순간이동”을 통해 들어올 가능성이 있기 때문에 확률값이 0이 아니다. 마지막으로 정점 C는 input edge가 하나뿐이지만, 그 하나가 가장 높은 확률값을 지니는 vertex B이므로 두번째로 높은 확률을 지닌다