[Data] 그래프 중심성에 대해 이해하기

Graph Centrality(중심성)이란?

중심성이란, 그래프에서 어떤 노드가 더 중요한지를 이해하기 위한 개념이다.
그래프의 연결 관계를 바탕으로 어떤 정보에 집중할지를 파악하고, 이를 분석한다.

Graph Centrality 종류들

1. Degree Centrality
2. Betweenness Centrality
3. Closeness Centrality
4. Eigenvector Centrality
5. PageRank
....
다양한 Centrality가 존재한다.

 

Graph Centrality 예시

Graph의 예시를 바탕으로, 각 Centrality를 개념적으로 이해하고자 한다.
이 글에서는 위의 예시의 1~4에 대해 이해하고자 한다.

 

이미지 출처 : https://rampages.us/thomaschon/2018/09/15/blog-3-node-centrality-is-a-small-world-network/

 

Degree Centrality

중심 노드에서 얼마나 많은 노드와 연결되었는지, 즉 차수를 기반으로 중심성을 측정하는 척도이다.
Social Network 분석 등에서, 해당 사람이 얼마나 영향력이 많은지 등을 확인하는데 쓸 수 있다.

Eigenvector Centrality

인접행렬의 eigenvector/eigenvalue를 구하여, 이를 바탕으로 중심성을 측정하는 방법이다. 단순히 연결된 차수 그 자체 보다도 전체적인 정보에 집중할 수 있다.

Closeness Centrality

여기에서는 하나의 노드에서 다른 노드로 가는 "최단거리"를 이용한다.
만일 조금 더 중심에 있는 노드라면, 다른 노드와의 거리가 상대적으로 더 가까울 것이기 때문이다.

하나의 노드에서 다른노드로 가는 최단거리의 역수의 합을 해당 노드의 Closeness Centrality로 정의한다.
만일, 해당 값이 크다는 것은 다른 노드로 가는 거리들이 짧다는 것을 의미하여, 해당 값이 클수록 중심성이 더 크다.

Betweenness Centrality

Closedness Centrality에서 조금 더 나아가, 특정 노드가 < 하나의 노드와 다른 노드의 최단 거리 위에 있는지 > 를 확인하는 지표이다. 즉, 두 노드의 연결 지점이 되어주는지를 측정하는 중심성 척도이다. 이를 수식으로 표현하면 다음과 같다.

주어진 두 개의 노드에 여러개의 최단거리가 존재할 수 있는데, 각 최단 거리를 모두 판별한다. 그 중 v가 포함된 것들의 비율을 계산하게 되고 이들의 결과값을 모두 더하게 된다.

그림에서는, h는 좌측과 우측을 연결해주는 지점이 되어 h의 Betweenness Centrality 값이 가장 높았을 것이라고 예측해볼 수 있다.

 

코드 구현

networkx 라이브러리에 잘 구현되어 있다.

deg_c = nx.degree_centrality(G)
eigen_c = nx.eigenvector_centrality(G)
close_c = nx.closeness_centrality(G)
bet_c = nx.betweenness_centrality(G)