군집과 군집성
군집이란?
(1) 집합에 속하는 정점 사이에는 많은 간선이 존재합니다.
(2) 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재합니다.
군집성
군집 탐색의 성공 여부를 판단하기 위해서, 군집성(Modularity)가 사용됩니다.
군집 내부의 간선의 수를 그래프와 배치 모형에서 비교합니다.
배치모형
(1) 각 정점의 연결성(Degree)을 보존한 상태에서
(2) 간선들을 무작위로 재배치하여서 얻은 그래프를 의미
군집성은 아래 수식으로 표현됩니다.
즉, 배치모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등히 많을 수록 성공한 군집 탐색입니다.
군집성은 항상 -1~1 값을 갖습니다. 보통 군집성이 0.3~0.7 정도의 값을 가질 때, 통계적으로 유의미한 군집임을 나타냅니다.
군집 탐색 알고리즘
Girvan-Newman 알고리즘
- 하향식(Top-Down) 군집 탐색 알고리즘
- 매개 중심성(Betweenness Centrality)을 통해 다리(Bridge) 역할의 간선을 순차적으로 제거
- 군집성이 최대가 되는 지점에 종료
매개 중심성(Betweenness Centrality)
해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미
Louvain 알고리즘
- 상향식(Bottom-up) 군집 탐색 알고리즘
(1) Louvain 알고리즘은 개별 정점으로 구성된 크기 1의 군집들로부터 시작
(2) 각 정점 u를 기존 혹은 새로운 군집으로 이동. 이 때, 군집성이 최대화되도록 군집을 결정
(3) 더 이상 군집성이 증가하지 않을 때까지 (2)를 반복
(4) 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 (3)을 수행
(5) 한 개의 정점이 남을때까지 (4)를 반복
중첩이 있는 군집 구조
중첩 군집 모형
(1) 각 정점은 여러 개의 군집에 속할 수 있습니다.
(2) 각 군집에 대하여, 같은 군집에 속하는 두 정점은 특정 확률로 직접 연결됩니다.
(3) 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적으로 적용됩니다.
예를 들어, 두 정점이 군집 A, B에 동시에 속할 경우 두 정점이 간선으로 직접 연결될 확률은 1-(1-PA)(1-PB) 입니다.
(4) 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 ε으로 직접 연결됩니다.
중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정입니다.
즉, 최우도 추정치(Maximum Likelihood Estimate)를 사용합니다.
중첩 군집 탐색을 용이하게 하기 위하여 완화된 중첩 군집 모형을 사용합니다.
완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현합니다.
최적화 관점에서 모형의 매개변수들이 실수 값을 가지기 때문에 익숙한 최적화 도구(경사하강법 등)을 사용하여 모형을 탐색할 수 있다는 장점이 있습니다.
