페이지랭크(PageRank) 알고리즘 쉽게 이해하기
1996년 콘텐츠 기반 검색의 한계를 극복하기 위해 세르게이 브린과 래리 페이지가 개발한 구글의 핵심 알고리즘 페이지랭크를 소개하는 글입니다. 페이지랭크는 각 페이지가 링크를 통해 평판을 다른 페이지에 전달하고, 받은 평판의 합으로 중요도를 계산하는 방식으로, 간단한 파이썬 코드 몇 줄로 구현할 수 있을 만큼 직관적인 원리입니다.
1996년으로 시간을 거슬러 갔다고 상상해보자. 당신은 당시 주류 검색 엔진이었던 알타비스타(AltaVista)에 좌절하고 있다. 알타비스타는 주로 콘텐츠 기반 검색을 수행했다(예를 들어 "호텔"을 검색하면 단어만 일치하는 "닭을 위한 호텔"이라는 글을 보여줄 수 있었다). 더 나은 방법이 있어야 하지 않을까? 물론 지금 와서 돌아보면 그렇다. 세르게이 브린과 래리 페이지는 바로 이 알고리즘, 즉 페이지랭크(PageRank)를 고안해냈고, 이는 구글을 가정의 이름으로 만들고 막대한 부를 안겨준 핵심 알고리즘 중 하나였다.
세르게이와 래리는 둘 다 스탠퍼드 대학원생이었으니, 이런 훌륭한 알고리즘을 만든 것이 놀랍지 않게 느껴질 수도 있다. 하지만 질문은 이것이다. 당신도 같은 것을 우연히 발견할 수 있었을까? 나는 그렇다고 생각한다.
페이지랭크는 본질적으로 다음과 같은 기본 원칙을 담고 있다:
- 모든 페이지는 "랭크(순위)" 또는 평판을 가진다.
- 페이지는 다른 페이지에 링크를 걸어 자신의 "랭크"를 공유함으로써 일종의 승인 도장을 찍어주는 것이다.
- 페이지의 총 랭크/평판은 어떤 최소치에, 자신을 링크한 이웃들로부터 받는 모든 평판을 더한 값이다.
그게 전부다.
구체적인 예시로 확실히 이해해보자. 어떤 페이지(예를 들어 BBC 뉴스)의 평판이 50이고 5개의 서로 다른 페이지에 링크를 걸고 있다고 하자. 이 페이지가 자신의 평판 중 80%(40)를 링크를 건 페이지들에게 분배한다고 하자(나머지는 모든 페이지에 균등하게 분배된다). 그러면 링크를 받은 각 페이지는 BBC로부터 40/5 = 8점을 받게 된다.
이것을 수행하는 아주 짧은(그리고 놀랍도록 읽기 쉬운) 파이썬 프로그램을 직접 만들어볼 수 있다:
incoming[n]은 n으로 들어오는 모든 노드를 담고 있다
outgoing[n]은 n에서 나가는 모든 노드를 담고 있다
페이지는 자신의 평판 중 damping%를 이웃들에게 분배한다.
(1-damping)%는 모든 페이지에 균등하게 분배된다.
def pagerank(incoming, outgoing, damping=.85, tolerance=1e-10): n = len(incoming) # 전체 페이지 수 rank = [1 / n] * n # 시작 랭크. 모두 동일. minimum_rank = (1 - damping) / n # 임의 점프(random jump)로 인해 # 모든 페이지는 최소한 이 정도는 받는다
while True:
old = rank.copy()
for page, neighbors in enumerate(incoming):
# 링크를 건 페이지(자신의 랭크를 모든 링크 대상에게
# 균등하게 분배하는)로부터 이만큼을 받는다
acquired = sum(
old[neighbor] / len(outgoing[neighbor])
for neighbor in neighbors
)
rank[page] = minimum_rank + damping * acquired
# 알고리즘이 수렴할 때까지 반복
if max(abs(a - b) for a, b in zip(rank, old)) < tolerance:
return rank
그리고 끝이다. 이 갱신을 여러 번 실행하면 결국 각 페이지의 랭크를 얻게 되는데, 이것이 기본적으로 그 페이지가 얼마나 중요한지를 말해준다.
물론 여기서 몇 가지 가정(예를 들어 링크가 없는 매달린 노드(dangling node)가 없다는 것 등)이 있지만, 이런 것들은 단순한 부수적인 처리 사항일 뿐이며, 이제 여러분은 이 알고리즘의 핵심을 알게 되었다. 축하한다. 만약 1996년으로 돌아가게 된다면, 억만장자가 되기 위해 무엇을 해야 하는지 이제 알고 있는 것이다!