Graph (python networkX) Metric 정리

centrality

• centrality란 네트워크 상에서 중요한 노드를 찾기 위한 일종의 metric 으로 확인
• 밀도의 개념 : node가 n개 주어졌을때 방향을 무시한 총 그을 수 있는 edge수는 n(n-1)/2 이다. 전체 그을수 있는 edge수 중에 해당 node에 들어온 edge수를 기반으로 밀도를 구할 수 있음

degree centrality

• degree centrality는 각 node별로 직접 연결된 edge 수를 고려함 -> 해당 node를 통해야 연결되게 되는 것. 즉 해당 노드가 가진 영향력을 확인할 수 있음
• 밀도의 개념이라고 생각하면 됨

weighted degree centrality

• 노드와 노드를 잇는 edge의 weight는 모두 다르게 설정할 수 있다. 예를 들어 재화의 이동을 예로 들면 100원을 보내는 것과 100만원을 보내는 것은 같지 않다.
• 따라서 서로 다른 weight를 고려하는 것이 필요하다

closeness centrality

• closeness centrality는 네트워크의 모든 node로부터 얼마나 가깝게 위치해있는지를 고려하여 centrality를 계산한다.
• 즉 가장 short path를 기준으로 얼마나 distance가 되냐를 고려함
• closeness centrality를 계산할 때는 distance를 고려해야 하고, 우리가 일반적으로 표현한 weight와는 다름
• distance는 중요할수록 낮아야 하며, 해당 edge의 빈도가 높을 수록 이 distance를 낮추는 것이 필요

betweeness centrality

• betweenness centrality는 네트워크의 모든 노드 쌍 간의 shortest path가 해당 노드를 지나는지를 고려한 centrality
• 만약 모든 노드 페어의 shortest path가 node a를 지난다면 node a의 betweenness centrality는 높음
• betweeness centrality가 중요한 이유는 이 값은 전체 네트워크의 흐름을 제어하며, 해당 노드가 없어질 경우, 전체 네트워크의 흐름 자체에 영향을 받게 됨

eigenvector centrality and pagerank

• 흔히 google의 pagerank로 해당 centrality를 말한다.  강한 놈들이 나와 많이 연결되어 있을 수록 내 eigenvector centrality는 높아진다

The eigenvector calculation is done by the power iteration method and has no guarantee of convergence. The iteration will stop after max_iter iterations or an error tolerance of number_of_nodes(G)*tol has been reached. The PageRank algorithm was designed for directed graphs but this algorithm does not check if the input graph is directed and will execute on undirected graphs by converting each edge in the directed graph to two edges.

• eigenvector centrality는 수렴하지 않는 경우가 있고 이 경우 에러가 발생된다는 것.
• pagerank의 경우는 수렴한다는 것 정도가 미묘한 차이라고 할 수 있다. 단, pagerank는 원래 웹을 분석하려고 나왔기 때문에, directed network를 기본으로 가정하고 진행한다. 그렇지 않을 경우 임의로 undirected network를 변환해서 하는데, 어쩌면 당연하지만, 이런 네트워크에서는 수렴하는 것이 쉽지 않다

 

neworkX는 그래프의 모양을 layouts을 통해 지정 가능

layouts = {'spring': nx.spring_layout(G), 
           'spectral':nx.spectral_layout(G), 
           'shell':nx.shell_layout(G), 
           'fruchterman_reingold':nx.layout.fruchterman_reingold_layout(G), 
           'kamada_kawai':nx.kamada_kawai_layout(G), 
           'random':nx.random_layout(G)
          }

betweeness centrality를 이용한 그래프 코드 예시

import pandas as pd
import matplotlib.pyplot as plt

import networkx as nx


G_asymmetric = nx.DiGraph()
for tup in df[['seller','buyer','payout']].itertuples():
    G_asymmetric.add_edge(tup.buyer,tup.seller, weight=tup.payout)
    
    
pos = nx.spring_layout(G_asymmetric)
betCent = nx.betweenness_centrality(G_asymmetric, normalized=True, endpoints=True)
node_color = [500.0 * G_asymmetric.degree(v) for v in G_asymmetric]
node_size =  [v * 70000 for v in betCent.values()]
plt.figure(figsize=(20,20))

nx.draw_networkx(G_asymmetric, pos=pos, with_labels=True,
                 node_color=node_color,
                 node_size=node_size,font_size=8)

# nx.draw_networkx_labels(G_asymmetric,pos,font_family=font_name,font_size=7)

plt.axis('off')

[네트워크 예시]

https://frhyme.github.io/python-lib/network-centrality/

networkx를 이용하여 기본적인 centrality 분석하기