페이지랭크 알고리즘 (PageRank algorithm)

논문

페이지랭크 알고리즘 (PageRank algorithm)

decaf coffee 2024. 11. 3. 11:47

Page Rank 알고리즘은 유저가 검색한 키워드가 아닌 웹사이트간 관계로 스코어를 측정하고, 순서를 나열해 결과를 보여줌으로써 가능성이 높은 페이지들을 보여주게 됩니다.

이 페이지랭크는 Google 검색엔진의 핵심 알고리즘입니다. 대학원생이였던 세르게이 브린과 래리 페이지가 쓴 논문(The Anatomy of a Large-Scale Hypertextual Web Search Engine) 이 Google 의 시작점이였기에 꽤 유명한 알고리즘이기도 한데요.

이 링크에서 한 문단을 인용하자면

Academic citation literature has been applied to the web, largely by counting citations or backlinks to a given page. This gives some approximation of a page’s importance or quality. PageRank extends this idea by not counting links from all pages equally, and by normalizing by the number of links on a page.

다른 페이지에서 오는 링크를 동일한 비중으로 카운트 하지말고, 페이지에 걸린 링크 숫자를 Normalize 하는 방식을 사용한다 라고 적혀있습니다.

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

우선 A라는 페이지의 Page Rank 를 구하는 수식을 가져와 봤습니다. 용어부터 살펴보면 다음과 같아요.

- PR : Page Rank

- d : Damping Factor

- T : Page of indicate to A

- C : Count

Damping Factor 는 논문에 따르면, 자유롭게 웹서핑 하는 사람이 페이지에 만족하지 못하고 다른 페이지로 가는 링크를 클릭할 확률로 0과 1사이 값을 가집니다. d 가 1일 경우 (1-d) 는 0이고, 뒤 수식인 d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) 가 PageRank가 됩니다. 반대로 d 가 0일 경우 d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) 가 0이 되고 PageRank 는 1이 됩니다. 그러니 d가 0일 경우는 항상 PageRank 가 1의 값을 가지기 때문에 의미가 없어요. 그래서 d는 실험을 통해 임의의 값으로 정해지는데 논문에선 0.85로 설정해놓았다고 합니다. 즉, damping factor 가 1이면 무한하게 웹서핑을 한다는 것이고 0이면 처음 방문한 페이지에 만족해 더이상의 클릭이 일어나지 않는 것입니다.

다시 수식을 살펴봅시다. 일단 A라는 페이지에 대한 PageRank 는 A라는 페이지를 가리키는 페이지들의 PageRank 들의 합입니다.

그런데 각 PageRank 의 T 값을 Count 한 것으로 나누는 걸 볼 수 있는데, 이건 해당 페이지에 랭크된 다른 모든 페이지들을 카운드 하는 걸 의미합니다. 다시말해 다른페이지에 링크를 여러개 걸어두었고 A 도 그중 하나라면 해당 페이지에서 얻는 값은 작아지는 것입니다.

또 논문에 의하면, 모든 페이지의 PageRank 합산값은 1이 되어야 한다고 하지만, 이 수식에 따르면 그렇게 될 수 없습니다. d 가 0이라 가정하면 PR(A)는 1이 되고 모든 페이지의 PageRank 는 1이 되니 합산값은 1이 아닌 모든 페이지 수인 N이 되기 때문입니다.

위키피디아에 따르면, 세르게이와 래리가 논문에서 실수를 한 것 같다면서, 아래의 수정된 수식을 제공하고 있습니다.

PR(A) = (1-d)/N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

쉽게 설명한 예시도 위키피디아에서 찾아볼 수 있는데요. 예를 들어 A, B, C, D 라는 4개의 페이지가 있고 B, C, D는 A 링크를 가지고 있다 가정해봅시다. 그리고 B, C, D PageRank 값이 0.25 라 가정하면 A의 PageRank 는 PR(B) + PR(C) + PR(D) = 0.75 입니다.

그럼 만약 B가 A, C 링크를 가지고 C가 A 링크를 가지고 D가 A, B, C 링크를 가진다면

페이지	링크
B	A, C
C	A
D	A, B, C

PR(A) = PR(B) / 2 + PR(C) / 1 + PR(D) / 3 = 0.125 + 0.25 + 0.083 = 0.458 입니다.

이런식으로 PageRank 를 계산해서 계속 내려가다보면 끝이 없으니 조건을 걸어 반복을 종료하게 되고 그렇기에 이는 재귀 알고리즘으로 분류됩니다.

즉, 링크가 많이 걸릴 수록 PageRank 값이 높아져 키워드 검색 시 상단에 뜰 가능성이 높아진다는 말이네요.

import numpy as np

def pagerank(M, d: float = 0.85):
    """PageRank algorithm with explicit number of iterations. Returns ranking of nodes (pages) in the adjacency matrix.

    Parameters
    ----------
    M : numpy array
        adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j'
        sum(i, M_i,j) = 1
    d : float, optional
        damping factor, by default 0.85

    Returns
    -------
    numpy array
        a vector of ranks such that v_i is the i-th rank from [0, 1],

    """
    N = M.shape[1]
    w = np.ones(N) / N
    M_hat = d * M
    v = M_hat @ w + (1 - d)
    while(np.linalg.norm(w - v) >= 1e-10):
        w = v
        v = M_hat @ w + (1 - d)
    return v

M = np.array([[0, 0, 0, 0],
              [0, 0, 0, 0],
              [1, 0.5, 0, 0],
              [0, 0.5, 1, 0]])
v = pagerank(M, 0.85)

이 코드는 PageRank 알고리즘을 구현한 것으로, 각 노드(페이지)의 순위를 계산하는데요. PageRank는 주어진 인접 행렬 MM을 사용하여 각 노드가 다른 노드에 주는 중요도를 반복적으로 계산하여 안정적인 순위를 찾는 알고리즘입니다. 시간 될 때 분석해보면 좋을 것 같네요.

참고자료

https://en.wikipedia.org/wiki/PageRank

http://infolab.stanford.edu/~backrub/google.html

https://sungmooncho.com/2012/08/26/pagerank/