Source-linked AI summary
Phase transition in the detection of modules in sparse networks
Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová
TL;DR
The paper asks when sparse-network topology supports recovery of hidden groups and model parameters. It uses cavity-method Bayesian inference to characterize detectability transitions and derive belief-propagation learning, finding undetectable, detectable-but-hard, and easy regimes.
Problem
The paper studies how to detect communities or functional modules and learn stochastic block-model parameters when only the network adjacency matrix is observed.
Method
Using the cavity method and belief propagation, the paper analyzes the full Bayesian distribution of group assignments and computes parameter-learning and marginal-inference quantities asymptotically exactly.
Results
The analysis identifies a transition from detectable to undetectable phases, with some detectable cases splitting into algorithmically hard and easy regions.
Takeaways & Limitations
The resulting algorithm can learn group counts, group sizes, affinity parameters, and node assignments in large sparse networks, while providing marginal probabilities that quantify module significance.
Takeaways & Limitations
The message equations assume conditional independence between each node’s neighbors and neglect lower-order terms, while the parameter prior is taken to be uniform.
Abstract
from arXiv · showhide
We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks. Our results are also applicable to detection of functional modules, partitions, and colorings in noisy planted models. Using a cavity method analysis, we unveil a phase transition from a region where the original group assignment is undetectable to one where detection is possible. In some cases, the detectable region splits into an algorithmically hard region and an easy one. Our approach naturally translates into a practical algorithm for detecting modules in sparse networks, and learning the parameters of the underlying model.