We present a novel hierarchical graph clustering algorithm inspired by modularity-based clustering techniques. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs. We prove that this distance is reducible, which enables the use of the nearest-neighbor chain to speed up the agglomeration. The output of the algorithm is a regular dendrogram, which reveals the multi-scale structure of the graph. The results are illustrated on both synthetic and real datasets.
Most graph clustering algorithms are not hierarchical and rely on some resolution parameter that allows one to adapt the clustering to the dataset and to the intended purpose @cite_8 @cite_22 @cite_19 @cite_16 . This parameter is hard to adjust in practice, which motivates the present work.
@cite_19 @cite_16 @cite_22 @cite_8
2963302977 2416738288 2025543856
Most methods proposed to uncover communities in complex networks rely on combinatorial graph properties. Usually an edge-counting quality function, such as modularity, is optimized over all partitions of the graph compared against a null random graph model. Here we introduce a systematic dynamical framework to design and analyze a wide variety of quality functions for community detection. The quality of a partition is measured by its Markov Stability, a time-parametrized function defined in terms of the statistical properties of a Markov process taking place on the graph. The Markov process provides a dynamical sweeping across all scales in the graph, and the time scale is an intrinsic parameter that uncovers communities at different resolutions. This dynamic-based community detection leads to a compound optimization, which favours communities of comparable centrality (as defined by the stationary distribution), and provides a unifying framework for spectral algorithms, as well as different heuristics for community detection, including versions of modularity and Potts model. Our dynamic framework creates a systematic link between different stochastic dynamics and their corresponding notions of optimal communities under distinct (node and edge) centralities. We show that the Markov Stability can be computed efficiently to find multi-scale community structure in large networks. We demonstrate an exact equivalence between two widely used methods of community detection in networks, the method of modularity maximization in its generalized form which incorporates a resolution parameter controlling the size of the communities discovered, and the method of maximum likelihood applied to the special case of the stochastic block model known as the planted partition model, in which all communities in a network are assumed to have statistically similar properties. Among other things, this equivalence provides a mathematically principled derivation of the modularity function, clarifies the conditions and assumptions of its use, and gives an explicit formula for the optimal value of the resolution parameter. Institute for Theoretical Physics, University of Bremen, Otto-Hahn-Allee, D-28359 Bremen, Germany(Dated: February 3, 2008)Starting from a general ansatz, we show how community detection can be interpreted as ﬁnding theground state of an inﬁnite range spin glass. Our approach applies to weighted and directed networksalike. It contains the at hoc introduced quality function from [1] and the modularity Q as deﬁnedby Newman and Girvan [2] as special cases. The community structure of the network is interpretedas the spin conﬁguration that minimizes the energy of the spin glass with the spin states being thecommunity indices. We elucidate the properties of the ground state conﬁguration to give a concisedeﬁnition of communities as cohesive subgroups in networks that is adaptive to the speciﬁc class ofnetwork under study. Further we show, how hierarchies and overlap in the community structure canbe detected. Computationally eﬀective local update rules for optimization procedures to ﬁnd theground state are given. We show how the ansatz may be used to discover the community around agiven node without detecting all communities in the full network and we give benchmarks for theperformance of this extension. Finally, we give expectation values for the modularity of randomgraphs, which can be used in the assessment of statistical signiﬁcance of community structure.