查看文章

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 Zdeborová 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 …