PageRank는 중요한 페이지에서 링크를 받은 페이지에 더 높은 점수를 줘요. 서로의 점수가 서로를 정하는 순환 관계를 정지분포 방정식으로 바꾸어 계산해요.
체크표에서 행은 링크를 보내는 페이지, 열은 링크를 받는 페이지예요. 체크박스로 링크를 바꾸고 노드를 드래그하여 옮겨 보세요. 노드가 클수록 PageRank가 높아요.
계산 행렬 $M$에서는 보내는 페이지 $i$를 열, 받는 페이지 $j$를 행에 놓아요. 페이지 $i$가 내보내는 링크 수를 $L_i$라고 해요. $i$에서 $j$로 가는 링크가 있으면 $M_{ji}=1/L_i$로 두고, 나가는 링크가 없으면 그 열의 모든 값을 $1/6$로 둬요. 따라서 $M$의 각 열 합은 1이에요. 링크를 따라갈 확률을 $d$, 링크와 관계없이 아무 페이지나 고를 확률을 $1-d$로 두면 Google 행렬은 $G=dM+(1-d)J$예요. 여기서 $J$의 모든 성분은 $1/6$이에요. $r_{k+1}=Gr_k$를 반복하면 $Gr=r$을 만족하고 성분의 합이 1인 PageRank 벡터 $r$을 찾을 수 있어요.
링크를 최소 개수만 바꾸어 F를 1위로 만들어 보세요. 바꾼 링크 수를 기록하고, 받는 링크와 주는 링크가 순위에 미치는 영향을 비교해 보세요.
한 페이지가 링크를 받기만 하고 아무 데도 보내지 않도록 나가는 링크를 모두 꺼 보세요. 감쇠 $d$를 0.99로 높인 뒤 순위를 비교해 보세요.
D·E·F가 서로에게만 링크하도록 바꾸고 세 페이지의 순위를 기록해 보세요. 이 실험은 링크 스팸이 순위를 높이는 원리를 보여 줘요.
// 인접 리스트: links[i] = i번 페이지가 링크하는 페이지들
const links = [[1, 2], [2], [0], [0, 2], [2, 3], [4]]; // ★ 자신의 웹으로 바꿔 보세요.
const n = links.length, d = 0.85; // ★ 링크를 따라갈 확률
let r = new Array(n).fill(1 / n); // 균등 분포에서 출발
for (let it = 0; it < 100; it++) { // 같은 계산을 반복
const next = new Array(n).fill((1 - d) / n);
for (let i = 0; i < n; i++) {
const out = links[i].length;
if (out === 0) { for (let j = 0; j < n; j++) next[j] += d * r[i] / n; }
else links[i].forEach(j => next[j] += d * r[i] / out);
}
r = next;
}
console.log("PageRank:", r.map(x => x.toFixed(4)));
// r의 합이 1인지 확인해 보세요. 링크 하나를 바꾸고 순위 변화를 살펴보세요.