[네트워크이론] Network Modularity (네트워크의 모듈성)

 네트워크를 바라보면, 네트워크 속에서도 끼리끼리 뭉쳐있는 커뮤니티가 보이곤 한다. 다음 네트워크를 예로 들어보자. 네트워크지만, 위쪽 아래쪽 왼쪽으로 끼리끼리 모여있는 3개의 작은 커뮤니티가 있는 것처럼 보인다. 그렇다면 이를 어떻게 찾아낼 수 있을 것인가?

 위의 그림의 3개의 커뮤니티에 대한 label이 존재한다고 생각해보자. 이 때, 이 네트워크의 커뮤니티 구조는 얼마나 모듈화 되어 있을 것인가? 

 Modularity(모듈성)는 이를 정량적으로 나타내기 위해 등장했다. 

 Modularity는 커뮤니티 내부에 펼쳐져 있는 링크들이 무작위적인 연결들과 비교했을 때 얼마나 더 많은지 정량화 한다. 구체적으로는 원래의 네트워크 G와 각 노드의 링크의 개수를 유지한 체로 대상을 랜덤하게 변화시킨 네트워크 G'와 원래 네트워크 G를 비교하여 도출된다.

 

 기본적인 식은 다음과 같다. 

 

Q             모듈성

M            전체 링크 수  

N             전체 노드 수

a_ij           i, j간 링크 (있을 경우 1, 없을 경우 0)

t_ij           각 노드가 지니는 링크의 개수는 그대로 유지, 대상을 무작위적으로 재연결 하였을 때 노드 i, j 간 링크

               (있을 경우 1, 없을 경우 0)

<t_ij>        t_ij의 기대치

C(i)           노드 i가 속하는 커뮤니티

δ(C(i), C(j))  C(i)와 C(j)가 같은 커뮤니티일 때 1, 다를 때 0

 

 

 식을 살펴보면, 커뮤니티 내부의 링크의 개수가 무작위적 상태의 기대 값보다 얼마나 큰지 나타내고 있음을 알 수 있다. 

 윗 식에서 <t_ij>값이 없다면, 커뮤니티 내부의 링크의 수가 전체 링크 중 차지하는 비율을 나타내는 식이 된다. <t_ij>는 임의적 연결이 나타낼 수 있는 모듈성을 제거하기 위해 도입되었다.

 극단적인 예로, 전체 network를 1개의 community로 두었을 때, 이 community의 모듈성은 <t_ij>가 없다면 1로 최댓값을 지닌다. 하지만, <t_ij>를 도입하면 0의 값을 가지게 된다. 임의적 연결이 생성하는 modularity를 제거하기 위함이라고 생각하면 되겠다.

 

 윗 식은 처음엔 복잡한 식이지만, 정리하여 나중에는 보기 쉬운 깔끔한 식으로 정리되므로 전개 과정이 필요 없는 경우에는 이 부분을 건너뛰고 보아도 된다. 

 

 먼저, 윗 식에서 무작위적인 상태로 정의한 링크 t_ij의 기대값을 구해보자. 결론부터 말하면, <t_ij>는 다음의 식으로 나타낼 수 있다.

 

M     전체 링크 수  

p_i    링크 중 한 쪽 끝에 노드 i가 있을 확률

 t_ij 는 각 node가 지닌 링크의 개수를 유지한 채로 무작위적으로 재구성한 network G'의 node i와 node j간의 link를 나타낸다. 링크가 있을 경우 1, 없을 경우 0의 값을 가진다.

 이 때, G'의 한 link가 node i와 node j간을 연결한 link일 확률은 (p_i * p_j + p_j * p_i) 이다. 전체 link의 개수는 M이므로, t_ij의 기대값은 2*M*p_i*p_j로 나타낼 수 있다.

 

 p_i는 G'이 단순히 링크를 무작위적으로 재연결한 것이 아닌, 각 node가 지닌 link의 수를 유지하고 있다는 점에 주의해야 한다. 즉, 단순히 1/N (N: node 개수)의 확률이 아닌, node가 지닌 link의 수에 비례하는 확률을 이용해야 한다.

k_i     노드 i가 지니는 링크의 개수

M      전체 링크 수  

 

  모든 노드의 링크의 수 k_i를 다 더하면 (2*전체 링크의 수(M))이 된다. 한 링크는 양단에 연결된 두 노드에서 각각 더해지기 때문이다. 

 

 이 식을 modularity Q를 구하는 식에 대입하면 모듈리티를 구하는 기본 식이 완성된다.

 

 

 이 식은 그냥 노드 한개씩 쭈욱 계산 하면 계산이 되기는 하는데, 계산 시간이 오래 걸린다. 

 

 그래서 이 식을 커뮤니티 관점에서 바라보는 식으로 변형한다. 윗 식에서 δ함수는 커뮤니티가 같을 때만 1이 되므로, 커뮤니티 관점에서 식을 정리하여 δ함수를 없앨 수 있다.

 

 

l              커뮤니티 넘버

n_C          전체 커뮤니티의 개수  

 

 이렇게 변형이 된다. 여기서 한층 더 변형을 한다. 2M을 식 내부로 넣어 표현하면 다음과 같이 변형을 시킨다.

 

 

 이렇게 변형하는 최종 목적은 모듈성을 커뮤니티 내부의 연결 개수와 커뮤니티 간의 연결의 개수로 표현하는 것이다. 이를 위해 C_l 커뮤니티 에서 C_l' 커뮤니티로의 연결의 개수를 전체 연결의 개수로 나눈 값, 즉 전체 연결에 대한 커뮤니티 간의 연결의 비율을 e_ll'로 나타낸다. 이에 대한 식은 다음과 같이 표현할 수 있다.

 

 

 

 C_l 커뮤니티에 속한 노드 i로부터 C_l'에 속한 노드 j로의 연결의 합을 전체 연결의 수 2M으로 나눈 비율을 표현한 것이다. M으로 나누지 않는 이유는 노드의 관점에서 연결의 개수를 전부 합하므로, 모든 노드에 대한 총 합이 2M이 되기 때문이다.

 또 한가지, l = l' 즉 같은 노드 안에서 연결을 계산할 경우에는 커뮤니티 내부에서의 모든 연결은 두 번씩 중복이 된다. 예를 들어 C_l에 속한 노드 i와 j는 i에서 j의 연결과 j에서 i의 연결이 두번씩 더해지게 된다. 반대로 l != l' 인 경우에는 각 노드에 대해 한번씩 더해지게 되므로 나중에 링크의 숫자를 세서 계산할 때에 혼동하지 않도록 주의해야 한다.

 

 이 식을 이용하면 위의 Q식의 첫번째 항을 e_ll로 대체할 수 있게 된다.

 

(2020.07.29 수정)

 

 다음으로, Q식의 두번째 항은 다음과 같이 표현할 수 있다.

 

 

이 때, k_i는 다음과 같이 표현할 수 있다.

 

이를 윗 식에 대입하면, 식을 e_ll'로 표현할 수 있다.

 

 

 이제 첫번째 항과 두번째 항을 합치면, 커뮤니티 별 내부/외부 연결의 갯수를 세어 Q를 계산하는 것이 가능해진다.

 

 

 

 더 간단히 하는 법이 있다. 먼저 윗 식의 첫번째 항은 자기 내부의 연결의 개수이다. 전체 연결 갯수 대비 커뮤니티 i에서 j로의 연결의 갯수 e_ij 를 행렬 E로 나타내면

 

 

 이와 같이 표현할 수 있고, Q식의 첫번째 항은 대각행렬의 합으로 나타낼 수 있다.

 

 

 두번 째 항은 행렬 E가 대칭 행렬임을 이용하여 다음과 같이 변형한다.

 

 

여기서 2번째 줄에서 3번째 줄은 e_ij로 구성된 행렬이 대칭 행렬이기 떄문에 가능하다. Community i에서 j로 연결된 연결의 개수와 j에서 i로 연결된 연결의 개수가 같기 때문이다. ||E^2|| 는 E행렬을 제곱하여 모든 항을 다 더한 것을 의미한다.

 

 두 식을 합치면 다음과 같이 계산량을 깔끔하게 줄일 수 있는 식이 구해진다.

 

 

 

>> Modularity를 이용한 커뮤니티 추출 예제는 여기

>> 여러가지 Modularity에 대한 글은 여기