종혁의 저장소

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

공부/네트워크과학

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

죠옹 2018. 2. 18. 03:17

 네트워크를 바라보면, 네트워크 속에서도 끼리끼리 뭉쳐있는 커뮤니티가 보이곤 한다. 다음 네트워크를 예로 들어보자. 네트워크지만, 위쪽 아래쪽 왼쪽으로 끼리끼리 모여있는 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를 구하는 식에 대입하면 모듈리티를 구하는 기본 식이 완성된다.


 

 이 식은 그냥 노드 한개씩 쭈욱 계산 하면 계산이 되기는 하는데, 불편하다. 노드의 관점에서 바라본 식이기 때문이다(Python Networkx에선 이 식을 이용해서 Modularity를 구한다. 컴퓨터에게 유리). 


 그래서 이 식을 커뮤니티 관점에서 바라보는 식으로 변형한다. 윗 식에서 δ함수는 커뮤니티가 같을 때만 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로 대체할 수 있게 된다.



 다음으로, 두번째 항은 다음과 같이 전개된다.



 변환 후에, 윗 식에서 구한 e_ll' 을 대입하여 식을 마무리한다.

 이제 첫번째 항과 두번째 항을 합치면



 이렇게 커뮤니티 별 내부/외부 연결의 갯수를 세어 계산하는 것이 가능해진다.


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



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



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



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


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




>> 다음 글에서는 실제 Modularity를 커뮤니티 추출에 어떻게 이용하는지 실제 예제를 통해 정리해보겠다.

2 Comments
댓글쓰기 폼