[네트워크 이론] local clustering과 global clustering이 다른 이유

 Degree 편향을 보정한 결집계수를 다룬 글에서 잠깐 거론된 바가 있는데, 지역적으로 clustering 계수를 구해서 평균을 낸 결과와, 전역적으로 clustering 계수를 구한 결과는 전반적으로 같은 경향을 보이지만, 그래프의 구조적 특성에 따라 크게 상이할 수 있다.

 

 이 문제를 본격적으로 다룬 논문이 있어 간략히 정리해본다. 

 

 이 문제를 풀기 위해 저자는 Windmill graph를 이용한다. Windmill graph는 한 node를 중심으로 완전 그래프 k(k개의 node가 서로 모두 연결된 그래프)가 n개 연결되어 있을 때, W(n, k)로 표시한다. node 하나를 중심으로 완전그래프들이 펼쳐진 모습이 마치 풍차의 모습과도 같다. 

 

 이 때, n을 무한히 늘리면, local clustering coefficient의 평균은 1이 되지만, global clustering coefficient는 0이 된다. 논문에서는 이를 수식으로 증명했는데, 쉽게 말하면 다음과 같다.

•  중심의 한 node를 제외한 모든 node들의 local clustering은 1이기 때문에 n이 늘어나면 평균값이 1이 된다.
•  n이 늘어나면, 중심 node 주변에 가능한 삼각형 개수가 n^2의 꼴로 늘어나는 반면에, 실제 삼각형 개수는 n^1 꼴로 늘어나기 때문에, global clustering은 0으로 수렴한다.

 즉, global clustering은 커다란 하나의 hub가 지니는 clustering 계수가 높게 반영되는 경향이, local clustering은 다수의 clustering 계수가 주요해지는 경향이 있는 것이다. 

 

 이는 실제 네트워크, 특히 논문 citation 네트워크와 collaboration network에서 두드러지게 나타난다고 한다. 이는 하나의 Hub가 되는 paper나 저자들 주변으로 형성된 network들이 부분적으로 clustering을 형성한 결과로 부터 비롯할 수 있다고 한다. 즉, 한 논문이 많은 수의 서로 다른 community (완전그래프에 가까운)로부터 인용되었을 때, 지역적으로는 높은 결집계수를 가지나, 전역적으로는 낮은 결집계수를 가질 수 있다는 것이다.

 

 Class size pradox 와 Friendship paradox의 예에서 처럼, 결집계수도 전역과 지역의 관점은 통합되기 힘들어 보인다. 물리적 공간에서 전역적 관점의 데카르트 좌표계와 지역적 관점의 극 좌표계는 서로 다른 관점으로 같은 현상을 표현할 수 있는 반면, 네트워크 공간에서 관점을 달리 한다는 것은 편향을 유발한다.

 네트워크 공간에서 실체란 무얼까. Social network를 볼 때 우리는 Hub를 중심으로 계층적으로 펼쳐진 전체 구조 속에서 node들의 중요성을 평가하지만, 개개인의 node에게는 그 주변이 제일 중요하다. 사람이 개인과 사회에서 끝없는 저울질을 하는 이유가 여기에 있지 않을까 싶다. 

 

 

참고)

Estrada, Ernesto. "When local and global clustering of networks diverge." Linear Algebra and its Applications 488 (2016): 249-263.