Community Detection

Contents

 

Community

군집이란 Cluster 혹은 Community를 의미하며, 집합에 속하는 노드 사이에는 만은 엣지가 존재하고, 집합에 속하는 노드와 그렇지 않은 노드 사이에는 적은 수의 엣지가 존재해야 한다. 아래의 그림을 예로 들면, 11개의 군집이 있는 것을 확인할 수 있다. 

 

온라인 소셜 네트워크에서도 군집을 찾아볼 수 있다. 이때는 사회적 무리(Social Circle)를 의미하는 경우가 많다. 예를 들어, 같은 회사 동료라는 사회적 무리와 가족 관계 혹은 고등학교 친구 등과 같은 사회적 무리를 의미한다. 이때의 사회적 무리는 회사 동료, 가족 관계, 고등학교 친구 뿐만 아니라 같은 지도 교수님한테 지도받은 학생들, 대학 동기 등 다양한 사회적 무리를 나타낼 수 있다.

Facebook

온라인 소셜 네트워크의 군집들이 부정 행위와 관련된 경우가 존재할 수 있다. 예를 들어, 인플루언서인 척 하기 위해 인스타나 트위터에서 팔로우를 구매하는 등의 행위를 해서 부정적인 계정들이 군집을 이룰 수도 있다. 또한, 조직 내의 분란이 소셜 네트워크 상의 군집으로 표현된 경우가 존재할 수 있다. 동아리 내에 분란이 발생해 동아리 내의 인원이 둘로 나뉘어지는 경우 그래프에서는 서로 다른 군집으로 형성될 수 있다. 

 

Neural Network

그 뿐만 아니라 사람의 뇌에 존재하는 뉴런 간의 연결성을 나타내는 그래프의 경우 군집들이 뇌의 기능적 구성 단위를 의미할 수 있다. 이처럼 그래프를 여러 군집으로 잘 나누는 문제를 Community Detection이라고 한다. 이는 머신러닝에서 다루는 비지도 학습인 군집분석과 상당히 유사하다. 그렇다면 그래프에서는 어떻게 Community Detection을 수행하는지 알아보자. 

 

Configuration Model 

Configuration Model은 각 노드의 차수를 보존한 상태에서 엣지를 무작위로 재배치해 얻은 그래프를 의미한다. 즉 원래 그래프와 다른 그래프를 생성하는 것이다. Configuration Model에서 임의의 두 노드 $i$와 $j$사이에서 엣지가 존재할 확률은 두 노드의 차수에 비례한다.

 

군집이 제대로 군집화 되었는지 확인하기 위해서는 군집성(Modularity)가 사용된다. 그래프와 군집들의 집합 $S$가 주어졌을 때 각 군집 $s\in S$가 군집의 성질을 잘 만족하는 지 살펴보기 위해 군집 내부의 엣지 수를 그래프와 Configuration Model에서 비교한다. 구체적으로 군집성은 아래와 같은 수식으로 계산된다. 

\[ \frac{1}{2|E|} \sum_{s \in S} ( |G^s_e| - \mathbb{E}(|C^s_e|)) \]

$G^s_e$는 그래프에서 군집 s 내부에 존재하는 간선의 수를 의미하고 $\mathbb{E}(|C^s_e|)$는 Configuration Model에서 군집 s 내부에 존재하는 엣지 수의 기댓값을 의미한다. 즉, Configuration Model과 비교했을 때 그래프에서 군집 내부 엣지의 수가 월등히 많을수록 성공한 Community Detection이라 한다. 

 

군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적으로 유의미한지 확인할 수 있는 하나의 평가지표를 의미한다. 군집성은 항상 -1에서 1사이의 값을 가지며, 보통 0.3에서 0.7 정도의 값을 가질 때 그래프에서 존재하는 통계적으로 유의미한 군집을 찾았다고 할 수 있다. 

 

 

Community Detection

위에서는 군집성(Modulariry)을 가지고 군집이 제대로 군집화 되었는지에 대해서 측정하는 평가지표에 대해서 다루어 보았다. 그렇다면 군집을 찾는 군집 탐색 알고리즘은 어떤 것들이 있을까? 대표적인 모델로는 Girvan-Newman 알고리즘과 Louvain 알고리즘이 존재한다. 두 알고리즘에 대해서 알아보자.

 

Givan-Newman

Givan-Newman 알고리즘은 대표적인 Top-Down 알고리즘이다. 먼저 전체 그래프에서 탐색을 시작하고, 군집들이 서로 분리되도록 엣지를 순차적으로 제거하는 방식으로 진행된다. 이때 서로 다른 군집을 연결하는 다리(Bridge) 역할을 하는 엣지를 제거하는 것을 목적으로 한다. 

 

이때는 매개 중심성(Betweenness Centrality)을 사용하여 다리 역할을 하는 엣지를 찾을 수 있다. 이는 노드 간의 최단 경로에 놓이는 횟수를 의미하며, 노드 $i$로 부터 $j$로 가는 최단 경로 수를 $\sigma_{i, j}$라고 하며고 그 중 엣지 $(x, y)$를 포함한 것을 $\sigma_{i,j}(x,y)$라고 하자. 그러면 엣지 $(x,y)$의 매개 중심성은 아래와 같은 수식으로 계산된다. 

\[ \sum_{i<j} \frac{\sigma_{i,j} (x,y)}{\sigma_{i,j}} \]

노드 간의 최단 경로를 계산할 때 자주 포함되는 엣지의 경우 서로 다른 군집을 연결하는 다리 역할을 할 가능성이 높아지기 때문에 매개 중심성이 높은 엣지를 순차적으로 제거하면서 진행된다. 제거한 후 다시 매개 중심성을 계산하고, 모든 간선이 제거될 때까지 반복한다. 엣지를 제거할 때마다 군집성의 변화를 확인하고, 군집성이 가장 커지는 상황을 복원해 이때의 연결된 구조를 하나의 군집으로 설정한다. 

 

1. 전체 그래프에서 시작.

2. 매개 중심성이 높은 순서로 엣지를 제거해 나가면서, 군집성이 변화하는 값을 기록.

3. 군집성이 가장 높아지는 상황을 복원.

4. 이때의 연결된 구조를 하나의 군집으로 간주.

 

Louvain

Louvain 알고리즘은 Givan-Newman 알고리즘과는 달리 Bottom up 방식을 사용한다. 개별 노드에서 시작해서 점점 큰 군집을 형성하는 형태로 진행된다. 

Louvain 알고리즘은 각각의 노드로 구성된 크기 1의 군집으로 부터 시작한다. 이때도 역시 군집성을 기준으로 군집성이 최대화되도록 군집을 결정하며, 더이상 군집성이 증가하지 않을 때 까지 반복하거나 한 개의 노드만 남을 때까지 반복한다.

 

 

Overlap Community Model

위에서 다룬 Girvan-Newman 알고리즘과 Louvain 알고리즘은 전부 군집 간의 중첩이 없다는 것을 가정하고 있다. 그렇다면 중첩이 있는 군집의 경우 군집을 어떻게 찾아낼 수 있을까? 일단 먼저 중첩되어 있는 군집 모형을 다음과 같이 가정하자. 1) 각 노드는 여러 개의 군집에 속할 수 있다. 2) 각 군집 A에 대해, 같은 군집에 속하는 두 노드는 $P_A$ 확률로 엣지에 직접 연결된다. 3) 두 노드가 여러 군집에 동시에 속할 경우 엣지 연결 확률은 독립적이다. 예를 들어, 두 노드가 군집 A와 B에 동시에 속할 경우 두 노드가 엣지로 직접 연결될 확률은 1 - (1-$P_A$)(1-$P_B$)이다. 4) 마지막으로 어떤 군집에도 속하지 않는 두 노드는 낮은 확률 $\epsilon$으로 직접 연결된다.

 

위에서 가정한 중첩 군집 모형이 주어지면, 주어진 그래프의 두 엣지의 두 노드가 직접 연결될 확률과 직접 연결되지 않은 각 노드 쌍이 직접 연결되지 않을 확률을 계산할 수 있다. 

이때 주어진 그래프의 확률을 최대화하는 중첩 군집을 찾는 것이다. 그러나 기존 노드의 경우 군집에 속하거나 속하지 않거나에 대한 값을 반환하기 때문에 이산형 변수로 Maximum Likelihood Estimate를 사용하는 것이 어렵다 .따라서, 이를 가능하게 하기 위해 완화된 Overlap Community Model을 사용한다.

 

이는 각 노드가 각 군집에 속해 있는 정도를 실숫값으로 표현한다. 기존에는 binary classification 문제였으나, 실숫값으로 변환함으로써 중간 상태를 표현할 수 있게 된 것이다. 위 그림에서는 확률을 엣지의 굵기로 표현하였다. 이와 같이 변환하게 되면 경사하강법(Gradient Descent) 등과 같은 익숙한 최적화 도구를 사용하여 모델을 업데이트하면서 학습할 수 있다는 장점이 존재한다.