페이지랭크(PageRank)

검색어가 들어간 페이지가 수백만 개라면 무엇을 먼저 보여 줘야 할까요? 1998년 미국 스탠퍼드 대학교의 대학원생으로 뒤에 구글을 세운 래리 페이지와 세르게이 브린은 링크를 일종의 추천으로 보았습니다. 많이 추천받은 페이지가 중요하고, 중요한 페이지의 추천은 더 무겁습니다. 중요도를 중요도로 정의하니 제자리를 맴도는 말 같지만, 무작위 산책자를 떠올리면 깔끔하게 풀립니다.

산책자는 매 걸음 확률⁠(probability)⁠ $d$로 지금 페이지의 링크 가운데 하나를 똑같은 확률로 골라 따라갑니다. 나머지 확률 $1-d$로는 지루해져서 모든 페이지 가운데 아무 곳으로나 순간이동하고, 나가는 링크가 없는 페이지에서는 늘 순간이동합니다. 링크를 따라갈 확률 d를 감쇠 계수⁠(damping factor)⁠라고 부릅니다. 다음 위치가 지금 위치에만 달려 있으니 이것은 링크 그래프 위의 무작위 행보⁠(random walk)⁠, 곧 마르코프 연쇄⁠(Markov chain)⁠입니다. 오래 걸은 뒤 산책자가 각 페이지에 있을 확률이 그 페이지의 페이지랭크입니다. d가 1보다 작으면 순간이동 덕분에 이 확률은 어디서 출발하든 같은 값으로 다가갑니다.

페이지 두 개를 차례로 누르면 첫째에서 둘째로 가는 링크가 생기거나 없어집니다. 감쇠 계수는 $d =$ 입니다. 페이지가 n개일 때 벡터⁠(vector)⁠ r의 i번째 성분은 산책자가 페이지 i에 있을 확률입니다. 전이 행렬⁠(transition matrix)⁠ M은 (i, j) 성분이 '페이지 j에서 링크를 따라 페이지 i로 갈 확률'인 행렬입니다. j에서 나가는 링크가 ℓ개이고 그중 하나가 i로 가면 1/ℓ, 아니면 0이며, 나가는 링크가 없는 j의 열은 모두 1/n입니다. 모든 페이지를 $1/n$에서 시작해 한 걸음마다 $r \leftarrow \tfrac{1-d}{n}\mathbf 1 + dMr$을 계산합니다. 첫째 항은 순간이동으로 각 페이지에 떨어질 확률, 둘째 항은 링크를 따라 들어올 확률입니다($\mathbf 1$은 성분이 모두 1인 벡터). 지금 $k =$ 걸음째입니다. 한 걸음 처음부터

막대가 멈추는 곳(점선) $r = Gr$를 만족합니다. 여기서 $G = dM + \tfrac{1-d}{n}\mathbf{1}\mathbf{1}^\top$를 구글 행렬이라 부릅니다(확률들의 합이 1이므로 위의 한 걸음은 곧 G를 곱하는 것입니다). G를 곱해도 변하지 않는 벡터, 곧 G의 고유값 1에 대한 고유벡터가 페이지랭크입니다. 같은 벡터를 연립일차방정식⁠(system of linear equations)⁠ $(I - dM)\,r = \tfrac{1-d}{n}\mathbf 1$의 해로 구할 수도 있지만, 페이지가 수십억 개일 때는 행렬⁠(matrix)⁠과 벡터의 곱만 되풀이하는 이 거듭제곱법⁠(power iteration)⁠이 가장 실용적입니다.

얼마나 빨리 수렴⁠(convergence)⁠할까요? 성분별 차이의 절댓값⁠(absolute value)⁠을 모두 더해 오차를 재면, 오차는 한 걸음마다 d배 이하로 줄어듭니다. 지금 오차는 이고, 보장된 상한⁠(upper bound)⁠ $d^k \times$(처음 오차)는 입니다. 까닭은 간단합니다. 두 확률 벡터의 차이에 한 걸음을 적용하면 순간이동 항은 서로 지워지고 $dM$만 남습니다. M은 확률을 여기서 저기로 옮기기만 하므로 차이의 절댓값 합을 늘리지 못하고, 결국 d배 이하가 됩니다. 고유값으로 말하면 G의 고유값 가운데 1이 아닌 것은 크기가 모두 d 이하입니다(대각화⁠, diagonalization⁠). 식을 풀어 쓰면 $r = \tfrac{1-d}{n}\sum_{k \ge 0} d^k M^k \mathbf 1$, 곧 길이 k인 링크 사슬마다 $d^k$의 무게를 주는 등비급수⁠(geometric series)⁠입니다.

d가 0이면 링크는 아무 상관이 없고 모두 똑같이 $1/n$입니다. d가 1에 가까울수록 링크 구조만 반영하지만 수렴이 느려지고, 나가는 링크가 무리 밖으로 없는 페이지 묶음에 산책자가 갇혀 순위를 독차지할 수 있습니다. 원 논문은 d = 0.85를 썼습니다.

이어지는 곳. 같은 생각이 논문 인용망에서 영향력 있는 논문을 찾거나 사회 연결망에서 중심 인물을 찾는 데 쓰입니다. 거듭제곱법이 몇십 걸음이면 자리를 잡는 것은 링크 구조와 상관없이 순간이동 덕분입니다($0.85^{50} \approx 0.0003$). 웹이 좁은 세상⁠(small world)⁠이라는 것은 이와 별개로, 링크 몇 번이면 대부분의 페이지 사이를 오갈 수 있다는 관찰입니다. 가장 큰 고유값의 고유벡터를 곱셈의 반복으로 찾는 거듭제곱법은 주성분 분석⁠(principal component analysis)⁠에서도 쓸 수 있습니다. 데이터가 가장 넓게 퍼진 방향이 바로 공분산 행렬⁠(covariance matrix)⁠의 가장 큰 고유값에 대한 고유벡터이기 때문입니다.