PageRank는 인간의 관심도를 반영하여 웹 페이지를 객관적이고 기계적으로 평가하는 방법입니다. 웹 검색 엔진은 검색 경험이 부족한 일반 사용자뿐 아니라, 기존 랭킹 서비스를 조작하려는 악의적인 페이지와도 끊임없이 씨름해야 합니다. 특히 웹 페이지의 단순히 복제 가능한 속성(예: 키워드 빈도)만 세는 평가 방식은 조작에 쉽게 노출된다는 한계가 있습니다.
PageRank의 핵심 아이디어
PageRank의 목표는 웹의 하이퍼링크 구조를 활용하여 모든 웹 페이지에 대한 전역적 중요도 순위(global importance ranking)를 산출하는 것입니다. 이렇게 계산된 순위를 PageRank라고 부릅니다.
웹은 약 1억 5천만 개의 노드(웹 페이지)와 17억 개의 엣지(하이퍼링크)로 구성된 거대한 그래프로 모델링할 수 있습니다. 여기서 웹 페이지 A와 B가 페이지 C를 가리킨다면, A와 B를 C의 백링크(backlink)라고 합니다.
백링크가 순위를 결정하는 방식
일반적으로 링크를 많이 받은 페이지일수록 더 중요하다고 간주되며, 따라서 백링크 수가 많아집니다. 흥미로운 점은 중요한 백링크일수록 그 수는 오히려 적다는 것입니다.
예를 들어, Yahoo처럼 권위 있는 사이트로부터 백링크 하나를 받은 페이지는, 알려지지 않은 개인 사이트로부터 여러 개의 백링크를 받은 페이지보다 더 높은 순위를 받아야 합니다. 즉, 어떤 페이지의 랭크는 해당 페이지로 향하는 백링크들의 랭크 총합에 비례하여 커집니다.
간소화된 PageRank 수식
u, v를 웹 페이지라 하고, Bu를 u를 가리키는 페이지들의 집합, Nv를 v에서 나가는 링크의 수, c(<1)를 정규화 계수라고 하면, PageRank의 간단한 해석인 랭킹 R을 다음과 같이 표현할 수 있습니다.
R(u) = c × Σv∈Bu R(v) / Nv
이 식의 의미는 다음과 같습니다. 각 페이지의 랭크는 자신이 가리키는 페이지들에게 균등하게 분배되며, 그 랭크는 링크를 받는 페이지들의 랭크에 더해집니다. 이 방정식은 재귀적으로 정의되지만, 간소화된 형태에는 중요한 문제점이 존재합니다.
랭크 싱크(Rank Sink) 문제
두 웹 페이지가 서로만을 가리키고 다른 어느 페이지로도 링크하지 않으며, 제3의 페이지가 그중 하나를 가리키는 상황을 생각해 보겠습니다. 이 경우 반복 계산 과정에서 루프(loop)가 생성되어, 랭크가 해당 루프 안에 계속 축적되기만 할 뿐 외부로 전혀 흘러나가지 않게 됩니다. 이처럼 아웃링크(outedge)가 없는 그래프 구조에서 루프로 인해 발생하는 함정을 랭크 싱크(rank sink)라고 부릅니다.
PageRank 알고리즘의 실제 계산 과정
실제 PageRank 알고리즘은 다음 단계로 진행됩니다.
1. URL 변환 및 링크 저장
먼저 데이터베이스에 있는 모든 URL을 고유한 숫자(정수 ID)로 변환합니다. 다음으로 이 정수 ID를 사용해 웹 페이지를 식별하면서 각 하이퍼링크를 데이터베이스에 저장합니다.
2. 반복 계산 시작
링크 구조를 부모 ID 기준으로 정렬하고, 댕글링 링크(dangling link, 아웃링크가 없는 페이지로의 연결)를 제거한 후 반복 계산(iteration)을 시작합니다.
3. 수렴을 위한 최적화
수렴 속도를 높이려면 최적의 초기값 배정을 선택하는 것이 중요합니다. 현재 시점의 가중치는 메모리에 유지하고, 이전 시점의 가중치는 디스크에서 선형 시간으로 접근하여 비교합니다.
4. 댕글링 링크 복원 및 재계산
가중치가 수렴하면 제거했던 댕글링 링크를 다시 삽입하고 최종 순위를 재계산합니다. 이 계산 방식은 안정적으로 잘 작동하지만, 수렴 판정 기준을 완화하고 더 효율적인 최적화 기법을 함께 사용하면 처리 속도를 한층 더 끌어올릴 수 있습니다.