Stochastic Block Models and Reconstruction

Abstract

The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on $n$ nodes with two equal-sized clusters, with an between-class edge probability of $q$ and a within-class edge probability of $p$. Although most of the literature on this model has focused on the case of increasing degrees (ie.\ $pn,qn\to \infty$ as $n\to \infty$), the sparse case $p,q=O(1/n)$ is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if $p=a/n$ and $q=b/n$, then Decelle et al.\ conjectured that it is possible to cluster in a way correlated with the true partition if $(a-b{)}^2>2(a+b)$, and impossible if $(a-b{)}^2<2(a+b)$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $(a-b{)}^2>C(a+b)$ for some sufficiently large $C$. We prove half of their prediction, showing that it is indeed impossible to cluster if $(a-b{)}^2<2(a+b)$. Furthermore we show that it is impossible even to estimate the model parameters from the graph when $(a-b{)}^2<2(a+b)$; on the other hand, we provide a simple and efficient algorithm for estimating $a$ and $b$ when $(a-b{)}^2>2(a+b)$. Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.

References in corpus (2)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Phase transition in the detection of modules in sparse networks

Cited by in corpus (68)

• Spectral redemption: clustering sparse networks
• Matrix estimation by Universal Singular Value Thresholding
• Spectral methods for network community detection and graph partitioning
• Pseudo-likelihood methods for community detection in large sparse networks
• Graph Frequency Analysis of Brain Signals
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Phase Transitions in Semidefinite Relaxations
• Model Selection for Degree-corrected Block Models
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Community Detection in the Labelled Stochastic Block Model
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• A Tensor Approach to Learning Mixed Membership Community Models
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Estimating the number of communities in networks by spectral methods
• Information-theoretic thresholds for community detection in sparse networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Testing for Global Network Structure Using Small Subgraph Statistics
• Information-theoretic thresholds for community detection in sparse networks
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Finding communities in sparse networks
• Community Detection via Random and Adaptive Sampling
• Consistency Thresholds for the Planted Bisection Model
• Community Detection in Networks using Graph Distance
• Non-Reconstructability in the Stochastic Block Model
• Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Recovering communities in the general stochastic block model without knowing the parameters
• Bayesian estimation from few samples: community detection and related problems
• Community Detection in Degree-Corrected Block Models
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Clustering from Sparse Pairwise Measurements
• Streaming, Memory Limited Algorithms for Community Detection
• Distributed Community Detection in Dynamic Graphs
• On the Duality between Network Flows and Network Lasso
• A unified framework for spectral clustering in sparse graphs
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• Learning Communities in the Presence of Errors
• A Semi-Definite Programming approach to low dimensional embedding for unsupervised clustering
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Recovering Structured Probability Matrices
• Statistical Limits of Convex Relaxations
• Efficient inference in stochastic block models with vertex labels
• Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction
• Federated Learning From Big Data Over Networks
• Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
• Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
• Community Detection with Node Attributes and its Generalization
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times
• The minimum bisection in the planted bisection model
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
• Uniqueness of communities in regular stochastic block models
• The Power of Side-information in Subgraph Detection
• Scaling Submodular Optimization Approaches for Control Applications in Networked Systems
• Information-theoretic Limits for Community Detection in Network Models
• Exact Inference with Latent Variables in an Arbitrary Domain
• Quantifying Filter Bubbles: Analyzing Surprise in Elections
• How Well Do Local Algorithms Solve Semidefinite Programs?
• Reconstruction in the Labeled Stochastic Block Model
• A Semidefinite Program for Structured Blockmodels