[네트워크 이론] 결집계수(Clustering Coefficient)

Posted by 적분 ∫2tdt=t²+c
2017.03.17 13:44 그냥 공부

앞서서 네트워크 상에서 어떤 노드가 중요한지를 알아보는 중심성을 살펴봤는데, 이번에는 네트워크가 얼마나 똘똘 뭉쳐있는지를 알려주는 '결집계수(Clustering Coefficient)'에 대해서 살펴보도록 합시다.


결집계수는 추이성(Transitivity)을 기반으로 합니다. 이는 A->B이고 B->C이면 A->C가 되는 성질을 말합니다. 수학에서 부등호나 등호 같은 경우가 추이성을 가지는 관계지요. 문제는 네트워크 그래프의 노드들은 항상 추이성을 가지지 않을 수도 있다는 것에 있습니다. A가 B와 연결되고, B가 C와 연결되어있다고 하더라도, A가 C와 반드시 연결되지 않을수도 있기 때문이죠. 


뭉쳐있는 정도를 얘기하다가 추이성을 꺼낸 이유는, 우리가 노드들이 똘똘 뭉쳐있다는 것을 "추이성" 가지고 정의할 것이기 때문입니다. 즉 A->B 이고, B->C일때 A->C인 경우 A, B, C는 뭉쳐있다고 보자고 정의하는 것입니다. 이를 바탕으로 결집계수가 정의되죠.


전역 결집계수


수식으로 적으면 다음과 같습니다.

여기서 TΔ는 A-B, B-C, C-A로 연결된 3개의 노드쌍을 모아놓은 집합이고, T는 A-B, B-C로 연결된 노드쌍의 집합입니다. 즉 전체 A-B, B-C로 연결된 전체 노드쌍들 중에서 C-A가 연결까지 노드쌍의 비율을 계산하는 것입니다.


이 그래프를 예로 들어보겠습니다. 여기에 있는 연결된 노드 삼중체(A-B-C와 같이 연결된 3개의 노드쌍)를 모두 나열하자면 ABC, ABE, AEB, AEC, AED, BAE, BCE, BEA, BEC, BED, CBA, CBE, CEA, CEB, CED, DEA, DEB, DEC, EAB, EBA, EBC, ECB 가 되겠죠. 이중에서 삼각형을 이루는 것은 굵게 표시한 녀석들 밖에 없습니다. 즉 전체 22개 중에 12개가 삼각형으로 연결되어 있으니, |TΔ| = 12, |T| = 22이므로

위 그래프의 결집계수는 0.545가 됩니다. |TΔ|를 쉽게 세는 방법은 삼각형 갯수에 6을 곱하는 것입니다. 삼각형 하나 당 6개의 경로가 나오기 때문이죠.


위의 예시는 가중치가 없는 그래프에 대한 것이었습니다. 간선에 가중치가 있는 그래프에 대해서는 어떻게 결집계수를 계산할 수 있을까요? Opsahl와 Panzarasa가 제시한 논문에서 가중치 있는 그래프에 대한 일반화된 결집계수 계산식을 제시했는데 다음과 같습니다. 

위와 같이 연결된 노드 삼중체들의 모든 가중치 합을 구하고, 삼각형을 이루는 삼중체들의 가중치 합과의 비율을 살펴보는 것입니다. 삼중체의 가중치는 어떻게 구할까요? Opsahl은 삼중체를 이루는 각 간선 가중치의 산술평균 또는 기하평균, 최댓값, 최솟값을 후보로 제시했습니다. 네트워크에 따라 실험을 통해 적절한 가중치 계산법을 사용해야 하는 것을 추천했습니다.


지역 결집계수

위에서 말한 결집계수는 전체 네트워크를 대상으로 계산하게 됩니다. 따라서 전역 결집계수(Global Clustering Coefficient)라고 부르기도 합니다. 한 노드 주변의 노드들이 얼마나 뭉쳐있는지를 살펴보기 위해서는 지역 결집계수(Local Clustering Coefficient) 개념을 사용해야 합니다. 이는 다음과 같이 계산됩니다.


A_xy 는 x와 y가 연결되어 있음을 뜻합니다. 즉 i의 모든 이웃들 중에서 2개씩 고른 쌍 중에서 연결되어 있는 쌍들의 비율을 계산하는 것입니다.


수식으로만 보면 정신없으니 위의 그래프에서 노드B의 지역 결집계수를 계산해봅시다.

B의 이웃은 A, C, E가 있지요. 이 이웃 노드들 간의 가능한 쌍은 AC, CE, EA 3개가 있습니다. 이중에서 굵게 표시한 2개만 실제로 이어져있으므로, B의 지역 결집계수는

가 됩니다.


덤으로 모든 노드에 대해서 지역 결집계수를 계산하고 그 평균을 구한것을 네트워크 평균 결집계수(Network Average Clustering Coefficient)라고도 부른답니다.


랜덤 그래프의 경우 그래프의 규모가 커질수록 결집계수는 0에 가까워지는 특징이 있습니다. 따라서 결집계수가 높게 나오는 것은 랜덤 그래프가 아닌 노드 간의 연결이 뚜렷한 그래프라고 볼 수 있겠죠. 

저작자 표시 비영리 동일 조건 변경 허락
신고
이 댓글을 비밀 댓글로