PageRank

PageRank

 

PargeRank는 구글의 창업자인 Larry Page와 Sergey Brin이 논문을 통해 발표한 이론으로 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾기 위한 방법이다.

 

웹은 Vertex인 웹페이지와 Edge인 하이퍼링크로 구성된 거대한 방향성을 가지는 그래프로 볼 수 있다.

 

페이지랭크의 핵심아이디어는 투표로 투표를 통해 사용자 키워드와 관련성이 높으며 신뢰할 수 있는 웹페이지를 찾는다.

In Degree가 크다는 것은 들어오는 간선이 많다는 것이고 신뢰할 수 있다는 이론이 바탕이 된다.

 

단지 In Degree로 신뢰도를 평가하면 악용의 소지가 있다. 

투표에 가중치를 부여하여 이를 해결한다.

 

PageRank Score

 

페이지랭크 점수는 웹페이지의 관련성 및 신뢰도의 척도로 웹페이지의 페이지랭크 점수만큼 투표에 가중치가 주어진다.

각 웹페이지는 각각의 나가는 이웃에 대해 (자신의 페이지랭크 점수 / 나가는 이웃의 수 (Out Degree))만큼 가중치로 투표를 한다.

 

 PageRank Voting

$r_{v}$는 Vertex v의 페이지랭크 점수를 의미한다.

Vertex j는 j의 PageRank Score $r_{j}$를 3으로 나눈 가중치로 j의 나가는 이웃 3명에게 각각 투표한다.

 

Vertex j가 받은 투표의 가중치는 Vertex i와 k로부터 $r_{i}/3, r_{k}/4$씩 받아서 $r_{j}=r_{i}/3+r_{k}/4$가 된다.

 

PageRank Score Formula

 

Random Walk Perspective

투표뿐만 아닌 랜덤워크의 관점으로 페이지랭크를 정의할 수 있다.

랜덤워크로 웹을 서핑하는 주체 웹 서퍼를 가정한다.

 

웹 서퍼가 t번째 방문한 웹페이지가 i이 확률을 $p_{i}(t)$라고 하자.

p(t)는 길이가 그래프에 속한 모든 Vertex 수(전체 웹페이지 수)와 같은 확률분포 벡터가 된다.

따라서 아래와 같은 수식이 성립한다.

 

Random-walk perspective PageRank Score

 

웹 서퍼가 웹페이지 방문을 무한히 계속한다면 p(t)는 수렴하게 된다.

$p(t) = p(t+1) = p$이 되고 수렴한 확률 분포 p는 Stationary Distribution(정상 분포)라고 한다.

 

따라서 위처럼 수식의 변환이 가능하며 이는 투표 관점에서 설명한 PageRank Score 산출 공식과 같다.

 

PageRank Score Calculation

페이지랭크 점수는 Power Iteration(반복 곱)을 사용하여 계산한다.

 

1. 각 웹페이지 i의 페이지랭크 점수 $r_{i}^{0}$을 동일하게 (1/웹페이지 수)로 초기화한다.
2. 수식을 통해 각 웹페이지의 t 번째 페이지랭크 점수를 계산한다.
3. 페이지랭크 점수의 변화값인 delta가 설정한 값보다 작아졌으면 수렴하였다고 판단하고 종료한다.

 

PageRank Score Example

Problem & Solution

 

Spider Trap

위의 방식으로 계산한 페이지랭크 점수는 항상 수렴하지 않는다.

Spider Trap

위와 같이 들어오는 간선이 있으나 나가는 간선이 없는 집합인 스파이더 트랩에 의해 b와 c의 페이지랭크 점수는 수렴하지 못하고 진동하게 된다.

 

Dead End

Dead End

위와 같이 들어오는 간선은 있으나 나가는 간선이 없는 Dead End(막다른 정점)은 페이지랭크 점수가 합리적이지 못한 값으로 수렴하게 한다.

 

Dead End problem

 

Teleport

위의 문제들을 해결하기 위해 Teleport(순간이동)을 도입한다.

 

기존의 웹 서퍼의 행동은 다음과 같이 수정된다.

• 현재 웹페이지에 하이퍼링크가 없으면, 임의의 웹페이지로 순간이동 
• 현재 웹페이지에 하이퍼링크가 있다면, (1-Damping Factor)의 확률로 임의의 웹페이지로 순간이동
• 위의 경우가 아닐 경우, 하이퍼링크 중 하나를 균일 확률로 선택하여 이동

Damping Factor(감폭 비율) $\alpha$는 보통 0.8의 값을 사용한다.

 

순간이동을 적용하기 위해 각 막다른 정점(Dead End)에서 모든 다른 정점으로 가는 간선을 추가한다.

순간이동의 도입은 페이지랭크 점수 계산과정을 다음과 같이 수정한다.

 

Adjusted PageRank Score Formula

위의 식은 $\alpha$확률로 하이퍼링크를 통해 j에 도달, $1-\alpha$ 확률로 전체 정점 중 하나에서 순간이동을 통해 j에 도달함을 나타낸다.

 

PageRank Score

 

Code

 

def pagerank(
    graph: Graph_dict,
    damping_factor: float,
    maxiters: int,
    tol: float,
) -> Dict[int, float]:
    vec: DefaultDict[int, float] = defaultdict(float)  # Pagerank vector
    
    # Initialization
    N = len(graph._nodes)
    for node in graph._nodes:
        vec[node] = 1 / N
    
    nodes = graph._nodes
    preference = {k: 1 / len(nodes) for k in nodes}

    for itr in range(maxiters):
        
        # r_old in lecture : vec
        # r_new in lecture : vec_new
        vec_new: DefaultDict[int, float] = defaultdict(float)
        edges = graph.edges()

        for e in edges:
            src, dst = e
            vec_new[dst] += damping_factor * vec[src] / graph.out_degree(src)
        
        # S = Sigma(j){r_new[j]}
        S = sum(vec_new.values())

        # r_new = r_old + (1 - S) * preference
        for k, v in preference.items():
            vec_new[k] += (1 - S) * v

        #### Check the convergence ###

        # Stop the iteration if L1norm[PR(t) - PR(t-1)] < tol
        delta: float = 0.0
        delta = l1_distance(vec_new, vec)

        print(f"[Iter {itr}]\tDelta = {delta}")

        if delta < tol:
            break

        # r_old <- r_new
        vec = vec_new


    return dict(vec)
    
 #출처: Naver AI Boostcamp - 신기정 마스터 hw1

 

Reference

[1] L Page et al. (1999). "The PageRank Citation Ranking: Bringing Order to the Web". url

[2] Naver Connect Boostcamp AI-Tech 페이지랭크&전파 모델 (신기정 마스터)