Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 구현하는 페이지랭크(PageRank) 알고리즘 완벽 가이드

페이지랭크(PageRank) 알고리즘은 웹 페이지의 중요도를 평가하는 대표적인 알고리즘으로, 구글 검색 엔진의 초기 핵심 기술로도 유명합니다. 이 글에서는 페이지랭크의 기본 개념과 함께 파이썬을 이용한 실제 구현 방법을 단계별로 살펴봅니다.

페이지랭크란 무엇인가?

웹은 하나의 유향 그래프(Directed Graph)로 모델링할 수 있습니다. 유향 그래프는 노드(node)와 연결(edge)이라는 두 가지 요소로 구성되는데, 여기서 각 웹 페이지는 노드에 해당하고, 페이지 사이의 하이퍼링크는 연결에 해당합니다.

페이지랭크는 이러한 링크 구조를 분석하여 각 페이지의 상대적 중요도를 수치화합니다. 페이지랭크 값은 확률로 정의되기 때문에 항상 0과 1 사이의 값을 가지며, 전체 페이지의 랭크 값을 모두 더하면 1이 됩니다.

페이지랭크의 핵심 원리

그래프에서 특정 노드의 페이지랭크 값은 해당 노드로 연결되어 있는 다른 모든 노드들의 페이지랭크 값에 의해 결정됩니다. 즉, 내 페이지로 들어오는 링크를 많이 가진 페이지일수록, 그리고 그 링크를 보낸 페이지 자체가 중요할수록 내 페이지의 랭크도 높아집니다.

문제는 이 값들이 서로 순환적으로 영향을 주고받는다는 점입니다. 이를 해결하기 위해 페이지랭크에서는 수렴 반복법(converging iterative method)을 사용합니다. 초기값을 균등하게 설정한 뒤, 랭크 값이 더 이상 변하지 않을 때까지(수렴할 때까지) 행렬 곱셈을 반복하면서 값을 갱신하는 방식입니다.

파이썬 구현 코드

다음 예제는 3개의 페이지로 구성된 작은 그래프에 대해 페이지랭크를 계산하는 코드입니다. 감쇠 계수(damping factor) β는 0.7로 설정했으며, 넘파이(numpy) 행렬 연산을 활용해 반복 계산을 수행합니다.

import numpy as np
from fractions import Fraction

def display_format(my_vector, my_decimal):
    return np.round((my_vector).astype(float), decimals=my_decimal)

my_dp = Fraction(1, 3)   # 초기 랭크값: 1/3씩 균등 분배
Mat = np.matrix([[0, 0, 1],
                 [Fraction(1, 2), 0, 0],
                 [Fraction(1, 2), 1, 0]])

# 텔레포트(무작위 점프) 행렬
Ex = np.zeros((3, 3))
Ex[:] = my_dp

beta = 0.7
Al = beta * Mat + ((1 - beta) * Ex)

r = np.matrix([my_dp, my_dp, my_dp])
r = np.transpose(r)
previous_r = r

for i in range(1, 100):
    r = Al * r
    print(display_format(r, 3))
    if (previous_r == r).all():   # 값이 수렴하면 반복 종료
        break
    previous_r = r

print("Final:\n", display_format(r, 3))
print("sum", np.sum(r))

실행 결과

반복이 진행될수록 랭크 값이 조금씩 변동되다가, 일정 횟수 이후에는 더 이상 변하지 않고 안정됩니다. 실제 출력 초반부와 최종 결과는 다음과 같습니다.

[[0.333]
 [0.217]
 [0.45 ]]
[[0.415]
 [0.217]
 [0.368]]
[[0.358]
 [0.245]
 [0.397]]
...
[[0.375]
 [0.231]
 [0.393]]

Final:
[[0.375]
 [0.231]
 [0.393]]
sum 0.9999999999999951

결과 해석

최종적으로 세 페이지의 랭크 값은 각각 약 0.375, 0.231, 0.393으로 수렴했습니다. 세 값의 합이 거의 정확히 1인 것을 확인할 수 있으며, 이는 페이지랭크가 확률 분포로 해석된다는 점을 잘 보여줍니다. 세 번째 페이지가 가장 높은 값을 가지는데, 이는 그래프 구조상 다른 페이지들로부터 더 많은 링크 가중치를 받기 때문입니다.

이처럼 페이지랭크는 단순한 행렬 연산만으로도 웹 전체의 링크 구조에서 각 페이지의 상대적 중요도를 효과적으로 계산할 수 있는 강력한 알고리즘입니다. 노드 수가 늘어나더라도 동일한 원리를 적용할 수 있으며, 희소 행렬(sparse matrix) 기법을 함께 사용하면 대규모 그래프에도 효율적으로 확장할 수 있습니다.