[네트워크이론] 여러가지 Modularity 들

 Newman과 Girvan에 의해 처음 고안된 modularity는 다음과 같다. (자세한 내용은 이전 글 참조)

 

$Q = \frac{1}{2M} \sum\limits_{i, j}^{N} (a_{ij} - \left\langle t_{ij} \right\rangle) \delta(c_{i}, c_{j}) $

 

$ \left\langle t_{ij} \right\rangle = \frac{k_{i}k_{j}}{2M} $ 

 

$ M $ : 총 link 수

$ N $ : 총 node 수

$ a_{ij} $ : node i와 j 사이의 link가 있을 때 1 (없을 때 0)

$ \left\langle t_{ij} \right\rangle $ : node i와 j 사이의 link의 기댓값

$ \delta(c_{i}, c_{j}) $ : node i 와 j가 같은 community 일 때 1 (아니면 0)

 

여기서 $ \left\langle t_{ij} \right\rangle $는 비교대상인 null model에 기반한다. 

Newman과 Girvan이 고안한 modularity에서 null model은 configuraton model에 해당한다.

Configuration model은 node가 지닌 link의 수(degree)를 유지하면서 임의로 link 연결을 조정한 random network이다. 이 모델에서 특정 node i, j사이에 연결이 있을 기대값은 각 node의 degree의 곱에 비례한다. 2M으로 나눠주는 이유는 link(i-j)와 link(j-i)를 따로 보기 때문이다. 따라서 i와 j사이에 link가 있을 확률은 $ \frac{k_{i}}{2M} \cdot \frac{k_{j}}{2M} $이고, link의 기댓값은 여기에 $2M$을 곱한 $\frac{k_{i}k_{j}}{2M} $이 된다. 

 

Configuration model은 자연스럽게 weighted network로 확장이 가능하다. 

바로, link의 weight를 하나하나의 link가 모인 multiple edge의 개념으로 생각해보면 된다. 그렇게 되면 configuration model의 개념에 따라 자연스럽게 node i와 j 사이의 link weight의 기댓값 $ \left\langle t_{ij} \right\rangle $은 $ \frac{s_{i}s_{j}}{2W} $로 해석될 수 있다. ($s_{i}$는 node i의 link의 weight의 총합, $W$는 모든 link의 weight의 총합)

정리해보면

 

$Q = \frac{1}{2W} \sum\limits_{i, j}^{N} (w_{ij} - \left\langle t_{ij} \right\rangle) \delta(c_{i}, c_{j}) $

 

$ \left\langle t_{ij} \right\rangle = \frac{s_{i}s_{j}}{2W} $ 

 

$ W $ : 총 link들의 weight의 합

$ N $ : 총 node 수

$ w_{ij} $ : node i와 j 사이의 link의 weight

$ \left\langle t_{ij} \right\rangle $ : node i와 j 사이의 link weight의 기댓값

$ \delta(c_{i}, c_{j}) $ : node i 와 j가 같은 community 일 때 1 (아니면 0)

 

 

 정리해보자면, link의 기대값을 빼주는 이유는, 자연스럽게 생길 수 있는 연결들을 modularity에서 제외시키기 위함이다. 그리고, 자연스럽게 생길 수 있는 연결은 null model인 configuration model에 기반한다. 

 Configuration model은 가장 직관적이지만, 적절치 않은 경우도 있다. 예를들면, unweighted network에서 self-loop와 multiple edges가 문제될 수 있다는 점을 지적한 연구라던가, null model로 configuration model보다 적절한 model (예를 들어 공간에 embedding된 network라면 gravity model, radiation model...)을 적용하는 것이 더 좋다는 연구도 있다.

 사실, configuration model은 만능이 아니다. Configuration model에서는 모든 node간의 연결이 가능하다고 보는데, 아주 큰 network는 보통 그 사이즈 (node의 개수)에 비례하여 link의 수가 증가하지 않는다. 따라서, node들간의 link에 대한 기댓값이 엄청나게 작아진다. 그 결과 별 의미 없는 link임에도 과대평가 되어 modularity를 높이는 역할을 하곤 하는데, 이는 modularity를 이용한 community detection 의 resolution limit을 낳게 된다. 즉, 의미 없는 연결임에도 Cluster라고 판단해 버리는 것이다. 이렇게 modularity의 resolution limit을 해결하기 위한 방법은 community detection의 한 분야가 되어 있다. 

 

 같은 modularity의 개념을 이용해서, resolution limit을 오히려 활용한 연구도 있다. 

 이 연구에서는 다음과 같은 식을 이용한다. 

 

$Q = \frac{1}{2M} \sum\limits_{i, j}^{N} (a_{ij} - \gamma\frac{k_{i}k_{j}}{2M}) \delta(c_{i}, c_{j}) $

 

 이 식에서 $\gamma$는 resolution paremeter인데, 이 값이 작으면 큰 사이즈의 community를, 크면 작은 사이즈의 community를 추출하게 된다. 위에서 말한 configuration model의 기댓값이 과소/과대 평가 되는 것을 조정하기 위함인데, 이를 통해 다양한 규모의 community를 추출하는 것이 가능하다.

 

 이 외에도 modularity density, z-modularity, surprise 와 같은 모듈성 평가지표들이 resolution limit을 해결하기 위해 등장했다고 하는데, 이는 다음 번에 기회가 있으면 정리해 보는 걸로.. (관련해서 community detection과 관련한 연구들을 모아 놓은 python package가 있다. 아주 유용하므로 링크를 추가.)