BoostCamp AI Tech - Day23

1. 군집 구조와 군집 탐색 문제

1.1 군집의 정의

다음 조건들을 만족하는 정점들의 집합

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

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

 

위의 사진에서 색이 모두 다른 11개의 군집이 있다.

 

1.2 실제 그래프에서의 군집들

 

 - 온라인 소셜 네트워크의 군집 - 사회적 무리

- 온라인 소셜 네트워크의 군집들이 부정 행위와 관련된 경우도 많다. 아래 사진에서 왼쪽 부정행위에 연루된 계정들이 군집을 형성한다는 것을 발견한 것이다.

- 조직 내의 분란이 소셜 네트워크 상의 군집으로 표현된 경우도 있다. 아래의 그래프는 대학교 가라테 동아리 내 친구 관계를 보여준다. 내분으로 동아리가 둘로 나뉘어 져 두 개의 군집이 형성된 것이다.

- 키워드 - 광고주 그래프에서는 동일한 주제의 키워드들이 군집을 형성한다. 아래 사진은 키워드-광고주 그래프의 인접행렬을 시각화 한 것이고, 원소 중 0은 흰색, 나머지는 검은색으로 표시한 것이다.

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

1.3 군집 탐색 문제(Community Detection Problem)

 

그래프를 여러 군집으로 '잘' 나누는 문제를 말한다. 보통은 각 정점이 한 개의 군집에 속하도록 군집을 나눈다. 비지도 기계학습 문제인 클러스터링(Clustering)과 상당히 유사하다고 한다.

2. 군집 구조의 통계적 유의성과 군집성

 

우선, 성공적인 군집 탐색을 정의하기 위해 배치 모형을 알아보자.

 

2.1 비교대상 : 배치모형(Configuration)

 

 주어진 그래프에 대한 배치 모형은 각 정점의 연결성(Degree)을 보존한 상태에서 간선들을 무작위로 재배치하여서 얻은 그래프를 의미한다.

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