[그래프] 5-1. 군집 구조 : 군집 탐색 문제

1. 군집(Community)의 정의

군집(Community)이란 다음 조건들을 만족하는 정점들의 집합을 의미하지만 수학적으로 엄밀한 정의는 아니다.

1. 집합에 속하는 정점 사이에는 많은 간선이 존재
2. 집합에 속하는 정점과 그렇지 않은 정점 사이에는 상대적으로 적은 수의 간선이 존재

온라인 소셜 네트워크의 군집들은 사회적 무리(Social Circle)를 의미하는 경우가 많다.

 

뉴런 간 연결 그래프에서는 군집들이 뇌의 기능적 구성단위를 의미

 

---

2. 군집 탐색 문제

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

비지도 기계학습 문제인 클러스터링과 상당히 유사함

군집 탐색 문제는 '정점'들을 그룹으로 묶는데 비해 클러스터링은 feature들을 벡터 형태로 표현된 인스턴스들을 그룹으로 묶음

 

---

3. 성공적인 군집 탐색 - 배치모형

• 성공적인 군집 탐색을 정의하기 위해 비교 대상으로 배치 모형(Configuration Model)을 살펴본다.
• 주어진 그래프에 대한 배치 모형은 1) 각 정점의 연결성(Degree)을 보존한 상태에서 2) 간선들을 무작위로 재배치해서 얻은 그래프를 의미.
• 배치 모형에서 임의의 두 정점 i, j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례 

 

---

4. 성공적인 군집 탐색 - 군집성

• 군집 탐색의 성공 여부를 판단하기 위해 군집성(Modularity)이 사용됨
• 전제 조건 : 그래프와 (탐색한) 군집들의 집합 S가 주어짐.
• 방법 : 각 군집 s$\in$S가 군집의 성질을 만족하는지를 살펴보기 위해 군집 내부의 간선의 수를 그래프와 배치 모형에서 비교
• 수식
  (앞의 2|E|를 나눠주는 부분은 정규화 : 군집성 크기의 범위를 -1 ~ 1로 제한)

$\frac{1}{2|E|} \sum_{s \in S}$ (그래프에서 군집 s 내부 간선의 수 - 배치 모형에서 군집 s 내부 간선의 수의 기댓값)

배치 모형과 비교해서 그래프에서 군집 내부 간선의 수가 월등히 많을수록 성공한 군집 탐색.

즉, 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단.
보통 군집성이 0.3 ~ 0.7 정도의 값일 때 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있음

 

 

---

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

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

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