Mutual information for the sparse stochastic block model
From MaRDI portal
Publication:6151948
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Viscosity solutions to PDEs (35D40) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) PDEs on infinite-dimensional (e.g., function) spaces (= PDEs in infinitely many variables) (35R15)
Abstract: We consider the problem of recovering the community structure in the stochastic block model with two communities. We aim to describe the mutual information between the observed network and the actual community structure in the sparse regime, where the total number of nodes diverges while the average degree of a given node remains bounded. Our main contributions are a conjecture for the limit of this quantity, which we express in terms of a Hamilton-Jacobi equation posed over a space of probability measures, and a proof that this conjectured limit provides a lower bound for the asymptotic mutual information. The well-posedness of the Hamilton-Jacobi equation is obtained in our companion paper. In the case when links across communities are more likely than links within communities, the asymptotic mutual information is known to be given by a variational formula. We also show that our conjectured limit coincides with this formula in this case.
Recommendations
Cites work
- scientific article; zbMATH DE number 227027 (Why is no real title available?)
- A proof of the block model threshold conjecture
- Asymptotic mutual information for the balanced binary stochastic block model
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection thresholds and the weak Ramanujan property
- Concentration inequalities. A nonasymptotic theory of independence
- Conditional random fields, planted constraint satisfaction, and entropy concentration
- Efficient discovery of overlapping communities in massive networks
- Exact Recovery in the Stochastic Block Model
- Free energy of multi-layer generalized linear models
- Fundamental limits of symmetric low-rank matrix estimation
- Global and Local Information in Clustering Labeled Block Models
- Hamilton-Jacobi equations for finite-rank matrix inference
- Hamilton-Jacobi equations for inference of matrix tensor products
- Hamilton-Jacobi equations for mean-field disordered systems
- Hamilton-Jacobi equations for nonsymmetric matrix inference
- Local algorithms for block models with side information
- Mixed membership stochastic blockmodels
- Mutual information for low-rank even-order symmetric tensor estimation
- On the replica symmetric solution of the \(K\)-sat model
- Random graph models of social networks
- Reconstruction and estimation in the planted partition model
- Spin glass models from the point of view of spin distributions
- Statistical inference of finite-rank tensors
- Stephen Fienberg: Superman of statistics
- Stochastic Blockmodels for Directed Graphs
- Strong replica symmetry in high-dimensional optimal Bayesian inference
- Structure of 1-RSB asymptotic Gibbs measures in the diluted \(p\)-spin models
- Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
- The Sherrington-Kirkpatrick model
- The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
- The phase transition in inhomogeneous random graphs
- The solution of some random NP-hard problems in polynomial expected time
Cited in
(4)- Infinite-dimensional Hamilton-Jacobi equations for statistical inference on sparse graphs
- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Breakdown of a concavity property of mutual information for non-Gaussian channels
- Information theoretic limits of learning a sparse rule
This page was built for publication: Mutual information for the sparse stochastic block model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151948)
