Dependence clustering, a method revealing community structure with group dependence

Abstract

We propose a clustering method maximizing a new measure called "group dependence." Group dependence quantifies how precise a certain division of a graph is in terms of dependence distance. Built upon statistical dependence measure between points driven by Markovian transitions, group dependence incorporates the geometric structure of input data. Besides capturing degrees of positive dependence and coherence for a group division, group dependence inherently supplies the proposed clustering method with a definite decision on the depth of division. We provide an optimality aspect of the method as theoretical justification in consideration of posterior transition probabilities of input data. Illustrating its procedure using data from a known structure, we demonstrate its performance in the clustering task of real-world data sets, Amazon, DBLP, and YouTube, in comparison with selected clustering algorithms. We show that the proposed method outperforms the selected methods in reasonable settings: in particular, the proposed method surpasses modularity clustering in terms of normalized mutual information. We also show that the proposed method reveals additional insights on community structure detection according to its connectivity scale parameter. (C) 2014 Elsevier B.V. All rights reserved.