[23] 군집 구조

1️⃣ 군집의 정의

 

군집(Community)이란 다음 조건들을 만족하는 정점들의 집합입니다.

 

(1) 집합에 속하는 정점 사이에는 많은 간선이 존재합니다.

(2) 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재합니다.

 

https://arxiv.org/pdf/1210.8182.pdf

 

그래프를 여러 군집으로 나누는 문제를 군집 탐색(Community Detection) 문제라고 합니다.

 

 

2️⃣ 군집성

1) 배치 모형 (Configuration Model)

배치 모형(Configuration Model)은 다음과 같은 그래프를 의미합니다.

 

1) 각 정점의 연결성(Degree)을 보존한 상태

2) 간선들을 무작위로 재배치하여서 얻음

 

https://www.edwith.org/bcaitech1

 

배치 모형에서 임의의 두 정점 𝑖와 𝑗 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례합니다

 

2) 군집성(Modularity)

 

군집 탐색의 성공 여부를 판단하기 위해서, 군집성(Modularity)이 사용됩니다.

 

그래프와 군집들의 집합 S가 주어졌다고 합시다. 각 군집 𝑠 ∈ 𝑆가 군집의 성질을 잘 만족하는 지를 살펴보기 위해, 군집 내부의 간선의 수를 그래프와 배치 모형에서 비교합니다.

 

군집성은 다음 수식으로 계산됩니다.

괄호 내부의 차이가 크면 클수록 군집성이 좋은 것으로 나타납니다.

즉, 배치 모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등이 많을수록 성공한 군집 탐색입니다.

(여기서 $|E|$는 전체 edge의 수이며, $\frac {1} {2|E|}$는 정규화 과정을 나타내 군집성은 -1 ~ 1 사이로 나오게 됨)

 

https://www.edwith.org/bcaitech1

즉, 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단합니다.

군집성은 항상 –1과 +1 사이의 값을 갖으며, 보통 군집성이 0.3 ~ 0.7 정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있습니다.

 

 

 

3️⃣ 군집 탐색 알고리즘

1) Girvan-Newman 알고리즘

 

Girvan-Newman 알고리즘은 대표적인 하향식(Top-Down) 군집 탐색 알고리즘입니다.

 

Girvan-Newman 알고리즘은 전체 그래프에서 탐색을 시작합니다. 군집들이 서로 분리되도록, 간선을 순차적으로 제거합니다. 

 

어떤 간선을 제거해야 군집들이 분리될까요?

바로 서로 다른 군집을 연결하는 다리(Bridge) 역할의 간선입니다.

아래와 같이 파란색 선을 따라 간선을 제거하면 군집을 찾을 수 있습니다.

 

https://pubmed.ncbi.nlm.nih.gov/26826854

 

서로 다른 군집을 연결하는 다리 역할의 간선을 찾는 방법은 "간선의 매개 중심성(Betweenness Centrality)"을 사용합니다. 매개 중심성은 해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미합니다.

 

아래 그림과 같이 왼쪽 군집의 정점 4개 x 오른쪽 군집의 정점 4개 = 16으로 두 개의 정점을 골라 최단 경로를 통한다고 가정했을 때 모든 경우의 수 중 16번을 지난다는 사실을 알 수 있습니다. 

 

https://www.edwith.org/bcaitech1

 

따라서 매개 중심성은 다음과 같은 수식으로 계산됩니다.

• $\sigma_{i,j}$ : 정점 𝑖로 부터 𝑗로의 최단 경로 수
• $\sigma_{i,j} (x,y)$ : $\sigma_{i,j}$중 간선 $(x,y)$를 포함한 것

 

매개 중심성을 통해 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있습니다.

아래 그림과 같이 매개 중심성이 높은 간선들이 서로 다른 군집을 연결하는 다리 역할을 하는 것을 확인할 수 있습니다.

 

http://infolab.stanford.edu/~ullman/mmds/ch10n.pdf

 

이제 Girvan-Newman 알고리즘을 순차적으로 알아보면 다음과 같습니다.

 

 

(1) 매개 중심성이 높은 간선을 순차적으로 제거합니다.

 

이때, 간선이 제거될 때마다, 매개 중심성을 다시 계산하여 갱신합니다.

 

http://infolab.stanford.edu/~ullman/mmds/ch10n.pdf

 

(2) 간선이 모두 제거될 때까지 반복합니다.

 

http://infolab.stanford.edu/~ullman/mmds/ch10n.pdf

 

(3) 간선의 제거 정도에 따라서 다른 입도(Granularity)의 군집 구조가 나타납니다.

 

http://infolab.stanford.edu/~ullman/mmds/ch10n.pdf

 

(4) 군집성이 최대가 되는 지점까지 간선을 제거합니다.

 

현재의 연결 요소들을 군집으로 가정하여 군집성을 계산합니다.

예를 들어, 2개의 입력 그래프가 있을 때에는 2개의 군집이 있다고 가정하고, 6개의 입력 그래프가 있을 때에는 6개의 군집이 있다고 가정합니다. 

 

아래 그림과 같이 빨간색 선에서 간선이 제거되었을 때 군집성이 최대가 됩니다.

따라서 빨간색 선 정도의 간선이 제거되었을 때에 입력 그래프의 상태를 복원해낸 뒤 그때의 입력 그래프의 연결 요소들을 군집으로 간주하게 됩니다.

 

http://infolab.stanford.edu/~ullman/mmds/ch10n.pdf

 

정리하면, Girvan-Newman 알고리즘은 다음과 같습니다.

 

1) 전체 그래프에서 시작합니다.

2) 매개 중심성이 높은 순서로 간선을 제거하면서, 군집성을 변화를 기록합니다.

3) 군집성이 가장 커지는 상황을 복원합니다.

4) 이때, 서로 연결된 정점들, 즉 연결 요소를 하나의 군집으로 간주합니다.

 

2) Louvain 알고리즘

 

Louvain 알고리즘은 대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘입니다.

Louvain 알고리즘은 개별 정점에서 시작해서 점점 큰 군집을 형성합니다.

 

https://sites.google.com/site/findcommunities/

 

Louvain 알고리즘을 순차적으로 알아보면 다음과 같습니다.

 

 

1) Louvain 알고리즘은 개별 정점으로 구성된 크기 1의 군집들로부터 시작합니다.

 

https://sites.google.com/site/findcommunities/

 

2) 각 정점 𝑢를 기존 혹은 새로운 군집으로 이동합니다. 이 때, 군집성이 최대화되도록 군집을 결정합니다.

 

https://sites.google.com/site/findcommunities/

 

3) 더 이상 군집성이 증가하지 않을 때까지 2)를 반복합니다.

 

4) 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3)을 수행합니다.

 

https://sites.google.com/site/findcommunities/

 

5) 한 개의 정점이 남을 때까지 4)를 반복합니다.

 

https://sites.google.com/site/findcommunities/

 

 

4️⃣ 중첩이 있는 군집 탐색

 

실제 그래프의 군집들을 중첩되어 있는 경우가 많습니다.

아래 그림과 같이 그래프 안에 여러 군집들이 중첩되어 있는 경우입니다.

 

https://sites.google.com/site/findcommunities/

 

이를 위해 아래와 같은 중첩 군집 모형을 가정합니다.

 

https://sites.google.com/site/findcommunities/

 

1. 각 정점은 여러 개의 군집에 속할 수 있습니다.
2. 각 군집 𝐴에 대하여, 같은 군집에 속하는 두 정점은 $𝑃_𝐴$ 확률로 간선으로 직접 연결됩니다.
3. 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적입니다.
   예를 들어, 두 정점이 군집 𝐴와 𝐵에 동시에 속할 경우 두 정점이 간선으로 직접 연결될 확률은 1 − (1 − $𝑃_𝐴$)(1 − $𝑃_𝐵$)입니다.
4. 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 𝜖으로 직접 연결됩니다.

 

중첩 군집 모형이 주어지면, 주어진 그래프의 확률을 계산할 수 있습니다.

 

그래프의 확률은 다음 확률들의 곱입니다.

 

1. 그래프의 각 간선의 두 정점이 (모형에 의해) 직접 연결될 확률
2. 그래프에서 직접 연결되지 않은 각 정점 쌍이 (모형에 의해) 직접 연결되지 않을 확률

https://sites.google.com/site/findcommunities/

 

하지만 현실에서는 그래프는 주어져 있지만 중첩 군집 모형이 주어져 있지 않은 경우가 많습니다.

따라서 중첩 군집 탐색을 사용하는데,

중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정입니다.

즉, 통계 용어로 최우도 추정치(Maximum Likelihood Estimate)를 찾는 과정입니다.

 

https://sites.google.com/site/findcommunities/

 

하지만 최우도 추정치(Maximum Likelihood Estimate)를 구하는 것은 쉽지 않습니다.

각 정점이 각 군집에 속하는지 여부가 "속한다, 속하지 않는다"처럼 이산적으로 결정되기 때문이죠.

따라서 연속적인 값일 때 사용할 수 있는 기술들(경사 하강법 등)을 사용할 수 없습니다.

 

중첩 군집 탐색을 용이하게 하기 위하여 완화된 중첩 군집 모형을 사용합니다.

완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속해 있는 정도를 실수 값으로 표현합니다.

즉, 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나였는데, 중간 상태를 표현할 수 있게 되었습니다.

 

완화된 중첩 군집 모형을 사용하면 최적화 관점에서 모형의 매개변수들이 실수 값을 가지기 때문에 익숙한 최적화 도구 (경사하강법 등)을 사용하여 모형을 탐색할 수 있다는 장점이 있습니다.