Asymptotic mutual information for the balanced binary stochastic block model

DOI10.1093/IMAIAI/IAW017zbMATH Open1383.62021arXiv1507.08685OpenAlexW2565889208MaRDI QIDQ4603702FDOQ4603702

Authors: Yash Deshpande, Emmanuel Abbe, Andrea Montanari 

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph $G$ from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit `single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and --in particular-- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.

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

Recommendations

• Community detection and stochastic block models
• Information-theoretic thresholds from the cavity method
• Global and local information in clustering labeled block models
• Community detection and stochastic block models: recent developments
• Information-theoretic thresholds from the cavity method

zbMATH Keywords

stochastic block modelcommunity detectionmutual informationapproximate message passing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (34)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603702)