페이지랭크 (PageRank)

1998년 구글이 검색 순위를 매길 때 쓴 알고리즘. "어떤 페이지를 중요한 페이지들이 많이 링크하면, 그 페이지도 중요하다"는 순환 정의를, 웹 전체를 돌아다니는 가상의 서퍼(surfer)로 풀어낸다.

1. 핵심 아이디어 — 링크는 투표다

• 페이지 A가 페이지 B로 링크를 걸면, A가 B에게 한 표를 준다.
• 단, A가 가진 표의 힘은 A 자신의 중요도(랭크)에 비례한다. 유명한 사이트의 링크가 더 값지다.
• A가 링크를 여러 개 걸면 표가 쪼개진다. 링크 k개면 각 링크는 랭크(A)/k 만큼 전달.
• "중요도를 계산하려면 중요도가 필요하다"는 순환이다 → 반복해서 수렴시킨다.

2. 랜덤 서퍼 모델

웹을 무작정 돌아다니는 사람을 상상하자. 매 클릭마다:

• 확률 d (보통 0.85): 현재 페이지의 링크 중 하나를 무작위로 클릭한다.
• 확률 1 − d: 지겨워져서 주소창에 아무 페이지나 쳐서 순간이동한다 (teleport).

이 사람이 아주 오랫동안 돌아다녔을 때 각 페이지에 머무른 시간의 비율이 바로 그 페이지의 PageRank다. 순간이동 항 1 − d 덕분에 링크가 없는 막다른 페이지나 서로만 링크하는 함정에 영원히 갇히지 않는다.

N = 전체 페이지 수, d = 감쇠 계수(damping), q → p = q가 p로 링크, L(q) = q의 나가는 링크 수. 모든 페이지의 PR을 더하면 항상 1.

3. 직접 돌려보기 — 파워 반복(power iteration)

아래 6개 페이지(A~F)와 화살표(링크)로 이뤄진 미니 웹이다. 처음엔 모두 랭크 1/6 ≈ 0.167로 시작한다. 「1회 반복」을 누를 때마다 위 공식을 모든 페이지에 한 번씩 적용한다. 몇 번만 반복하면 값이 거의 안 변한다(수렴). 원의 크기 = 현재 랭크.

4. 랜덤 서퍼로 검증하기

공식 없이, 정말로 서퍼 한 명을 수십만 번 클릭시켜 페이지별 방문 비율을 세어 보자. 큰 수의 법칙에 따라 이 비율은 위에서 계산한 PageRank로 수렴한다.

5. 알고리즘 코드

# links[q] = q 페이지가 링크를 거는 대상들의 리스트
def pagerank(links, d=0.85, iters=50):
    pages = list(links)
    N = len(pages)
    pr = {p: 1 / N for p in pages}     # 균등 분포로 시작

    for _ in range(iters):
        nxt = {p: (1 - d) / N for p in pages}   # 순간이동 몫
        for q in pages:
            outs = links[q]
            if outs:
                share = d * pr[q] / len(outs)
                for p in outs:
                    nxt[p] += share             # q의 표를 균등 분배
            else:                                # 막다른 페이지(dangling)
                for p in pages:
                    nxt[p] += d * pr[q] / N     # 전체에 골고루
        pr = nxt
    return pr

한 번 반복에 O(V + E). 실제 웹(수십억 페이지)에서도 링크 행렬이 희소(sparse)해서 40~50회 반복이면 충분히 수렴한다.

6. 왜 수렴할까 — 마르코프 연쇄

랭크 벡터에 "링크 따라가기 + 순간이동" 변환을 반복 적용하는 것은, 확률 행렬 M을 계속 곱하는 것과 같다: PR ← M · PR. 순간이동 항이 모든 칸을 양수로 만들어 주므로(에르고딕), 페론–프로베니우스 정리에 의해 시작값과 무관한 유일한 정상 분포(고윳값 1의 고유벡터)로 수렴한다. PageRank는 결국 이 거대한 행렬의 주고유벡터를 파워 반복으로 구하는 것이다.

7. 어디에 쓰이나