[Search Engine] PageRank

PageRank 알고리즘은 세르게이 브린과 래리 페이지가 쓴 논문 <The Anatomy of a Large-Scale Hypertextual Web Search Engine> 에서 처음 나왔다. 앞선 포스트에서 구글은 검색엔진을 구현하는 데 수백여 가지의 알고리즘을 사용하지만 근본적인 알고리즘은 PageRank라고 할 수 있다.

 

 

PageRank

PageRank 알고리즘은 페이지 간 중요도를 웹페이지 간 연결관계에 기반한다. 

학술지 논문을 생각해보자. 논문이 공신력이 있고 전문성과 신뢰도가 높을 수록 그 주제에 관련된 타 논문들에서의 인용횟수는 증가할것이다. 검색 엔진도 마찬가지로, 검색 결과 나타난 페이지들에 대해 특정 페이지에 대한 링크가 많이 들어가게 된다면 그 페이지는 검색하고자 하는 주제에 핵심적인 내용을 담고 있다고 할 수 있다.

 

주요 내용

PageRank 식

여기서 PR은 PageRank를, d는 Damping Factor, C는 괄호 내 페이지가 가지고 있는 링크의 총 개수이다.

이렇게 구한 전체 페이지의 PageRank의 합산 값은 1이 된다. 이 식을 풀어서 설명하면, 어떤 페이지 A의 페이지 랭크는 그 페이지를 인용하고 있는 다른 페이지 T1, T2, T3, ... 가 가진 페이지 랭크를 정규화시킨 값의 합을 구하는 것이라고 할 수 있다. 정규화하는 이유는 T1의 PR이 높더라도 그 페이지에서 링크를 수천개 달아놓았다면 그 페이지가 기여하는 비중은 낮아지기에 이를 PR에 반영하기 위함이다.

 

Damping factor

damping factor는 0에서 1사이의 값으로 이루어지며, 마구잡이로 웹서핑 하는 사람이 그 페이지에 만족 못하고 타 페이지로 가는 링크를 클릭할 확률을 의미한다. damping factor가 1이면 만족하지 못하고 무한히 링크를 클릭하는 것을 의미하며, 0이면 처음 방문한 페이지에서 만족해 검색을 그만하는 것을 의미한다. 보통 0.85로 가정하고 계산한다.

 

지금부터 웹페이지를 노드(Node), 웹페이지 간 연결을 엣지(Edge)로 표현하겠다. 위 그림과 같은 그림을 어떻게 행렬식으로 구현할 수 있을까?

 

1. Adjacent Matrix

단순히 연결과 미연결을 0과 1로 표현하여, 열마다 특정 노드의 연결관계를 파악할 수 있다. 이 때 열벡터의 모든 값이 0인 노드는 Dangling Node라고 한다.

 

2. Stochastic Matrix

다음 방법은 확률 행렬로, 앞선 Adjacent Matrix에 n승을 표현해 몇번 링크를 거쳤는지까지 구현하는 행렬이다.

H는 Adjacent Matrix의 열벡터마다 각 노드에 연결된 엣지의 총 개수로 나눈 행렬이다. 여기에 추가적인 수식을 거쳐서, Dangling Node의 값이 0이 아닌 1 / (전체 페이지의 수) 의 값을 가진 열벡터로 표현을 하게 만든다. 어쨌든 다른 페이지에서 인용은 안됐으나 총합이 1이 되도록 만든 것이다. 

 

3. Google Matrix

Google 행렬은 damping factor와 S를 행렬곱하고, (1-d)와 1 행렬을 전체 페이지의 수로 나눈 행렬을 곱해 더한 값이다. 이렇게 구한 G에서 페이지 링크를 구할 수 있다.