[네트워크이론] Degree 편향을 보정한 결집계수(Clustering Coefficient)

결집계수

 결집계수(Clustering coefficient)는 네트워크의 결집도를 정량화 하는 한 방법이다. 그 정의가 참 재미있는데 다음과 같다.

C_i : node i 의 지역(local) 결집 계수

k_i : node i 의 이웃의 수 (=degree)

T(i) : node i 의 이웃끼리 이웃인 경우 (node i를 중심으로 삼각형이 만들어지므로 Triangle의 개수라고도 한다)

 특정 node i 의 이웃과 이웃이 서로 이웃인 경우를, 모든 가능한 경우 'k(k-1)/2'로 나눈 값을 지역(local) 결집계수로 정의한다. 

결집계수의 문제점

 결집계수는 node의 특성을 나타내는 값으로 많이 이용하는데, 치명적인 단점이 있다. 바로, 분모가 과대 평가 된다는 점이다. 이웃의 수가 적다면 모든 경우의 수 'k(k-1)/2'가 납득이 갈 수도 있겠지만, 링크가 100이 되고, 1000이 된다면 어떨까? 내 이웃 1000명이 모두 서로 서로 연결된 엄청나게 밀도가 높은 network가 현실적으로 가능할까? 하는 생각이 들 것이다.

  고로, 지역 결집계수는 높은 degree에서 상당한 negative 편향이 발생한다. 그래서 지역 결집계수를 보완하기 위해서는 C_i의 분모항이 가능한 범위를 더 엄격히 볼 필요가 있다.

 다음 논문은 이웃이 지닌 degree정보를 이용하여 이러한 편향을 줄이기 위한 방법을 제안하고 있다.

 Soffer, Sara Nadiv, and Alexei Vazquez. "Network clustering coefficient without degree-correlation biases." Physical Review E 71.5 (2005): 057101.

 

보정 방법

 방법을 간단히 설명하면 다음과 같다. 윗 그림의 흰 동그라미가 지역 결집계수를 조사하고자 하는 node이다. 이 node를 i라고 하자. i는 이웃이 5명 있으므로, 보통 가능한 모든 경우의 수는 5*4/2=10 가지다. 고로, 예전 방법을 적용하면 T(i)/10이 지역 결집계수가 될 것이다.

 하지만 i의 이웃인 검은 동그라미들이 지닌 이웃의 개수를 살펴보자. 8, 7, 2, 2, 2 이다. 이미 node i 와 연결되었으니, 사실상 node i 의 이웃끼리 연결할 수 있는 여분의 link의 수는 7, 6, 1, 1, 1 이다. 

 이 때 첫 번째, 두 번째 이웃의 여분 link는 7과 6이므로 node i의 나머지 모든 이웃들과 연결될 가능성이 있다. 하지만 3~5번째 이웃은 여분 link가 1이므로 node i 의 이웃 한 명과 연결되고 나면 여분의 link가 없다. 기존의 방법은 이를 고려하지 않고, node i 의 모든 이웃끼리 연결될 경우를 전체 가능성으로 두었기 때문에 분모가 과대평가 된다.

 (b)를 보면, 7, 6, 1, 1, 1 을 4, 4, 1, 1, 1 로 둔다. 어차피 7이든 6이든 뭐 100이든 간에 나머지 이웃들과 연결될 수 있기 때문에 maximum을 나머지 이웃의 개수로 두는 것이다. 그리고 나서 여분 link가 높은 node로 부터 나머지 node들 간의 연결을 시작한다. 이렇게 하고 나면, 전체 가능한 link는 4가 되고, 잉여 link는 3이 남는다. 기존의 '10'을 대신하여 '4'를 분모에 둠으로써 Degree가 커지면서 과소평가 되는 결집계수를 보정해 준다. 

보정 결과

 가장 만만한 karate club의 Data를 이용해서 어떤 식으로 보정 되는지 살펴보자.

 

 c가 기존 지역 결집계수, c_w가 보정 후 결집계수를 나타낸다. 보기 좋게 같은 degree별로 평균 값을 취했다. 기존  degree가 커질 수록 적게 평가 되었던 결집계수가 보정된 것을 볼 수 있다.

 이러한 보정 방식은 기존 전체 네트워크의 결집 계수를 구하는 두 가지 방법, 지역 결집계수의 평균을 구하는 방법과, 전체 T(i)의 밀도를 구하는 방법에서 나타나는 차이를 보정하여 일관적인 지표로 이용할 수 있다는 장점이 있다고 한다.

 특히, degree가 disassortative한 network에 적용하기에 유용하다. disassortative network는 끼리끼리 뭉쳐 있지 않은 network로, degree가 큰 node의 이웃들은 비교적 적은 degree를 갖는다. 고로, 기존 방법에서 분모가 degree*(degree-1)로 되는 것은 실제 이룰 수 있는 삼각형의 수를 상당히 뻥튀기 한 꼴이 된다. 그래서 기존 방법을 이러한 network를 대상으로 시행했을 때, 지역적 결집계수의 평균과 전체 결집계수에 큰 bias가 발생한다. 이럴 때 새로운 기법을 도입하면 일관적인 지표를 얻을 수 있다.

코드

 간단한 코드는 다음과 같다. 편의를 위해 networkx 패키지를 이용했다. 

import matplotlib.pyplot as plt
import numpy as np
import networkx as nx
import pandas as pd

graph = nx.karate_club_graph()

""" 인접행렬 """
A = nx.to_numpy_array(graph)

""" degree """
k = A.sum(axis=0)
""" degree matrix"""
A_degree = k * A

clustering = []
clustering_new = []
for node in range(A.shape[0]):
    """ 이웃 list """
    n_list = np.where(A[node] != 0)[0].tolist()
    """ 이웃들로 이뤄진 matrix 추출 """
    tmp = np.take(A, n_list, axis=0)
    n_m = np.take(tmp, n_list, axis=1)

    """ 기존 분모 """
    old_method = len(n_list) * (len(n_list) - 1) / 2

    """""""""" 보정 """""""""
    """ 이웃들의 degree"""
    n_degree = np.take(k, n_list)
    """ node의 이웃 수와 이웃들의 degree 수 중 최소값 만을 취함"""
    minimum_degree = np.minimum(len(n_list) - 1, n_degree - 1)
    """ 이웃과 이웃 사이에 가능한 link 수 계산 """
    a = minimum_degree.copy().astype(int)
    w = 0
    while True:
        """ 가능한 link가 소진되었을 때 while문 종료 """
        if len(np.where(a != 0)[0]) <= 1:
            break
        """ 정렬 """
        a = np.sort(a)[::-1]
        """ 가장 큰 degree를 지닌 node로부터 link를 연결 """
        a[1:a[0] + 1] = a[1:a[0] + 1] - 1
        """ 연결된 link 수 가산 """
        w += a[0]

        """ 이미 여분 link가 0인 node에까지 연결되었을 시 보상 """
        tmp = a[1:a[0] + 1].copy()
        compen = np.sum(tmp[tmp < 0])
        w += compen
        a[a < 0] = 0
        a[0] = 0 - compen

    """ 실제 T_i는 이웃간 연결 개수 """
    T_i = np.sum(n_m) / 2

    """ 지역 결집계수 계산 """
    c = T_i / old_method
    c_w = T_i / w

    clustering += [c]
    clustering_new += [c_w]

""" k에 따른 결집계수 평균 값 계산 """
df = pd.DataFrame(data={'degree': k,
                        'c': clustering, 'c_w': clustering_new})
c_mean = []
c_w_mean = []
degree = pd.unique(df['degree'])
for n in degree:
    c_mean += [np.mean(df[df['degree'] == n]['c'])]
    c_w_mean += [np.mean(df[df['degree'] == n]['c_w'])]

""" 플롯 """
fig = plt.figure
plt.scatter(degree, c_mean, label='c')
plt.scatter(degree, c_w_mean, label='c_w')
plt.xscale('log')
plt.yscale('log')
plt.xlabel('degree')
plt.ylabel('clustering coefficient')
plt.legend()
plt.show()

추가

 좀 더 큰 network의 경우를 보고 싶어서 Stanford 대학에서 제공하는 Collaboration data에도 적용해 보았다. 

 마찬가지로 높은 degree에서의 음의 trend가 어느정도 보정되는 것을 확인할 수 있다.

 node개수 10만개 이상의 아주 큰 네트워크에서는 Memory 에러가 나는데, 인접행렬을 이용한 T(i) 계산 방법을 보완할 필요가 있어보인다.