Lovain Algorithm

## Lovain Algorithm

앞서 설명한 Newman Method(2021.12.08 - [Graph Mining] - Newman Method ) 는 computing power가 많이 드는 문제점이 있었다. 반면에 Lovain Algoritm은 빠른 community detection 방법이다.

이는 greedy algorithm 기반으로 O(nlogn)의 시간 복잡도를 갖고 있다. 또한 Lovain Algorithm은 weighted graph와 hierarchial community에 모두 동작한다.

동작과정은 간단하게 보면 다음과 같다.

modularity optimization -> community aggreation -> 1st pass -> 2nd pass

## 동작과정 1단계

처음엔 partitioning 을 수행한다. 이는 같은 커뮤니티끼리 묶는다는 의미이다.

partitioning은 각 노드 하나에 대해 \( \Delta Q \) 를 계산한다. 이 \( \Delta Q \)는 특정 노드 i에 대해서 현재 존재하는 커뮤니티에 넣었을 때와 안넣었을 때의 모듈성 차이를 말한다. 이러한 과정을 movement(모듈성이 더이상 올라가지 않을 때)가 없을 때 까지 반복한다.

이 때 이러한 modularity 계산을 할 때 모든 노드와 비교하는 것이 아닌 random한 노드를 비교 반복하면서 node를 선택하는 것이다. 이래서 greedy algorithm이 된다. 이러한 특성 때문에 node i가 어떠한 순서 어떠한 노드가 선택됐는지에 따라서 modularity 가 변화할 수 있다. 즉, 항상 일관성을 유지하지 못한다는 점이다. 

### Modularity Gain

여기서 \( \Delta Q \) 에 대해서 더 자세히 알아보자 . \( \Delta Q \)는 modularity Gain이라고 부른다.

식은 다음과 같다.

Modularity Gain

node_i가 C라는 Community에 포함 되었을 때의 modularity gain을 계산하는 식이다.

각 변수에 대해서 설명하겠다.

• \( \Sigma_{in} \) : Community 내부에 있는 모든 edge들의 합
• \( \Sigma_{tot} \) : \( \Sigma_{in} \) + 바깥으로 나가는 edge들끼리 포함
• \( k_{i,in} \) : node_i가 community C로 향하는 degree
• \( k_{i} \) : community C로 향하지 않는 노드까지 모두 포함하는 degree

modularity gain을 알아보기 전에 modularity에 대한 식을 다시 한 번 짚고 넘어가자

modularity

이 modularity 식을 보면서 생각하면 modularity gain의 첫 괄호(대괄호 기준)는 i가 C에 포함되었을 때 식이고, 두번쨰 괄호는 node i가 C에 포함되지 않았을 때 modularity이다.

더욱 빠른 이해를 위해 다음 그림을 참고하면서 이해하면 된다.

여기서 더욱 상세하게 봐보자

 이 식은 i가 community C에 들어왔을 때의 modularity이다. 이 때 graph는 random graph가 아닌 real graph 이다. 즉, \( \Sigma_{in} \)과 node i의 community로 들어가는 degree의 합이다.

 

이 식은 i와 C가 하나의 노드로 연결되어서 내부적으로 있을 기대 확률이다. 그림에서 node i의 모든 degree(community로 안들어가도 됨)와 C의 degree의 합이다.

 

이 식은 Community C의 modularity를 계산한 결과이다.

 

 

이 식은 node i 의 modularity 이다.

 

따라서 우괄호 식은 node i를 제외한 community C의 modularity를 말한다.

## 동작과정 2단계

위와 같은 과정을 거치면 partition이 생겨난다. 그리고 partition의 하나하나를 super node(하나의 노드)로 보고 graph를 simplification한다.

result