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

(83)

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

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)