Asymptotic mutual information for the balanced binary stochastic block model

DOI10.1093/imaiai/iaw017zbMath1383.62021arXiv1507.08685OpenAlexW2565889208MaRDI QIDQ4603702

Yash Deshpande, Emmanuel Abbe, Andrea Montanari

Publication date: 19 February 2018

Published in: Information and Inference (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.08685

zbMATH Keywords

mutual informationcommunity detectionstochastic block modelapproximate message passing

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Statistical aspects of information-theoretic topics (62B10)

Related Items

Approximate message passing algorithms for rotationally invariant matrices, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Computational barriers to estimation from low-degree polynomials, Information-theoretic thresholds from the cavity method, Information theoretic limits of learning a sparse rule, Estimation of low-rank matrices via approximate message passing, An information-percolation bound for spin synchronization on general graphs, Statistical thresholds for tensor PCA, Application of the information-percolation method to reconstruction problems on graphs, Statistical limits of spiked tensor models, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, Fundamental limits of detection in the spiked Wigner model, Entrywise eigenvector analysis of random matrices with low expected rank, Mutual information for the sparse stochastic block model, Phase transitions in semidefinite relaxations, Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Optimizing mean field spin glasses with external field, Notes on computational-to-statistical gaps: predictions using statistical physics, TAP free energy, spin glasses and variational inference, Fundamental limits of symmetric low-rank matrix estimation, Phase transition in random tensors with multiple independent spikes, Community Detection and Stochastic Block Models, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Universality of approximate message passing algorithms, The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference, On the computational tractability of statistical estimation on amenable graphs, Partial recovery bounds for clustering with the relaxed \(K\)-means, Phase transition in the spiked random tensor with Rademacher prior, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, A Unifying Tutorial on Approximate Message Passing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Spectral clustering and the high-dimensional stochastic blockmodel
• Exact solution of the gauge symmetric \(p\)-spin glass model on a complete graph
• A generalization of the Lindeberg principle
• Finding one community in a sparse graph
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• The Metropolis algorithm for graph bisection
• Broken replica symmetry bounds in the mean field spin glass model
• Broadcasting on trees and the Ising model.
• Universality in polytope phase transitions and message passing algorithms
• Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
• Stochastic blockmodels with a growing number of classes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Exact Recovery in the Stochastic Block Model
• The solution of some random NP-hard problems in polynomial expected time
• Mixed membership stochastic blockmodels
• Mutual Information and Minimum Mean-Square Error in Gaussian Channels
• Graph Partitioning via Adaptive Spectral Techniques
• An Introduction to Random Matrices
• The Generalized Area Theorem and Some of its Consequences
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Community detection thresholds and the weak Ramanujan property
• Applications of the Lindeberg Principle in Communications and Statistical Learning
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing