다양한 실제 네트워크에서 클러스터링 계수와 클러스터 경향의 상관관계 분석 (Correlation Analysis between Clustering Coefficient and Clusterability in Various Real-World Networks)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 31권 / 2호 / 95 ~ 103페이지
· 저자명 : 김정은, 이재길

초록

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

영어초록

Clustering has attracted significant attention during the past several years since it is applicable to a wide range of applications. Recently, as social network services became popular, the importance of graph clustering has been widely recognized. However, not all data sets have meaningful cluster structures, and optimizing the objective function of the clustering algorithm is NP-hard. Thus, a preliminary assessment of clusterability of massive data sets is crucial. In this paper, we empirically verified the correlation between clustering coefficient and clusterability using various real-world networks, graph clustering algorithms, and cluster goodness metrics. First, we discovered clusters in each data set by adopting three representative graph clustering algorithms such as Infomap, label propagation, and modularity maximization. Then, we evaluated clusterability based on three representative cluster goodness metrics such as internal density, conductance, and modularity. Finally, we analyzed the correlation between clustering coefficient and clusterability in terms of Pearson correlation coefficient. The experimental results in 14 real-world networks demonstrated that clustering coefficient and clusterability have strong correlation.

참고자료

· 없음