Density Evolution in the Degree-correlated Stochastic Block Model

Understand

There is a recent surge of interest in identifying the sharp recovery thresholds for cluster recovery under the stochastic block model.

• In this paper, we address the more refined question of how many vertices that will be misclassified on average.
• We consider the binary form of the stochastic block model, where $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 clusters.
• Suppose that as $n \to \infty$, $a= b+ \mu \sqrt{ b} $, $c=b+ \nu \sqrt{ b} $ for two fixed constants $\mu, \nu$, and $b \to \infty$ with $b=n^{o(1)}$.