[네트워크이론] Louvain algorithm for community detection

 network로부터 community를 추출하는 방법으로 Girvan-Newman algorithm와 Link community를 소개한 적이 있었다. 오늘은 그 3탄으로 Louvain algorithm을 소개하려고 한다.

 Louvain algorithm이 처음 소개된 논문은 Fast unfolding of communities in large networks, Vincent D et al., Journal of Statistical Mechanics: Theory and Experiment(2008) 이다. 이 알고리즘에 Louvain이라는 이름이 붙은 이유는 벨기에의 Louvain이라는 대학 출신이어서.. 애교심이 대단하다ㅎㅎ

 이번 글은 논문의 전개 방식에 맞추어 Louvain algorithm의 배경부터 소개해보고자 한다.

배경

---

 network에서 community를 추출하는 방법은 크게 두가지로 나뉜다. 

 하나는 divisive algorithm, 네트워크가 분열되도록 inter-community, 즉 community간 link를 잘라나가는 방법이다. inter-community link를 추정하는 대표적인 방법이 link의 betweenness 중심성을 조사하는 방법으로, Girvan-Newman algorithm이 이와 같은 방법을 사용하고 있다.

 다른 하나는 agglomerative algorithm, 비슷한 노드/커뮤니티를 점진적으로 합쳐나가는 방법이다. 주로, clustering기법을 사용하며 이전에 소개한 link community 법이나, fast greedy algorithm 같은 방법이 있다.

 위의 방법들은 최적의 community 추출 상태를 평가하기 위해, 여러가지 방법들이 고안되어왔는데, 그 중 대표적인 것이 modularity, 모듈성이다. modularity는 -1~1의 값으로 네트워크의 모듈화 정도를 나타내며, community 내부 link와 community간 link의 밀도를 비교하는 방식이다.

 modularity는 계산에 긴 시간이 소요된다는 단점이 있다. modularity를 이용한 최적화 방법 중에서 가장 빠른 방법인 greedy algorithm(Clauset et al.)이 있는데, 최적화 성능이 그렇게 좋지 않다. 또, 큰 규모의 super-communities를 생산해버리는 경향이 있어, 심지어 인공적으로 community구조가 없도록 만든 network에서도 거대한 규모의 community를 추출해버리곤 한다.

 위와 같은 문제점들을 해결하기 위해 Louvain algorithm이 고안되었다. Louvain algorithm은 한개의 node로부터 주변 node들을 흡수하며 community를 생성해 나간다는 것은 greedy법과 비슷하지만, 두 가지 개선책을 적용하고 있다. 하나는 개선된 modularity 계산법, 둘은 network의 계층적 구조를 이용하는 방법이다.

---

Method

---

 Louvain algorithm은 두가지 phase의 반복으로 구성된다.

Phase 1

첫 phase에서는 한 node를 원래의 community에서 빼어내어 인접한 community에 재배치 하였을 때의 modularity의 변화를 측정한다. 측정값을 기준으로, modularity가 가장 큰 폭으로 상승하는 community에 node를 배속 시킨다. 어떤 변화도 일어나지 않을 때 까지 수행한다. 

 이 방법은 한개의 node 1번 부터 100번 까지의 node가 있다면, 이 작업을 어떤 노드부터 수행하는가에 따라 다른 결론이 도출될 수 있는데, 저자들은 여러번의 실험결과 이러한 순서가 도출되는 modularity에 큰 영향을 끼치지 않는다는 것을 알아냈다. 하지만, 바뀐 순서는 계산 속도에 영향을 줄 수 있다는 것도 알아냈는데, 추후 순서를 어떻게 정할지 추가적으로 연구할 필요가 있다고 한다. (2008년 논문이므로 이미 나와있을 수도..)

 첫 phase에서는 modularity 변화량을 다음과 같이 정의한다.

modularity 변화량  =  node i가 community에 배속된 상태의 modularity  -  node i가 배속되지 않은 상태의 modularity

m : 모든 link weight의 합

 원래 modularity의 정의는 다음과 같다. (이전글 참조)

 이를 특정 community C_l에서만 살펴본다면 다음 식으로 표현할 수 있다. 

 

 그러면 node i가 특정 community에 배속되었을 때(윗 그림의 가장 오른쪽 상태)와, 그러기 전 상태(윗 그림의 중간 상태)의 modularity 변화량은 위에서 정의한 식임을 알 수 있다.

 위의 과정을 더이상 변화가 일어나지 않을 때까지 모든 node에 대해 반복 수행하는 것이 Phase1의 작업 내용이다.

 

Phase 2

 두번째 phase에서는 Phase 1에서 생성된 community를 하나의 block으로 합쳐서 node취급을 한다. 이 때, community 내부 link의 weight은 자기 회귀 상태의 link로, community간에 연결되어있던 node간의 link weight는 합쳐서 하나의 link로 생성한다. 

 이 후, 이 새롭게 변형한 network는 다시 Phase 1의 algorithm을 통해 병합해나간다. Phase 1을 마치면 다시 Phase 2로 돌입한다.

 Phase 2 이후, Phase 1에서 더 이상 변화가 일어나지 않을 때 Louvain algorithm은 동작을 정지한다.

Fast unfolding of communities in large networks, Vincent D et al.(2008)

---