[네트워크이론] Degree Centrality(연결 중심성) 고찰

 네트워크 이론의 강력한 파워 중 하나는 바로 중심성(Centrality)다. 복잡한 관계 속에 위치한 각각의 node의 중요성을 나타내는 지표를 중심성 이라고 하는데, 엄청나게 다양한 중심성이 제안 되어 왔다. 

 오늘은 가장 대표적이면서 중요한 Degree centrality를 고찰해 보려 한다. 

 Degree centrality는 가장 간단하고도 대표적인 중심성이다. node가 지닌 degree, 즉, link의 수를 중심성의 지표로 활용한다. 더 쉽게 말하자면 '친구가 몇 명 있는가?'에 해당한다. 간단하지만 강력하고, 수많은 중심성 지표와 상관 관계를 갖는다.

 쉽게 생각해보자, 친구가 많은 사람 A가 있다. 그런데 A의 친구들은 친구가 한 명도 없는 경우가 있을까? 이런 상황은 Degree centrality는 크지만, 영향력은 거의 미미할 경우에 해당하는데, 아마도 그런 경우는 거의 없을 것이다. 고로 Degree centrality는 보통 단순히 친구의 수 이상의 강력한 파워를 지니고 있다.

(심화1)

 이러한 문제를 조금 더 심화하기 위해서는 친구가 많은 사람 A의 친구들이 어떤 특징을 지닐지 살펴볼 필요가 있다. 대표적인 방식으로 Degree assortativity(동류성) 혹은 Rich club coefficient가 있다. 

 Degree assortativity는 끼리끼리 어울린다는 의미로, 친구가 많은 사람 A의 친구들 또한 친구가 많은 경향이 있는 network의 구조를 설명한다. 

 Rich club coefficient는 Degree가 큰 node간의 연결 밀도를 정량화 하는 지표다. network에서 degree가 낮은 node를 제거해 나가며 network의 연결 밀도의 상승폭을 조사한다. 상류 사회가 끈끈하게 연결된 network일수록 밀도의 상승폭이 높아지며, Rich club의 존재를 확인하기 위한 수단으로 활용된다.

 실제 관찰된 Social network의 많은 경우에서 끼리끼리 모이는 구조와 Rich club의 존재가 확인 되었고, 이는 친구가 많은 인물일 수록 network 전반에 걸쳐 큰 영향력을 행사할 수 있다는 것을 설명해 준다.

(심화2)

 Degree centrality는 사실 network상 random walk의 행위자와 관련된 특징을 나타내기도 한다. random walk는 network 상에서 임의의 주변 link를 통해 이동하는 움직임이 반복되었을 때 나타나는 경로를 나타내는데, 이를 통해 특정 node에 머무를 확률을 구하는 방식이다. 이 확률이 높을 수록 그 node는 network의 중심적인 위치일 가능성이 높다.

 식을 통해 살펴보면 특정 시간 t에 node i 에 발걸음이 머무를 확률은 다음과 같이 표현할 수 있다.

j는 network에 속한 node를 나타내고, a_ij는 node i와 node j 사이에 link가 있을 경우 1, 없을 경우 0의 값을 갖는다. k_j는 node j가 지닌 link의 수를 나타내며, k_j로 나눈 이유는, node j에서 node i로의 이동이 k_j의 선택 지 중 하나 이기 때문이다.

 이를 network 전체에 대한 식으로 합쳐 표현하면 다음과 같다. (굵은 글씨: 행렬)

이때, k_i는 node i 가 지닌 link의 수의 합(degree)를 나타낸다.

 이를 무한히 반복하여 p(t)가 수렴하게 되었을 때, 즉 Random walk 시 발걸음이 머무를 확률 p는 다음과 같다.

이를 변형하면 다음과 같다.

 이 때 L은 Graph Laplacian으로 network 내의 확산 과정을 나타내는 행렬이다. 일반적으로 확산의 법칙은 특정 공간내의 물질의 변화율이 인접한 공간의 물질의 양과의 차이에 영향 받는다는 개념인데, network에서는 인접한 공간이 이웃 node에 해당한다. Graph Laplacian에서는 node i와 이웃 node들 j이 지니는 어떤 양 x의 차이를 (x_i - x_j1) + (x_i - x_j2) ... 의 형태로 정의 한다. 그리고 이를 정리하면 k_i * x_i - x_j1 - x_j2 - ... 이런 식으로 표현할 수 있고, 이를 모든 노드에 대한 행렬로 표현하면 D-A이 된다. 고로 network에서는 Laplacian이 D-A의 형태로 정의된다.

 이러면 D^(-1)p은 Laplacian의 고유값 0을 지닌 고유 벡터가 되는데, 모든 node가 하나의 그룹으로 연결된 network에서는 모든 값이 동일한 유일 벡터 1을 갖는다. (크기는 상관 없음)

 

 

  고로, D^(-1)p는 다음과 같이 나타낼 수 있고, 이를 통해 p의 비율을 구할 수 있다.

 

 마지막 p_i는 확률의 총합이 1이 되도록 맞추어 준 결과이다. 이 식은 network라는 하나의 유한 공간 속에서 임의적으로 움직이는 행위자가 특정 node에 머무를 확률이 node의 degree에 비례한다는 것을 표현한다. 

 이 확률은 Barabasi-Albert model(BA model)의 Preferential attachment rate와 같은 값을 나타내며, BA model의 메커니즘을 이해하는 방식으로도 활용된다.