Dependence clustering

네트워크 구조를 이루고 있는 데이터 중에는 아래 그림과 같이 내부의 커뮤니티 구조 (community structure)를 가지는 경우가 있다. 이러한 데이터는 기존의 일반적인 클러스터링 기법 (예: k-means, DBSCAN, etc)으로는 커뮤니티 구조를 반영한 클러스터링 결과를 얻기가 힘들다. 

Fig. 1. from (Newman, 2006)^[각주:1]

커뮤니티 구조를 반영하는 클러스터링 알고리즘을 커뮤니티 탐지 (community detection) 알고리즘이라고도 부른다. 커뮤니티 탐지 알고리즘 중 가장 유명한 알고리즘은 Newman (2006)에서 제시한 Modularity-based clustering이 있다. Modularity (응집성)은 네트워크 내에 link (or edge)로 연결된 node (or vertice)들이 소규모의 다른 커뮤니티를 이루며 얼마나 더 밀집되어 있는가를 측정하는 척도이다. 

(나머지 추후 작성, 첨부파일 참고)

20160824_Dependence Clustering.pptx

1. Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23), 8577-8582. [본문으로]