페이지랭크 (PageRank) 원리

네트워크 그래프에서 노드의 중심성을 파악하고 계산하는 방법들을 살펴보았습니다.

• 연결중심성(Degree Centrality)과 근접중심성(Closeness Centrality)
• 매개중심성(Betweenness Centrality)

 

중심성을 파악하는 간단하고 효율적인 또 다른 방법으로

페이지랭크(PageRank)가 있습니다.

 

 

PageRank 페이지 랭크

• "하이퍼링크 네트워크 구조에서 웹페이지들의 중요성을 어떻게 측정할까"에 대한 고민으로 구글이 개발
• 핵심 개념 및 가정 : 중요한 노드들은 또다른 중요한 페이지로부터 많은 유입 링크를 가진다.
• 방향성을 가진 네트워크에 효과적
• 한 노드의 페이지랭크 점수는 다른 노드의 페이지랭크 점수에 의존적
  (따라서 여러번 반복적으로-순환적Circular으로- 계산하고 업데이트 해야함)

 

페이지랭크 계산원리

페이지랭크는 순환적으로 계산됩니다. k번의 주기를 돌릴 때마다 값이 조금씩 달라집니다.

첫번째 싸이클을 돌렸을때(k=1)의 페이지랭크값을 구해봅시다

• 전체 노드들의 페이지랭크 값 총합은 1이다. (맨 처음 각 노드의 페이지랭크값 = 1/n)
• 각 노드들은 자신을 가리키는 노드들로부터 페이지랭크 값을 받음
• 각 노드들은 자신이 가리키는 노드들에게 자신의 페이지랭크 값을 분배함

이 과정을 반복하다보면 대부분의 네트웨크에서 페이지랭크값은 수렴합니다.

위와 같은 과정을 무한히 반복하면 수렴값을 얻을 수 있습니다.

 

즉, 페이지 랭크의 값은 임의로 k번 움직일 때 각 노드에 머무르게 될 확률을 의미합니다.

 

 

본 게시물은 Coursera의 Applied Social Network Analysis in Python(by Daniel Romero)를 통해 자습하며 작성한 게시물입니다.