Pagerank

pagerank의 핵심 아이디어는 투표이다.

투표를 통해 사용자 키워드와 관련성이 높고 신뢰활 수 있는 웹페이지를 찾는다.


웹은 웹페이지(정점)와 하이퍼링크(간선)로 구성된 거대한 방향성 있는 그래프이다.


  • 투표관점 pagerank

각각의 웹페이지의 페이지랭크 점수는 받은 투표의 가중치 합으로 정의된다.

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


  • 임의 보행 관점

\(웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i 일 확률을 p_i(t)라고 한다.\) \(이때 p(t)는 길이가 웹페이지 수와 같은 확률분포 벡터가 된다.\)

\[p_j(t+1) = \sum_{i \in N_{in}(j)}\frac{p_i(t)}{d_{out}(i)}\] \[\frac{j로 들어갈 정점i에 있을 확률}{i에서 j로 나갈 확률}\]

즉, p(t) 와 p(t+1)이 동일해진다. 따라서 이러한 p는 정상분포라고 부를 수 있다.

\[p_j = \sum_{i\in N_{in}(j)}\frac{p_i}{d_{out}(i)}\]

투표관점과 임의 보행 관점의 식이 같은꼴인 것을 볼 수 있다.


  • 페이지랭크 계산 : 반복곱

    • 각 웹페이지 i의 페이지랭크점수 r_i(0)를 동일하게 1/웹페이지의수 로 초기화한다.

    • 위의 두 과점의 식을 사용하여 점수를 갱신해 나간다.

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


  • 한계점

반복곱이 항상 수렴하지는 않는다. (스파이더 트랩 문제 : 들어오는 간선은 있지만, 나가는 간선이 없는 정점 집합.)

반복곱이 항상 합리적인 점수로 수렴하지 않는다. (막다른 정점 문제 : 들어오는 간선은 있지만, 나가는 간선이 없음)


위의 한계를 극복하기 위해 순간이동개념을 도입한다.

  • 각 막다른 정점에서 모든 다른 정점으로 가는 간선을 추가한다.
\[r_j = \sum_{i \in N_{in}(j)} \,(\alpha \frac{r_i}{d_{out}(i)}) + (1-\alpha)\frac{1}{\left | V \right |}\]