Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
arXiv:1902.07273
Abstract
We rigorously derive a single-letter variational expression for the mutual information of the asymmetric two-groups stochastic block model in the dense graph regime. Existing proofs in the literature are indirect, as they involve mapping the model to a rank-one matrix estimation problem whose mutual information is then determined by a combination of methods (e.g., interpolation, cavity, algorithmic, spatial coupling). In this contribution we provide a self-contained direct method using only the recently introduced adaptive interpolation method.
References in corpus (11)
- Community detection in graphs
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- The phase transition in inhomogeneous random graphs
- A General Formalism for Inhomogeneous Random Graphs
- Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
- An Extended Variational Principle for the SK Spin-Glass Model
- Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
- Information-theoretic thresholds from the cavity method
- A note on classical ground state energies
- Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method