How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra Thanks: Email: This work is supported in part by NSF CAREER Award CCF-1453261, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Affiliation: Massachusetts Institute of Technology, Department of Mathematics Affiliation: Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Lab William Perry Thanks: Email: Affiliation: Massachusetts Institute of Technology, Department of Mathematics Alexander S. Wein Thanks: Email: This work is supported in part by an NDSEG graduate fellowship. Affiliation: Massachusetts Institute of Technology, Department of Mathematics
Abstract
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, Decelle et al. [DKMZ11] conjectured a sharp threshold for when community detection is possible in the sparse regime. Mossel, Neeman and Sly [MNS14b] and Massoulié [Mas14] proved the conjecture and gave matching algorithms and lower bounds.
原文 arXiv:1511.01473;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.01473v2