[그래프 이론] Modularity 뜻, 계산 예시(그래프 분할 평가)

그래프 분할(Graph Partition)

다음과 같은 그래프가 있다고 가정을 해봅시다. 이제 이 그래프를 2개의 그룹으로 나누어보겠습니다. 그래프 분할을 위한 여러 알고리즘을 적용할 수 있겠지만 속마음으로 한번 나누어 보세요. 이제 두 개의 그래프가 A, B 두 가지 방법으로 나누어진 경우를 생각해보겠습니다.

두 그룹 사이 cut(주황색 선)을 지나는 edge 개수 등의 대략적인 기준이나 이 경우는 눈대중으로만 보더라도 B가 A보다는 그래프 분할이 잘 진행된 것으로 보입니다.

 

그래프 분할이 의미있는 상황은 예를 들어, 제가 고등학교때 만난 친구들 그룹끼리 SNS 친구 관계가 얽혀있을 것이고, 대학교 과에서 만난 친구들 그룹끼리 SNS 친구 관계가 얽혀있을 것이고 등의 관계를 생각해보면 이해가 쉬울 것입니다.

 

이번 포스팅에서는 그래프 분할을 평가하는 Modularity라는 지표의 의미와 계산 방법, 그리고 계산 예시를 간단히 살펴보고, 그래프 분할을 진행하는 방법 등에 대한 내용은 나중에 기회가 있다면 다루어보도록 하겠습니다.

 

Modularity

참고로, 방향이 없는 그래프를 기준으로 설명드리겠습니다.

방향이 있는 경우는 해당 방향만 edge가 있는 것으로 평가하시면 됩니다.

 

우선, Modularity의 정의를 살펴보면 다음과 같습니다.

$$ Q = \frac{1}{2m}\sum_{s \in S} \sum_{i, j \in s} (A_{ij} - \frac{k_i k_j}{2m})$$

식의 의미를 차근차근 설명해드리겠습니다.

 

Q가 저희가 구하려는 Modularity이며, -1 ~ 1 사이의 값을 가지고, 높은 숫자일수록 그래프가 잘 분할되었다는 의미입니다. 0.3~0.7 이상으로 측정되는 경우 커뮤니티 구조가 어느정도 뚜렷하다는 양상을 의미한다고 알려져있습니다.

S는 분할된 그래프의 집합입니다. 위 그림에서는 빨강, 파랑 2개의 집합이 있겠죠.

\(A_{ij}\)는 그룹 s 내부의 그래프 내 i번쨰 node와 j번째 node 사이에 edge 유무를 의미합니다. 있으면 1, 없으면 0입니다.

m은 전체 edge의 개수를 의미합니다.

\(k_i, k_j\)는 i번째, j번째 node의 degree를 의미합니다.

 

\(A_{ij} - \frac{k_i k_j}{2m}\) 부분이 의미하는 것은 그룹 내부에 실제로 연결된 edge의 개수 - 그룹 내 edge 개수의 기대값을 의미합니다.

 

참고로, \(\sum_{i, j \in s}\)에서 의미하듯, 방향의 없는 그래프의 경우 i -> j방향과 j -> i방향을 각각 따로 세주셔야합니다.

 

Modularity 계산 예시

첫 번째 예시입니다. 우선, 총 edge는 7개이므로 m = 7 입니다.

각 그룹에 대해서 \(\sum A_{ij}\)를 계산해보도록 하겠습니다.

빨강색 그룹부터 계산해보면, 1번 노드 입장에서 2개(2, 3번 노드로), 2번 노드 입장에서 2개(1, 3번 노드로), 3번 노드 입장에서 2개(1, 2번 노드로, 4번 노드는 다른 그룹으로 가는 노드라 세지 않습니다.)로 총 6개의 노드가 내부에서 연결되어 있다는 것을 알 수 있습니다.

파랑색 그룹도 마찬가지로 6개의 노드가 내부에서 연결되어 있습니다.

 

이제 그룹 내 edge 개수의 기대값 부분에 있는 \(\sum k_i k_j\) 부분을 계산해보겠습니다.

이 때, i = j인 경우(자기 자신 노드로 들어오는 경우)도 카운팅해주어야 합니다.

빨강색 그룹부터 계산해보면, 1, 2번 노드는 degree가 2이고, 3번 노드는 degree가 3입니다(여기서는 다른 그룹과 연결된 edge도 셉니다).

따라서, $$ k_1 k_1 + k_1 k_2 + k_1 k_3 + k_2 k_1 + k_2 k_2 + k_2 k_3 + k_3 k_1 + k_3 k_2 + k_3 k_3 $$

$$ = (k_1 + k_2 + k_3)^2 = (2 + 2 + 3)^2 = 49$$

가 됩니다.

파랑색 그룹도 마찬가지로 계산이되고, 최종 modularity를 구해보면 다음과 같이 유도됩니다.

$$ Q = \frac{1}{14} \sum_s \sum_{i, j}(A_{ij} - \frac{k_i k_j}{14}) $$

$$ = \frac{1}{14} \sum_s (6 - \frac{49}{14}) $$

$$ = \frac{1}{14} (6 - \frac{7}{2}) \times 2$$

$$ = \frac{5}{14}$$

 

약 5/14로 0.35이상이고, 어느 정도 뚜렷한 커뮤니티를 형상한 그룹임을 의미한다 정도를 유추해볼 수 있겠습니다.

 

마찬가지로 다음 그래프에 대해서도 계산을 진행해볼까요?

edge개수인 m = 6

\(\sum A_{ij}\)는 두 그룹 모두 4 (두 그룹 모두 1 + 2 + 1)

\(\sum k_i k_j\)는 두 그룹 모두 36 (빨강 그룹 (1 + 3 + 2)^2, 파랑 그룹 (2 + 2 + 2)^2)

최종 modularity는

$$ Q = \frac{1}{12} \sum_s \sum_{i, j}(A_{ij} - \frac{k_i k_j}{12}) $$

$$ = \frac{1}{12} \sum_s (4 - \frac{36}{12}) $$

$$ = \frac{1}{12} \times 1 \times 2$$

$$ = \frac{1}{6}$$

 

첫 번째 예시보다 modularity가 낮게 측정되었고, 이 경우는 그룹 간의 커넥션도 더 많은 것으로 생각해볼 수 있습니다.