페이지 랭크 알고리즘의 이해와 원리

개요

페이지 랭크(PageRank) 알고리즘은 웹페이지의 중요도를 평가하기 위해 구글의 창업자인 래리 페이지와 세르게이 브린이 개발한 알고리즘이다. 이 알고리즘은 웹페이지가 받는 링크의 수뿐만 아니라 링크의 질을 고려하여 페이지의 중요도를 산출한다. 페이지 랭크는 구글 검색 엔진의 핵심 기술로, 구글이 검색 시장에서 우위를 차지하는 데 결정적인 역할을 했다.

설명

페이지 랭크 알고리즘은 학술지 인용 방식을 웹에 적용한 개념이다. 기존에는 특정 페이지를 가리키는 링크(백링크)의 수를 단순히 세는 방식으로 페이지의 중요도를 평가했다. 그러나 페이지 랭크는 이러한 개념을 확장하여 모든 페이지의 링크가 동일한 가치를 갖는 것이 아니라, 링크를 제공하는 페이지의 중요도와 해당 페이지에서 나가는 총 링크 수를 고려하여 페이지의 중요도를 계산한다.

페이지 랭크의 기본 공식은 다음과 같다:

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

여기서:

• PR(A)는 페이지 A의 페이지 랭크 값
• PR(T1)부터 PR(Tn)은 페이지 A로 링크를 제공하는 페이지들의 페이지 랭크 값
• C(T1)부터 C(Tn)은 이들 페이지에서 나가는 총 링크 수
• d는 댐핑 팩터(Damping Factor)로, 일반적으로 0.85의 값을 사용

이 수식은 '어떤 페이지 A의 페이지 랭크는 그 페이지를 인용하고 있는 다른 페이지들이 가진 페이지 랭크를 정규화시킨 값의 합'으로 해석된다. 즉, 페이지 A의 중요도는 A를 가리키는 다른 페이지들의 중요도에 비례하지만, 그 페이지들이 가진 총 링크 수에 반비례한다.

특성

페이지 랭크 알고리즘의 주요 특성은 다음과 같다:

1. 재귀적 계산: 페이지 랭크는 재귀적으로 계산된다. 즉, 모든 페이지의 페이지 랭크를 계산하기 위해서는 해당 페이지를 가리키는, 그리고 이를 다시 가리키는 모든 페이지의 페이지 랭크를 알아야 한다.
2. 댐핑 팩터(Damping Factor): 댐핑 팩터는 '마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족하지 못하고 다른 페이지로 이동할 확률'을 의미한다. 일반적으로 0.85로 설정되며, 이는 사용자가 85%의 확률로 현재 페이지에서 다른 페이지로 이동한다는 것을 의미한다.
3. 정규화: 총 링크 수에 의한 정규화를 통해, 많은 링크를 가진 페이지의 '투표력'이 분산되도록 한다. 이는 링크 스팸(많은 링크를 무분별하게 추가하는 행위)을 방지하는 효과가 있다.
4. 수정된 수식: 위키피디아에 따르면, 원래 논문에서의 수식은 모든 페이지의 페이지 랭크 합이 1이 되지 않는 문제가 있었다. 이를 수정한 수식은 다음과 같다:

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

여기서 N은 전체 페이지 수를 의미한다.

예제

페이지 랭크의 계산 과정을 간단한 예로 설명하면 다음과 같다:

웹페이지 A를 가리키는 페이지가 T1, T2, T3, T4, T5의 다섯 개가 있다고 가정해 보자. 각 페이지의 페이지 랭크와 총 링크 수는 다음과 같다:

• T1: 페이지 랭크 = 0.1, 총 링크 수 = 5
• T2: 페이지 랭크 = 0.3, 총 링크 수 = 2
• T3: 페이지 랭크 = 0.05, 총 링크 수 = 1
• T4: 페이지 랭크 = 0.2, 총 링크 수 = 10
• T5: 페이지 랭크 = 0.3, 총 링크 수 = 3

A의 페이지 랭크를 계산하면:

PR(A) = 0.1/5 + 0.3/2 + 0.05/1 + 0.2/10 + 0.3/3 = 0.02 + 0.15 + 0.05 + 0.02 + 0.1 = 0.34

이 값은 댐핑 팩터를 고려하지 않은 단순화된 계산이다. 실제로는 댐핑 팩터를 적용해야 한다.

실제 웹에서는 수십억 개의 페이지가 서로 복잡하게 연결되어 있으므로, 페이지 랭크 계산은 반복적인 과정을 통해 수렴하는 값을 찾아내는 방식으로 이루어진다.

결론

페이지 랭크 알고리즘은 구글이 검색 엔진 시장에서 혁신을 일으킨 핵심 기술이다. 이 알고리즘은 단순히 링크의 수를 세는 것이 아니라, '영향력 있는 페이지가 인용할수록 페이지 랭크가 올라간다'는 근본적인 원칙을 적용함으로써 보다 관련성 높고 질 좋은 검색 결과를 제공할 수 있게 했다.

현재 구글의 검색 알고리즘은 페이지 랭크 외에도 수백 가지의 요소를 고려하는 훨씬 복잡한 시스템으로 발전했지만, 페이지 랭크의 기본 개념은 여전히 중요한 역할을 하고 있다. 페이지 랭크는 구글이 야후를 비롯한 경쟁자들을 제치고 검색 엔진의 대명사로 자리매김하는 데 결정적인 기여를 했다.

참고 문헌

1. '쉽게 설명한' 구글의 페이지 랭크 알고리즘: https://sungmooncho.com/2012/08/26/pagerank/
2. Wikipedia - PageRank: https://en.wikipedia.org/wiki/PageRank
3. The Anatomy of a Large-Scale Hypertextual Web Search Engine (원본 페이지 랭크 논문): http://infolab.stanford.edu/~backrub/google.html