Density Evolution in the Degree-correlated Stochastic Block Model

The problem of cluster recovery under the stochastic block model has been intensely studied in statistics [24, 44, 6, 8, 47, 19], computer science (where it is known as the planted partition problem) [17, 25, 13, 31, 11, 12, 9, 4, 10], and theoretical statistical physics [14, 48, 15]. In the simplest binary form, the stochastic block model assumes that n vertices are partitioned into two clusters with edge probability a/n within the first cluster, c/n within the second cluster, and b/n across the two clusters. The goal is to reconstruct the underlying clusters from the observation of the graph. Different reconstruction goals can be considered depending on how the model parameters a, b, c scale with n (See [2] for more discussions): - Exact recovery (strong consistency). If the average degree is Ω(log n), it is possible to exactly recover the clusters (up to a permutation of cluster indices) with high probability.