[NetworkX] 페이지랭크 (PageRank)

지난 글에서는 페이지랭크의 원리를 간략하게 살펴보았습니다.

페이지랭크 (PageRank) 원리

이번에는 NetworkX로 페이지랭크를 구현, 계산해 보겠습니다.

 

PageRank 페이지 랭크

import networkx as nx

edges = [('A','B'),('B','C'),('B','D'),('C','B'),('D','A'),('D','C'),('D','E'),('E','A')]

G = nx.DiGraph()
G.add_edges_from(edges)

# 네트워크 그리기
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, with_labels=True)

페이지랭크 계산

pr = nx.pagerank(G,alpha=1)
print(pr)

# 결과
{'A': 0.12499985859863202,
 'B': 0.37500069212248505,
 'C': 0.2499997246394413,
 'D': 0.18749944927888273,
 'E': 0.06250027536055858}

이전 글에서 계산한 값과 상당히 유사한 값이 도출되었습니다.

 

그런데 새로 소개할 파라미터로 alpha가 있습니다.

 

알파α

지난 페이지랭크의 원리 글에서 설명하지는 않았지만,

페이지 랭크는 치명적인 문제를 가지고 있습니다.

고립이 발생하면 한도끝도 없다는 점입니다.

위의 그래프에서, 페이지랭크 계산을 무한히 진행한다면 (k가 무한으로 발산한다면) 어떨까요?

F, G 노드의 순환에 고립이 발생하고, 나머지 노드들에 다다를 가능성은 끝도 없이 낮아집니다.

 

즉, F,G의 페이지랭크 값은 각각 0.5에 수렴하고,

나머지 A~E의 페이지랭크 값은 0에 수렴한다는 뜻입니다.

 

때문에 새로운 파라미터인 알파α 를 도입한 것입니다.

• α : 그대로 선택 가능한 경로로 진행할 확률
• 1-α : 경로랑은 전혀 무관하게 랜덤하게 아무 노드로 jump할 확률

일반적으로 α=0.8 ~ α=0.9 로 지정한다고 하며,

NetworkX에서의 default값은 0.85 입니다.

# A~E까지만 있는 그래프
pr = nx.pagerank(G)  # alpha=0.85
print(pr)

# 결과
{'A': 0.15035141786968964,
 'B': 0.35519316255962585,
 'C': 0.2322277097853423,
 'D': 0.18095642215666966,
 'E': 0.08127128762867264}
 
 
 # F, G 노드도 있는 그래프
 pr = nx.pagerank(G,alpha=1,max_iter=1000000)  # max_iter=k : 페이지 랭크를 k번 계산 
 print(pr)
 
 # 결과
 {'A': 1.655364605146791e-06,
 'B': 5.2343789363186666e-06,
 'C': 2.408878972558538e-06,
 'D': 1.685351915755418e-06,
 'E': 7.235270568031201e-07,
 'F': 0.49999414624925675,
 'G': 0.49999414624925675}