[NetworkX] 매개중심성 (Betweenness Centrality)

지난 글에는 연결중심성(Degree Centrality)과 근접중심성(Closeness Centrality)를 살펴보았습니다.

[NetworkX] 연결중심성, 근접중심성 (Degree Centrality, Closeness Centrality)

또 어떤 기준으로 중요한 노드를 뽑을 수 있을지

똑같은 그래프를 예시로 실습해 보겠습니다.

import networkx as nx
G = nx.karate_club_graph()
G = nx.convert_node_labels_to_integers(G,first_label=1)

 

 

 

Betweenness Centrality 매개 중심성 (사이중심성)

• 새로운 친구를 소개받고 싶을 때 꼭 거쳐야하는 사람이라면
• = 일종의 허브(hub) 역할을 한다면

중요한 노드 아닐까요?

 

서로 다른 노드를 연결함에 얼마나 역할을 하는가를 매개중심성(Betweenness Centrality)이라고 부릅니다.

매개 중심성이 높은 노드를 기준으로 중요한 노드를 고른다면,

가장 중요한 노드 5개는 1, 34, 33 3, 32가 될겁니다.

btwnCent = nx.betweenness_centrality(G, normalized=True, endpoints=False)
# btwnCent = {1: 0.43763528138528146, 2: 0.053936688311688304, 3: 0.14365680615680618, ... }

sorted_nodes = sorted(btwnCent.items(), key=lambda x:x[1], reverse=True)
sorted_nodes[:5]
# [(1, 0.43763528138528146),
#  (34, 0.30407497594997596),
#  (33, 0.145247113997114),
#  (3, 0.14365680615680618),
#  (32, 0.13827561327561325)]

매개중심성의 공식은 다음과 같습니다.

각 노드의 매개중심성 공식

• 노드v의 매개중심성 = 총합( (노드s→노드t path 중, v를 거쳐가는 path 개수) / (노드s→노드t path 개수) )

 

(endpoints = True) vs (endpoints = False)

그런데 이때, 노드 v를 노드s(start), 노드t(target)으로 두느냐 마느냐에 따라 값이 매개중심성 값은 달라집니다.

노드 A~D로 이루어진 위의 그래프에서라면, 다음과 같이 계산됩니다.

• endpoinnts = True → C(B) = 2
• endpoinnts = False → C(B) = 5

 

(normalized = True) vs (normalized = False)

위의 계산식과 예시에서 볼 수 있듯, 매개중심성의 최대값은 1이 아닙니다.

그래프 G의 크기가 커지면 커질수록 매개중심성 역시 무한히 커질 수 있습니다.

 

이 경우, 작은 그래프에서 정말 중심적인 역할을 하는 노드의 매개중심성이

매우 큰 그래프의 변두리에 있는 노드의 매개중심성보다 작아질 수 있다는 문제가 발생합니다.

 

그래서 그래프 G의 전체 노드 개수 N을 감안해 정규화처리를 할 수 있습니다.

일종의 순열조합식이죠. 이 값으로 나누면 됩니다.

 

 

매개중심성 계산의 복잡성 (샘플링으로 근사치 구하기)

매개중심성이 가지고 있는 또하나의 문제는 계산이 너무 오래 걸린다는 점입니다.

모든 노드들의 최단path를 구하고, 그 안에 특정 노드가 존재하는지 일일이 확인해봐야하기 때문입니다.

{"originWidth":862,"originHeight":420,"style":"alignCenter","width":811,"height":395,"caption":"

 

대안은 몇개의 노드만 샘플링해서 근사치를 구하는 것입니다.

기존의 nx.betweenness_centrality()에 k=샘플수를 넣으면 됩니다.

btwnCent_approx = nx.betweenness_centrality(G, normalized=True, endpoints=False, k=10)

sorted_nodes = sorted(btwnCent_approx.items(), key=lambda x:x[1], reverse=True)
sorted_nodes[:5]
# [(34, 0.3401584295334295),
#  (1, 0.31763588263588266),
#  (33, 0.12210828523328525),
#  (3, 0.11885281385281384),
#  (32, 0.09804999398749398)]

수치랑 순서가 조금씩은 바뀌었습니다.

 

 

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