[Algorithm] What is the page rank?

1. Page rank 란?

Page rank란 페이지의 중요도를 웹페이지 간 연결 관계에 기반을 두고 측정한 지표이다. 

Figure 1.

Figure1 은 웹페이지들을 노드로 취급하고 화살표가 가르키는 방향은 해당 웹페이지에서 가르키는 쪽의 웹페이지 쪽으로 접근이 가능하다는 것을 표시하는 것이다. 또한 노드 안의 숫자는 각 웹페이지의 page rank를 의미한다. 또한 Page rank의 값이 클수록 해당 웹페이지의 중요도가 크다는 것을 의미한다. 

 

2. Page rank 알고리즘

 

Figure 2.

Figure2. 같은 경우 Pagerank를 MapReduce로 구현하였을 때의 pseudo 코드 이다. Map phase에서는 각 노드의 PageRank 값을 계산하여 node id와 Pagerank value를 Emit해준다. 그 후, Reduce phase에서 각 node id에 포함된 모든 Pagerank를 합산하여 새로운 pagerank를 구하여 Emit해준다.

 

Figure 3.

Figure 3에서는 MapReduce를 2번 Iteration 한 것을 보여주는 그림이다. 첫번째 그림을 가볍게 설명해보면 Pagerank를 5개의 node에 공평하게 0.2로 나누고, edge의 화살표에 따라 해당 노드의 pagerank value를 분배해줍니다. 그후 Reduce phase에서 edge(화살표)에 있는 값을 aggregate 한 후 다음 Iteration에 Emit 해주는 방법입니다.

 

3. My Review

이번 알고리즘은 뭔가 실제로도 사용했던 알고리즘을 실제 데이터를 갖고 사용해봐서 좋은 기회였다고 생각한다. 특히 이 알고리즘은 굉장히 단순하지만 각 Iteration마다 체계적이여서 각 phase가 납득이 잘 가는 알고리즘이였다. 하지만 현재 구글 검색엔진에는 사용되지 않는데 그 이유는 들어가는 간선은 있지만 나가는 간선은 없는 정점 집합인 Spider Trap에 의한 문제와 Dead End에 의한 문제로 Pagerank 그 자체를 사용해서 현재 검색엔진을 사용하고 있지는 않다고 한다.