2015년 2월 7일 토요일

Page rank 머냐 이거 먹는거냐! (1화)

Page rank 머냐 이거 먹는거냐! (1화)

목표

각각의 웹페이지에 점수를 매겨서
검색 사이트에서 특정 단어에 대한 검색을 할 경우 웹페이지의 점수가 높은 애부터 나열하자

ex) 네이버에서 검색을 하면 신뢰성있고 연관성있는 결과물이 상위에 노출된다.

기본 아이디어

모든 웹페이지는 링크로 연결되어 있다고 가정할수있다.
링크는 들어오는 링크(in link) 와 나가는 링크로(out link) 분리할수있다.
더 중요한 페이지는 많은 웹페이지가 가리키고 있을것이다.

위 그림(1)을 보면 각각의 페이지들 있고 페이지들은 링크로 연결되어있다.
총 페이지 점수의 합은 100이다.
많은 링크를 받을 수록 높은 점수를 같는다.
높은 점수의 페이지가 가리키는 페이지는 높은 점수를 같는다.

C는 한개의 in link를 가지고 있지만 B가 점수가 높기 때문에 높은 점수를 같는다.

점수를 어떻게 계산해야 할까?(재귀식)

alt text

위 그림(2)을 보면 j 페이지의 점수를 계산하는 방법이 나와있다

j 페이지는 i, k 페이지에서 링크를 받고 있고 두개의 페이지 점수/out link수 를 기반으로 매겨진다.

j 페이지는 3개의 out link를 가지고 있고 각각의 링크의 점수는 j/3 이다.

위의 식을 보면 재귀적으로 각 페이지의 점수가 매겨지는걸 알수있다.
공식으로 하면 아래와 같다.

$r_j = \frac{r_i}{3} + \frac{r_k}{4}$
i 페이지는 3개의 out link를 가지고 있다.
k 페이지는 4개의 out link를 가지고 있다.

위식을 좀더 추상화하면 아래의 식을 얻을수있다.

$r_j = \sum_{i \to j} \frac{r_i}{d_i}$
1번식
j 페이지의 점수는 j로 들어오는 out link 들의 합이다.
out link 점수는 원페이지(i) 점수 / 원페이지의 out link 수

흐르는 모델 (Flow model)

중요한 페이지의 out link 점수는 더 높다.
그러므로 중요한 페이지에게 out link 를 받은 페이지의 점수는 높다

alt text

위 그림(3) 을 보자
위그림의 우측 상단의 그림은 웹이 3개의 사이트로 이루어져 있다고 가정한다.
그럼 실제로 페이지 랭크를 구해보자!

1번 식을 적용하면 아래의 점수를 구할수 있다.

$r_y = r_y/2 + r_a/3$
$r_a = r_y/2 + r_m$
$r_m = r_a/2$

우리는 3개의 미지수와 3개의 공식있다. 풀면된다.
하지만 비례식이므로 답이 여러개다 그러니

$r_y + r_a + r_m = 1$

아래의 조건을 추가하자

그럼 답은

$r_y = 2/5$
$r_a = 2/5$
$r_m = 1/5$

과 같다

page rank 2화 실적에 적용해 볼까나?

이미지 출처