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 (31)

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

This page was built for publication: Asymptotic mutual information for the balanced binary stochastic block model