5강. 군집 탐색
1. 군집 구조와 군집 탐색 문제
1) 군집의 정의
•
군집(Community) : 집합에 속하는 정점 사이에는 많은 간선이 존재하는 정점들의 집합 and 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재하는 정점들의 집합
2) 실제 그래프에서의 군집들
•
온라인 소셜 네트워크의 군집
•
키워드 - 광고주 그래프 → 동일한 주제의 키워드를 통한 군집 형성
•
뉴런간 연결 그래프 → 뇌의 기능적 구성 단위
3) 군집 탐색 문제
•
군집 탐색(Community Detection) : 그래프를 여러 군집으로 ‘잘’ 나누는 문제
•
비지도 기계학습인 클러스터링(Clustering)과 유사
4) 비교 대상 : 배치 모형
•
배치 모형(Configuration Model) : 각 장점의 연결성(Degree)를 보존한 상태에서 간선들을 무작위로 재배치하여 얻은 그래프
•
두 정점 i와 j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례
5) 군집성의 정의
•
군집성(Modulartiy) : 군집 탐색의 성공 여부를 판단하는 요소
•
배치 모형과 비교했을 때 그래프에서 군집 내부 간선의 수가 월등히 많을수록(차이가 클수록) 성공적인 군집 탐색
•
즉, 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단
•
항상 -1에서 +1 사이의 값을 가짐
•
0.3~0.7의 값을 가질 시, 통계적으로 유의미한 군집이라고 할 수 있음
2. 군집 탐색 알고리즘
1) Girvan-Newman 알고리즘
•
대표적인 하향식(Top-Down) 군집 탐색 알고리즘
•
전체 그래프를 먼저 탐색 후 군집들이 분리되도록 간선을 순차적으로 제거
•
서로 다른 군집을 연결하는 다리 역할의 간선들을 제거
•
간선의 매개 중심성(Betweenness Centrality) : 정점 간의 최단 경로에 놓이는 횟수
•
제거 과정
•
군집성이 최대가 되는 시점까지 간선을 제거
순서
1) 전체 그래프에서 시작
2) 매개 중심성이 높은 순서로 간선을 제거하면서 군집성의 변화를 기록
3) 군집성이 가장 커지는 상황을 복원
4) 서로 연결된 정점들, 연결 요소를 하나의 군집으로 간주
2) Louvain 알고리즘
•
대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘
•
개별 정점에서 시작해서 점점 큰 군집을 형성
순서
1) 개별 정점으로 구성된 크기 1의 군집으로부터 시작
2) 각 정점 u를 기존 혹은 새로운 군집으로 이동 → 군집성이 최대화되도록 군집을 결정
3) 군집이 더 이상 증가하지 않을 때까지 2)번 반복
4) 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3)번 수행
5) 한 개의 정점이 남을 때까지 4)를 반복
3) 중첩이 있는 군집 구조
•
그래프 확률 : 그래프의 각 간선의 두 정점이(모형에 의해) 직접 연결될 확률 and 그래프에서 직접 연결되지 않은 각 정점 쌍이(모형에 의해) 직접 연결되지 않을 확률
•
중첩 군집 탐색 : 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정
•
완화된 중첩 군집 모형 : 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현
→ 이진 값을 가지고 있지 않기 때문에 최적화 도구인 경사하강법과 같은 방법을 이용해 모형을 탐색할 수 있음
