[Graph Theory]Betweenness Centrality(매개 중심성)

Centrality

1. Degree Dependant Centrality

Betweenness centrality는 최단 거리(shortest path)에 기반해 그래프의 중심성(centrality)을 측정하는 것이다. 중심성이란 정점(vertex)의 상대적 중요성을 나타내는 척도이다.

• 중심성(Centrality): 지수로 계산됨
  • 연결 중심성(Degree Centrality)
  • 근접 중심성(Closeness Cetrality)
  • 매개 중심성(Betweenness Centrality)
  • 고유벡터 중심성(Eigenvector Centrality)

Betweenness Centrality를 ‘한 정점이 다른 두 정점 사이의 경로에 얼마나 자주 위치하는가?’를 수치화 한 것이다. Betwenness Centrality가 높은 정점은 그래프 안에서 rich-informative한 정점이라고 할 수 있다. 반면, 이 값이 작으면 그래프 안에서 중요도가 떨어지는 poorly informative한 정점이다.

1) 연결 중심성(Degree Centrality, \(C_d\))

• 정점: A, B, C, D, E
• 간선: (A, B), (A, E), (B, C), (B, E), (C, E), (D, E)
• 인접 행렬(Adjacency Matrix)

\[A= \begin{pmatrix} 0&1&0&0&1 \\ 1&0&1&0&1 \\ 0&1&0&0&1 \\ 0&0&0&0&1 \\ 1&1&1&1&0 \end{pmatrix}\]

\(C_d\)는 가장 간단한 중심성 척도이다. 한 정점에 연결된 모든 간선의 수로 중심성을 평가한다. 위의 예시에서 \(C_d\)는 \(\begin{pmatrix}2&3&2&1&4 \end{pmatrix}^T\)이다. 이는 다시 말해 한 정점과 직접적으로 연결된 간선의 수이다. 인접행렬의 각 요소를 \(a_{ij}\)라 할 때, 인접행렬에서 i번째 위치한 정점의 degree centrality는 \(\sum_j a_{ij}\)가 된다. 이처럼 undirected graph에서는 정점과 연결된 간선의 수가 곧 그래프에서 그 정점의 popularity가 된다.

반면, 지식 그래프와 같은 directed graph에서는 간선에 방향성이 생기기 때문에 In-degree와 Out-degree로 계산되는 centrality는 다른 의미를 가지게 된다. In-degree가 정점으로 들어오는 간선에 해당하며 이는 곧 그 정점의 popularity를 반영한다. Out-degree의 경우 정점에서 뻗어 나가는 간선에 해당하며 이는 그 정점이 다른 정점에 영향을 많이 끼치는 것을 의미하므로, 해당 정점의 영향력을 반영하게된다. 두 경우 모두 크면 클 수록 그래프에서 rich-informative한 정점이라고 말할 수 있다.

단순히 연결 중심성으로만 네트워크의 중심성 비교를 수행하기는 어렵다. 크기가 큰 그래프일수록 당연히 \(C_d\)값도 커지기 때문에 공정한 비교는 불가능하다. 따라서 비교의 공정성을 주고자 정규화를 진행하기도 한다. \(N\)개의 정점을 가지는 그래프 내 가능한 최대 \(C_d\)값은 \(N-1\)이며 이 값을 나눈값을 사용하거나, 실제로 측정한 \(C_d\)의 최댓값을 나눈다.

\[C_d = A \cdot \vec{1} \;\; \\ \vec{1} = 1 \times N \; \text{vector}\]

2) 고유벡터 중심성(Eigenvector Centrality, \(C_e\))

그래프에서 무작정 연결된 정점이 많다고 rich-informative하다고 말하긴 어렵다. 만약 한 정점의 degree가 100이고, 그 정점과 연결된 100개의 정점의 평균 degree가 2이면 전체 그래프에서 이 subgraph부분은 중요한 정보가 아닐 수 있다(일종의 outlier). 연결 중심성은 이러한 것처럼 단순히 degree만 고려한다는 점에서 한계를 보인다. 이를 보완하고자 나온 것이 바로 고유벡터 중심성(eigenvector centrality, $C_e$)이다. 이는 중심성을 계산할 때 다른 정점의 중심성도 반영하여 계산한다.

\[\lambda C_e = AC_e\]

\(A\) 가 그래프의 인접 행렬이고, \(C_e\)는 중심성을 나타내는 \(1 x N\) 행렬이다. 위의 인접행렬식을 사용해 계산하면
\(C_e = \begin{pmatrix}0.882&1.121&0.882&0.464&1.247 \end{pmatrix}^T\)이 된다.

3) Katz 중심성(Katz Centrality, \(C_k\))

고유벡터 중심성의 한계 중 하나는 방향성 비순환 그래프와 같이 특정 상황에서 centrality의 값이 0이 되는 경우가 있다는 것이다. Katz는 이를 해결하고자 모든 정점의 centrality에 특정한 상수값을 더하는 방식을 제안하였다. 대체적으로 \(\alpha < \frac{1}{\lambda}\) 로 설정한다.

\[C_k =\alpha AC_e \; + \; \beta\]

4) 페이지 랭크(Page Rank, \(C_p\))

Page rank는 추천 시스템 등 다양한 분야에서 사용되는 가장 대표적인 centrality algorithm이다. Katz 중심성을 변형해 계산된다. Katz 중심성 계산식에서는 한 정점의 중요성이 연결된 다른 정점으로 전부 전파(propagation)된다. 즉, 어떤 정점의 중심성이 높을 경우 , 그 정점의 이웃 정점들의 중요도도 같이 높아진다. 이는 그래프를 이해하는데 방해가 될 때가 존재한다.

위의 그림에서 (1)의 그래프와 (2)번 그래프 모두 중심에 위치한 정점 \(P\)가 다른 모든 정점들과 연결된 것을 확인할 수 있다. 즉, \(P\)를 중심으로 한 ego network라 할 수 있다. 다만, (1)번 그래프의 경우 중심을 제외하고는 모든 정점들은 다른 정점과 연결되지 않지만, (2)번 그래프의 경우 각 정점별로 degree가 다른 것을 볼 수 있다. 두 그래프 존재하는 정점은 같더라도, 두 그래프에서 각각의 정점이 가지는 영향력은 상이하다. 하지만, Katz 중심성을 사용할 경우 (1)번 그래프에서 중심 \(P\)와 다른 모든 정점들 모두 중요하다 판단할 수 있다. (2)번 그래프에서도 마찬가지다. 하지만, (2)번 그래프에서는 각 정점별로 degree가 다르기 때문에 정점별로 중요도가 다르다. 즉, 중심 \(P\)와 \(g\)가 중요하다 말할 순 있지만, 중심 \(P\)와 \(h\)가 중요하다고 말하긴 어렵다.

Page rank는 각 정점의 영향력을 다른 정점으로 전파할 때, 외부로 향하는 모든 간선의 수(Out-degree)로 나누어 Out-edge로 영향력이 지나치게 퍼지는 것을 막는다.

\[C_p = \alpha AD^{-1}C_p + \beta\]

대체적으로 \(\alpha < \frac{1}{\lambda}\) 로 설정한다. 이 때 \(\lambda\)는 A의 고유값 중 가장 큰 값이며 Undirected Graph에서는 1이 된다.

1) 연결 중심성, 2) 고유벡터 중심성 3) Katz 중심성 4) Page Rank는 모두 한 정점이 다른 정점과 얼마나 연결되어 있는지에 대해 초점을 맞춘다.

2. Degree Independant Centrality

1) 매개 중심성(Betweenness Centrality, \(C_{btw}\))

매개 중심성의 핵심은 최단 경로이다. 어떤 정점의 매개 중심성을 파악할 때, 다른 두 정점을 연결하는 최단 거리 경로 상에 그 정점이 존재하는 경우의 수를 중심성의 척도로 삼는다.

다시 말해, Betweenness Centrality는 모든 두 정점 사이의 가장 짧은 경로(shortest path)가 해당 정점을 지나가는 수를 의미한다. 즉, 모든 shortest path 위에 해당 정점이 많을수록 중요한 정점으로 여기는 것이다. 단, \(V\)개의 정점과 \(E\)개의 간선이 있을 때의 시간 복잡도는 \(O(\vert V \vert \cdot \vert E \vert\)로 매우 크다는 단점이 있기에, 특정 정점들을 샘플링해 진행하기도 한다. 매개 중심성은 그래프를 이해하는 강력한 도구이다. 매개 중심성을 이해하기 위해 예를 들면, “만약 회사에서 새로운 고객을 유치할 때 꼭 거쳐야 하는 사람이라면( = 일종의 Hub Node) 중요한 사람이 아닐까?” 라는 질문에 대한 답이 매개 중심성이다.

2) 근접 중심성(Closeness Centrality, $C_c$)

근접 중심성은 한 정점으로 부터 모든 정점 사이의 최단거리를 구한 후 이 평균값이 작은 정점을 중요한 정점으로 판단하는 방법이다. 즉, 어떤 정점이 그래프에서 다른 정점들과의 평균 거리가 짧을수록 \(C_c\)값은 크다.

\[C_c = \frac{1}{\frac{1}{N-1} \displaystyle\sum_{X \neq A} l_{X, A} }\]

\(l\)은 두 정점 사이 최단 거리이다.

3) 조화 중심성(Harmony Centrality, $C_h$)

근접 중심성과 유사하지만, 최단거리의 평균을 역수로 취하는 것이 아니라, 최단 거리 역수의 평균을 구한다.

\[C_h(A) = \frac{1}{N-1}\displaystyle\sum_{X \neq A} \frac{1}{l_{X, A}}\]

3. Betweenness Centrality 구현하기

1) Basic

betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None)

• parameters
  • G : Graph
  • k : int, optional
    • If k is not None use k node samples to estimate betweenness. The value of k <= n where n is the number of nodes in the graph. Higher values give better approximation.
  • normalized : bool, optional
    • Graph: 2/((n-1)(n-2))
    • Directed Graph: 1/((n-1)(n-2))
  • weight : None or String, optional
    • If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight. Weights are used to calculate weighted shortest paths, so they are interpreted as distances.
  • endpoint : bool, optional
    • If True include the endpoints in the shortest path counts.

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)]

2) Approximated Betweenness Centrality (Sampling)

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)]

Reference

Blog1 - [NetworkX] 매개중심성 (Betweenness Centrality)
Blog2 - [네트워크 이론] 다양한 중심성(Centrality) 척도들

Graph 카테고리 내 다른 글 보러가기