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 (17)

• Fast unfolding of communities in large 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
• Finding statistically significant communities in networks
• Consensus clustering in complex 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
• Statistical Physics of Hard Optimization Problems

Cited by in corpus (15)

• Community detection in networks: A user guide
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Hierarchical benchmark graphs for testing community detection algorithms
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Multi-scale Laplacian community detection in heterogeneous networks
• 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
• Community Detection on Networks with Ricci Flow
• Detecting network communities via greedy expanding based on local superiority index
• On the accuracy of message-passing approaches to percolation in complex networks
• Network topology mapping of Chemical Compounds Space