Scalable detection of statistically significant communities and hierarchies, using message passing for modularity
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 08, 2014
- Source ID
- 10.1073/pnas.1409770111
Entities
People
- Cristopher Moore
- Pan Zhang
Organizations
- Air Force Office of Scientific Research
- Santa Fe Institute