Proof of the Achievability Conjectures for the General Stochastic Block Model

DOI10.1002/cpa.21719zbMath1394.62082OpenAlexW2766650626WikidataQ122928098 ScholiaQ122928098MaRDI QIDQ4575511

Emmanuel Abbe, Colin Sandon

Publication date: 13 July 2018

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/cpa.21719

zbMATH Keywords

informationclusterspolynomial timeachievability conjectureacyclic belief propagation (ABP)general stochastic block model

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of design theory to circuits and networks (94C30)

Related Items (26)

Testing community structure for hypergraphs ⋮ A likelihood-ratio type test for stochastic block models with bounded degrees ⋮ Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Unnamed Item ⋮ Local law and Tracy-Widom limit for sparse stochastic block models ⋮ Community detection in the sparse hypergraph stochastic block model ⋮ Combinatorial statistics and the sciences ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Learning sparse graphons and the generalized Kesten-Stigum threshold ⋮ Non-backtracking spectra of weighted inhomogeneous random graphs ⋮ Step-by-step community detection in volume-regular graphs ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Bethe states of random factor graphs ⋮ Charting the replica symmetric phase ⋮ Community Detection and Stochastic Block Models ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ On the computational tractability of statistical estimation on amenable graphs ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Spectral clustering revisited: information hidden in the Fiedler vector ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Algorithmic thresholds for tensor PCA ⋮ Unnamed Item ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Global and individualized community detection in inhomogeneous multilayer networks ⋮ Graph Powering and Spectral Robustness ⋮ Depth separations in neural networks: what is actually being separated?

This page was built for publication: Proof of the Achievability Conjectures for the General Stochastic Block Model