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

arXiv: https://arxiv.org/abs/1403.5787 · HTML: https://mlsanity.com/paper/1403.5787/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2014.

## Built on by (most cited first, 16 of 16)

- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [qecGPT: decoding Quantum Error-correcting Codes with Generative Pre-trained Transformers](https://mlsanity.com/paper/2307.09025/) (2023)
- [Community Detection in the Stochastic Block Model by Mixed Integer Programming](https://mlsanity.com/paper/2101.12336/) (2021)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Deep Graph Clustering via Mutual Information Maximization and Mixture Model](https://mlsanity.com/paper/2205.05168/) (2022)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [Inverse Knowledge Search over Verifiable Reasoning: Synthesizing a Scientific Encyclopedia from a Long Chains-of-Thought Knowledge Base](https://mlsanity.com/paper/2510.26854/) (2025)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)
- [Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models](https://mlsanity.com/paper/2403.19516/) (2024)
- [Robust Markov stability for community detection at a scale learned based on the structure](https://mlsanity.com/paper/2504.11621/) (2025)
- [Graph energy as a measure of community detectability in networks](https://mlsanity.com/paper/2601.05065/) (2026)

## Abstract (arXiv)

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.