A proof of the block model threshold conjecture

DOI10.1007/S00493-016-3238-8MaRDI QIDQ1715062zbMATH OpenOpenAlexWikidataFDO

Authors Elchanan Mossel, Joe Neeman, Allan Sly

Publication date 1 February 2019

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

stochastic block modelrandom graphplanted partition model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph with two equal-sized clusters, with a between-class edge probability of $q$ and a within-class edge probability of $p$. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov'a 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$, $s=(a-b)/2$ and $p=(a+b)/2$ then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if $s^2>p$ and impossible if $s^2<p$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $s^2>Cplnp$ for some sufficiently large $C$. In a previous work, we proved that indeed it is information theoretically impossible to to cluster if $s^2<p$ and furthermore it is information theoretically impossible to even estimate the model parameters from the graph when $s^2<p$. Here we complete the proof of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when $s^2>p$. A different independent proof of the same result was recently obtained by Laurent Massoulie.

Recommendations

• Proof of the achievability conjectures for the general stochastic block model
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• Publication:3033152
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• On the chromatic number in the stochastic block model
• An exact threshold theorem for random graphs and the node-packing problem
• scientific article; zbMATH DE number 1789844
• The Maximum Block Size of Critical Random Graphs
• Blocks in constrained random graphs with fixed average degree
• Further evidence for conjectures in block theory.

Cited in

(80)

• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Proof of the achievability conjectures for the general stochastic block model
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Step-by-step community detection in volume-regular graphs
• On the complexity of random satisfiability problems with planted solutions
• Community detection in the sparse hypergraph stochastic block model
• Strong consistency, graph Laplacians, and the stochastic block model
• Joint community detection and rotational synchronization via semidefinite programming
• Bethe states of random factor graphs
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Detecting a planted community in an inhomogeneous random graph
• Powerful multiple testing of paired null hypotheses using a latent graph model
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Outliers in spectrum of sparse Wigner matrices
• Testing community structure for hypergraphs
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Exact recovery in the Ising blockmodel
• Belief propagation, robust reconstruction and optimal recovery of block models
• Iterative algorithm for discrete structure recovery
• Matched bipartite block model with covariates
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Optimal rates for community estimation in the weighted stochastic block model
• Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
• On semidefinite relaxations for the block model
• Graph powering and spectral robustness
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Estimating the number of communities by spectral methods
• Non-backtracking spectrum of degree-corrected stochastic block models
• Disentangling group and link persistence in dynamic stochastic block models
• Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Statistical inference on random dot product graphs: a survey
• Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Charting the replica symmetric phase
• Charting the replica symmetric phase
• Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
• Application of the information-percolation method to reconstruction problems on graphs
• Random Laplacian matrices and convex relaxations
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Global and individualized community detection in inhomogeneous multilayer networks
• Universal latent space model fitting for large networks with edge covariates
• Average whenever you meet: opportunistic protocols for community detection
• On the computational tractability of statistical estimation on amenable graphs
• A note on probably certifiably correct algorithms
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Community detection in sparse networks via Grothendieck's inequality
• The structure of Gaussian minimal bubbles
• scientific article; zbMATH DE number 7307464 (Why is no real title available?)
• The planted matching problem: sharp threshold and infinite-order phase transition
• Finding one community in a sparse graph
• Global and local information in clustering labeled block models
• Community detection thresholds and the weak Ramanujan property
• Entrywise eigenvector analysis of random matrices with low expected rank
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Mutual information for the sparse stochastic block model
• Inference in balanced community modulated recursive trees
• Community Detection in Censored Hypergraph
• Optimal couplings between sparse block models
• scientific article; zbMATH DE number 7415091 (Why is no real title available?)
• Pair-matching: link prediction with adaptive queries
• Computational lower bounds for graphon estimation via low-degree polynomials
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Searching for (sharp) thresholds in random structures: where are we now?
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Bad local minima exist in the stochastic block model
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
• Compressive sensing for cut improvement and local clustering
• A compressed sensing based least squares approach to semi-supervised local cluster extraction
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Combinatorial statistics and the sciences
• Eigenvalues of the non-backtracking operator detached from the bulk

This page was built for publication: A proof of the block model threshold conjecture

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