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

Abstract

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 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.

References in corpus (37)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Community detection in complex networks using Extremal Optimization
• Finding statistically significant communities in networks
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Consensus clustering in complex networks
• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Extracting the hierarchical organization of complex systems
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Community Detection as an Inference Problem
• Reconstruction on trees and spin glass transition
• Stochastic Block Models and Reconstruction
• The Nishimori line and Bayesian Statistics
• Statistical significance of communities in networks
• Model Selection for Degree-corrected Block Models
• Robust reconstruction on trees is determined by the second eigenvalue
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• A testing based extraction algorithm for identifying significant communities in networks
• Conjecture on the maximum cut and bisection width in random regular graphs
• Statistical Physics of Hard Optimization Problems
• Belief propagation for graph partitioning

Cited by in corpus (54)

• Community detection in networks: A user guide
• Statistical physics of inference: Thresholds and algorithms
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Element-centric clustering comparison unifies overlaps and hierarchy
• A Clarified Typology of Core-Periphery Structure in Networks
• Evaluating accuracy of community detection using the relative normalized mutual information
• Statistical inference of assortative community structures
• Block Models and Personalized PageRank
• Core-periphery structure requires something else in the network
• Consistency of community structure in complex networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Disentangling bipartite and core-periphery structure in financial networks
• A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Revealing consensus and dissensus between network partitions
• Information-theoretic thresholds for community detection in sparse networks
• Cross-validation estimate of the number of clusters in a network
• Universality of the stochastic block model
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• A generalised significance test for individual communities in networks
• Representative community divisions of networks
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• Core of communities in bipartite networks
• Algorithmic detectability threshold of the stochastic block model
• Fast Maximum Likelihood estimation via Equilibrium Expectation for Large Network Data
• Comparative analysis on the selection of number of clusters in community detection
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Weighted Community Detection and Data Clustering Using Message Passing
• Total variation based community detection using a nonlinear optimization approach
• Multiple phases in modularity-based community detection
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Multi-scale Laplacian community detection in heterogeneous networks
• Performance of a community detection algorithm based on semidefinite programming
• Deep Graph Clustering via Mutual Information Maximization and Mixture Model
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Detectability thresholds of general modular graphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Detecting network communities via greedy expanding based on local superiority index
• Community Detection on Networks with Ricci Flow
• Adjusted chi-square test for degree-corrected block models
• Detecting Statistically Significant Communities
• Financial Contagion in a Generalized Stochastic Block Model
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• The Atlas for the Aspiring Network Scientist
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Network topology mapping of Chemical Compounds Space
• On the accuracy of message-passing approaches to percolation in complex networks
• Thermodynamics of the Minimum Description Length on Community Detection