[그래프] 5-2. 군집 구조 : 군집 탐색 알고리즘

 

1. Girvan-Newman 알고리즘

1. 개념 설명

• 대표적인 하향식(Top-down) 군집 탐색 알고리즘 = 전체 그래프에서 탐색을 시작함. 즉, 군집들이 서로 분리되도록 간선을 순차적으로 제거함
• 어떤 간선을 제거해야 하나? → 서로 다른 군집을 연결하는 다리(Bridge) 역할의 간선
• 아래 예시에서 빨간 선을 따라 간선을 제거한다고 생각해보면 → 각각의 군집들이 다른 요소가 되어 떨어져 나옴을 상상할 수 있음

 

• 그럼 다리 역할의 간선을 어떻게 찾아낼 수 있을까? 간선의 매개 중심성(Between 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}}$ : 각 정점의 최단 경로 중 x, y 포함한 것의 비율의 합

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

 

2. 군집 탐색 프로세스

Girvan-Newman 알고리즘은 매개 중심성이 높은 간선을 순차적으로 제거. 간선이 제거될 때마다 매개 중심성을 다시 계산하여 갱신.
이를 간선이 모두 제거될때까지 반복한다.

간선의 제거 정도에 따라 다른 입도(Granularity)의 군집 구조가 나타남

 

3. 간선 제거 기준

군집성이 최대가 되는 지점까지 간선을 제거한다. 그 기준은 앞서 정의한 군집성으로 삼는다. → 군집성이 최대가 되는 지점까지 간선 제거
이 때, 현재의 연결 요소들을 군집으로 가정하되, 입력 그래프에서 군집성 계산

 

 

정리
1. 전체 그래프에서 시작
2. 매개 중심성이 높은 순서로 간선 제거하면서 군집성 변화 기록
3. 군집성이 가장 커지는 상황을 복원
4. 이 때, 서로 연결된 정점들, 즉 연결 요소를 하나의 군집으로 간주

 

---

2. Louvain 알고리즘

1. 개념 설명

• 대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘, 개별 정점에서 시작해서 점점 큰 군집을 형성
  
• 아래 그림은 군집 단위에서 그래프를 재 구성한 것임

 

2. 군집 탐색 프로세스

이때에도 군집성을 기준으로 군집을 생성한다.

1. 개별 정점으로 구성된 크기 1의 군집으로 시작

2.  각 정점 u를 기존 또는 새로운 군집으로 이동. 이때, 군집성이 최대화 되도록 결정

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

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

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

 

 

---

edwith의 그래프와 추천 시스템 강의를 듣고 정리 한 내용입니다.

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith