구글(Google)의 PageRank 알고리즘

▣ 구글(Google)의 PageRank 알고리즘

구글의 페이지 순위 알고리즘은 기본적으로 얼마나 많은 참조(hyper link)가 있는가를 기준으로 순위를 결정함

서로 링크가 걸려있는 A, B, C 라는 3개의 페이지가 있을 경우,

특정페이지 A의 순위(Rank)는 다음과 같이 계산함
A의 Rank = (B의 Rank / B가 가진 Link수) + (C의 Rank / C가 가진 Link수) + …

즉, 특정 페이지의 Rank 를 해당 페이지에 존재하는 참조(Link)수로 나눈 것을 모두 합하면

페이지 A의 순위(Rank)가 결정된다.

* 이 문제는 위의 내용은 참고만 하고 박스안의 공식만 집중해서 이해하고 풀어야함

 - 핵심은 총 링크 개수, 해당 페이지 참조 개수로 전이 행렬을 구해야함

 

예) 페이지 1의 경우 총 참조(Link)는 2개 이고, 그 중 페이지 1에 대한 참조는 1 이므로,
M11 = 1/2 이다.

 * 참조(Link)는 위의 선의 화살표가 본인한테 향해 있는 것이다.

 

 

 

▶ j가 링크한 전체 페이지 수 : 본인(j)한테 화살표가 향해 있는 것

Mj(j=1)  : 2개

Mj(j=2)  : 2개

Mj(j=3)  : 1개

 

▶ 페이지 j가  페이지 i에 대한 링크 : 본인(j)한테 향한 화살표 중 페이지 i에서 온 링크

Mij(i=1, j=1) : 1/2

Mij(i=2, j=1) : 1/2

Mij(i=3, j=1) : 0

Mij(i=1, j=2) : 1/2

Mij(i=2, j=2) : 0

Mij(i=3, j=2) : 1/2

Mij(i=1, j=3) : 0

Mij(i=2, j=3) : 1/1 = 1

Mij(i=3, j=3) : 0

 

M값이 1/2 인 항목은 총 4개, M값이 1인 항목은 총 1개가 존재함