Scalable detection of statistically significant communities and hierarchies, using message passing for modularity

By Pan Zhang, Cristopher Moore. 2014

183 citations recorded by the source corpus.

Significance Most work on community detection does not address the issue of statistical significance, and many algorithms are prone to overfitting. We address this using tools from statistical physics. Rather than trying to find the partition of a network that maximizes the modularity, our approach seeks the consensus of many high-modularity partitions. We do this with a scalable message-passing algorithm, derived by treating the modularity as a Hamiltonian and applying the cavity method. We show analytically that our algorithm succeeds all the way down to the detectability transition in the stochastic block model; it also performs well on real-world networks. It also provides a principled method for determining the number of groups or hierarchies of communities and subcommunities. Modularity is a popular measure of community structure. However, maximizing the modularity can lead to many competing partitions, with almost the same modularity, that are poorly correlated with each other. It can also produce illusory ‘‘communities’’ in random graphs where none exist. We address this problem by using the modularity as a Hamiltonian at finite temperature and using an efficient belief propagation algorithm to obtain the consensus of many partitions with high modularity, rather than looking for a single partition that maximizes it. We show analytically and numerically that the proposed algorithm works all of the way down to the detectability transition in networks generated by the stochastic block model. It also performs well on real-world networks, revealing large communities in some networks where previous work has claimed no communities exist. Finally we show that by applying our algorithm recursively, subdividing communities until no statistically significant subcommunities can be found, we can detect hierarchical structure in real-world networks more efficiently than previous methods.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Handbook of Big Data (2016, background): “Operations such as minimum spanning trees [18], maximum weight matchings [65], and message passing methods [66] fit into the same framework as well.”
Modular Brain Networks (2015, methodology): “In doing so, we necessarily omitted many methods that may yet prove useful in network neuroscience, including several based on random walks (Delvenne et al. 2010, Pons & Latapy 2005), belief propagation (Zhang & Moore 2014), and phase synchronization (Boccaletti et al. 2007).”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “Related algorithm was discussed recently in the context of modularity-based community detection in [243].”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, background): “The nodes of this network are divided into two groups, with most connections falling within groups and only a few between groups. clustering [10] [11], modularity optimization [12] [13] [14], spectral clustering [15] [16] and statistical inference [17] [18].”
Community detection in networks: A user guide (2016, background): “Indeed, it has been shown that the consensus of many high-modularity partitions, combined with a hierarchical 31 approach, could help to solve resolution problems and to avoid to find communities in random graphs without groups (Zhang and Moore, 2014).”