Reconstruction and estimation in the planted partition model

• 成果类型: Article
• 署名作者: Mossel, Elchanan; Neeman, Joe; Sly, Allan
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley; Australian National University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-014-0576-6
• 发表日期: 2015
• 页码: 431-461
• 关键词: stochastic blockmodels; graphs; algorithms

摘要

The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on nodes with two equal-sized clusters, with an between-class edge probability of and a within-class edge probability of . Although most of the literature on this model has focused on the case of increasing degrees (ie. as ), the sparse case is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborova 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 and , then Decelle et al. conjectured that it is possible to cluster in a way correlated with the true partition if , and impossible if . By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if for some sufficiently large . We prove half of their prediction, showing that it is indeed impossible to cluster if . Furthermore we show that it is impossible even to estimate the model parameters from the graph when ; on the other hand, we provide a simple and efficient algorithm for estimating and when . Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.