A proof of the block model threshold conjecture

DOI10.1007/s00493-016-3238-8zbMath1424.05272arXiv1311.4115WikidataQ123278351 ScholiaQ123278351MaRDI QIDQ1715062

Allan Sly, Elchanan Mossel, Joe Neeman

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

random graph; stochastic block model; planted partition model

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

Related Items

Unnamed Item, On the Complexity of Random Satisfiability Problems with Planted Solutions, Statistical inference on random dot product graphs: a survey, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Unnamed Item, Unnamed Item, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Find Your Place: Simple Distributed Algorithms for Community Detection, Optimal couplings between sparse block models, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Community detection in sparse networks via Grothendieck's inequality, Finding one community in a sparse graph, Information-theoretic thresholds from the cavity method, MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass, Notes on computational-to-statistical gaps: predictions using statistical physics, Bethe states of random factor graphs, On semidefinite relaxations for the block model, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Charting the replica symmetric phase, Random Laplacian matrices and convex relaxations, Application of the information-percolation method to reconstruction problems on graphs, Optimal rates for community estimation in the weighted stochastic block model, Entrywise eigenvector analysis of random matrices with low expected rank, Step-by-step community detection in volume-regular graphs, Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Exact recovery in the Ising blockmodel, Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels, Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks, Disentangling group and link persistence in dynamic stochastic block models