We consider the problem of clustering (or reconstruction) in the stochastic
block model, in the regime where the average degree is constant. For the case
of two clusters with equal sizes, recent results by Mossel, Neeman and Sly, and
by Massoulie, show that reconstructability undergoes a phase transition at the
Kesten-Stigum bound of $\lambda_2^2 d = 1$, where $\lambda_2$ is the second
largest eigenvalue of a related stochastic matrix and $d$ is the average
degree. In this paper, we address the general case of more than two clusters
and/or unbalanced cluster sizes. Our main result is a sufficient condition for
clustering to be impossible, which matches the existing result for two clusters
of equal sizes. A key ingredient in our result is a new connection between
non-reconstructability and non-distinguishability of the block model from an
Erd\H{o}s-R\'enyi model with the same average degree. We also show that it is
some times possible to reconstruct even when $\lambda_2^2 d < 1$. Our results
provide evidence supporting a series of conjectures made by Decelle, Krzkala,
Moore and Zdeborov\'a regarding reconstructability and distinguishability of
stochastic block models (but do not settle them).

在平均度数不变的情况下，考虑了随机块模型中聚类（或重构）的问题。通过新的非重新构建和块模型与具有相同平均度数的 Erdős-Rényi 模型的不可区分性之间的联系，给出了聚类不可能的充分条件。