[논문 소개] Degree와 Closeness centrality 사이에 어떤 관계가..?

네트워크에는 정말 많은 중심성 지표가 있다. 이번에 소개할 논문에서도 인용하고 있지만, 중심성 지표를 보기 좋게 정리한 홈페이지가 있어서 일단 공유. https://schochastics.net/sna/periodic.html

Periodic Table of Network Centrality

 

네트워크에 이렇게나 많은 중심성 지표가 있는 이유는, 수학적으로도 의미가 있는 정량적 중심성이 있지만, 정성적으로 상황을 알기 쉬운 중심성도 있기 때문이다. 예전에 연결 중심성(Degree centrality)를 고찰하는 글에서도 언급한 적 있었는데, 중심성이라는 게 대개 비슷한 정보를 encoding 하기 마련이다. 따라서, 중심성 지표 여러개를 각각의 축으로 network를 설명하기 위해서는, 더 날카롭게 중심성 지표들 간의 의존성을 파악할 필요가 있다. 

 

이번에 소개할 논문의 제목은 "Linking the network centrality measures closeness and degree" 이다 (링크). 제목에서도 알 수 있듯이 이 논문에서는 Closeness centrality와 Degree centrality의 관계를 파고든다. Degree centrality는 단순히 node가 지닌 link의 개수이다. Closeness centrality는 다른 모든 node들과의 거리를 측정하고, 그 평균의 역수 값으로 나타낸다. 복잡한 것 같지만, 다른 node들과의 평균 거리가 가까울 수록 1에 가깝게, 멀 수록 0에 가깝게 조정되는 중심성 지표다.

 

 Degree 와 Closeness는 서로 양의 상관관계를 갖는다는 것이 알려져 있었다. 이를 직관적으로 설명해보자면, 친구가 많을 수록 전체 network의 사람들에게 빠르게 도달할 수 있다는 것이다. 다만, 이를 구체적으로 파고들었던 모델은 없었다. 그만큰 Closeness라는 중심성이 가진 의미가 명확했기 때문일 것이다.

 

 이 논문에서는 Closeness를 구하기 위한 spanning tree network, 즉, 자신을 뿌리로 하는 나뭇가지 모형의 network에서 2차 이상의 친구(친구의 친구, 친구의 친구의 친구...) 관계 부터는 그 수가 지수적으로 성장한다는 모델을 가정한다. 이 모델은 직접적인 친구 너머의 관계들은 지수적으로 성장하는 대량의 뭉텅이 네트워크라는 모델로 퉁칠 수 있다는 가정을 두고 있다. 그리고, 이 모델을 통해 Closeness와 Degree, 그리고 지수적 성장의 계수(z)의 관계식을 도출한다.

 

위 관계식에서 Closeness (C)의 역수는 Degree (k)에 log를 취한 값과 선형 관계를 갖는다. 즉, log(k) 값이 커질 수록, 1/C값은 선형적으로 감소하는 관계인데, 인공 네트워크 모델인 ER, BA, Config-BA model에서 이러한 관계가 뚜렷히 나타나는 걸 확인한다. 또한 실제 네트워크에서도 edge의 밀도가 높거나 비균질적인 구조의 네트워크가 아닌 경우 대개 이러한 선형 관계가 나타난다는 것을 보인다.

 

 저자는 이렇게 높게 나타나는 상관관계가 Closeness와 Degree가 실은 거의 같은 정보를 encoding하고 있다는 해석을 내린다. 따라서 굉장히 Closeness의 개념의 중요성이 두드러 지지 않는 경우, 높은 계산 cost를 사용해가면서 둘을 중복해서 계산할 필요가 없음을 주장한다. 또한, 위에서 제시한 모델에 의해 bias가 제거된 이후에도 나타나는 Closeness, 즉, Degree 정보와 독립적인 Closeness 값이 더 유의미하게 사용될 수 있음을 주장한다.

 

 이런 상관관계의 배경에는 대부분의 복잡 network가 지닌 비유클리드 공간적 특징이 있다. l단계 떨어져 있는 node의 수가 거리 l에 대해 지수적으로 증가한다는 것은 네트워크의 반경이 좁다는 뜻이다. Small-network, 좁은 반경속에서 얽힌 network인 것이다. 이런 공간에서 인접한 node를 넘어서는 node들은 대개 지수함수적으로 증가하는 거대한 뭉텅이로 표현될 수 있으며, 이러한 node들은 small world라는 조건 속에서 대개 짧은 거리 내에 밀집하므로 변별력이 크지 못하다는 것이다. 따라서 Degree가 Closeness의 변별력을 만들어내는 강력한 요인이며, 둘이 강한 관계로 나타난다는 것이다.

 

 Closeness 중심성은 사실 Road network와 같이 실제 소요되는 물리적 거리를 모티브로 고안된 지표라고 한다. 이런 물리적 거리는 대개 유클리디언 공간의 특징을 갖는다. 유클리디언 공간은 regular network와 같은 정형적인 네트워크로, small-world의 특성이 나타나지 않는 공간이다. 이런 공간에서는 자연스럽게 윗 모델의 가정이 무너지고, Degree와 Closeness의 의존성이 낮아진다.

 

정리하자면, 다음과 같다. Closeness 중심성은 유클리드 공간 특성을 갖는 network (regular, random geometric...), 비균질적인 network에서 Degree와 분리된 유의미한 값을 가진다. 좁은 반경으로 묶인 small-world network에서 Closeness는 Degree와 거의 비슷한 정보를 encoding하기 때문에, 윗 모델이 제시한 의존성을 제거한 Closeness를 사용하는 것이 의미가 있다.

 

흥미로운 점은 각각의 node를 중심으로 network로 펼쳐지는 풍경을 지수함수 모델을 이용해 퉁쳤다는 점이었는데, 그게 꽤 잘먹힌다는 점이었다. 던바의 프렌즈를 보며, ego-network와 전체 network가 공존할 수 있는 그림을 머릿속에 자꾸만 그려보게 되는데 이 모델은 꽤 구체적인 그림을 제시한다는 점에서 흥미를 느꼈던 것 같다.