다양한 실제 네트워크에서 클러스터링 계수와 클러스터 경향의 상관관계 분석

Abstract

다양한 응용 분야에 적용이 가능한 클러스터링 기법은 많은 관심을 받아왔으며, 최근에는 소셜 네트워크 서비스의 폭발적인 증가로 그래프 클러스터링에 대한 중요성이 널리 인식되고 있다. 하지만 모든 데이터 셋이 의미 있는 클러스터 구조를 갖는 것은 아니며 대용량 데이터 셋에서 클러스터링 알고리즘의 목적함수를 최적화 하는 것이 NP-hard이기 때문에 클러스터링 수행 전에 데이터 셋의 클러스터 경향을 판단하는 것은 중요하다. 본 논문에서는 클러스터링 계수와 클러스터 경향의 상관관계를 다양한 실제 그래프 데이터 셋, 그래프 클러스터링 알고리즘, 그리고 클러스터 질적 평가방법을 통해 실험적으로 분석한다. 먼저 각 그래프 데이터 셋에 세 개의 대표적인 그래프 클러스터링 알고리즘(Infomap, Label propagation, Multi-level modularity)을 적용하여 클러스터들을 발견한다. 그리고 발견된 클러스터 각각에 대해 세 가지의 대표적인 클러스터 질적 평가 방법(Internal density, Conductance, Modularity)을 적용하여 클러스터 경향을 평가한다. 마지막으로 클러스터링 계수와 클러스터 경향의 상관관계를 피어슨 상관 계수를 통해 분석한다. 7종의 14개 실제 그래프 데이터 셋에 대해 실험한 결과 클러스터링 계수와 클러스터 경향이 서로 강한 상관관계를 갖는 것을 확인하였다.