  We consider the problem of community detection in the Stochastic Block Model
with a finite number $K$ of communities of sizes linearly growing with the
network size $n$. This model consists in a random graph such that each pair of
vertices is connected independently with probability $p$ within communities and
$q$ across communities. One observes a realization of this random graph, and
the objective is to reconstruct the communities from this observation. We show
that under spectral algorithms, the number of misclassified vertices does not
exceed $s$ with high probability as $n$ grows large, whenever $pn=\omega(1)$,
$s=o(n)$ and \begin{equation*} \lim\inf_{n\to\infty} {n(\alpha_1 p+\alpha_2
q-(\alpha_1 + \alpha_2)p^{\frac{\alpha_1}{\alpha_1 +
\alpha_2}}q^{\frac{\alpha_2}{\alpha_1 + \alpha_2}})\over \log (\frac{n}{s})}
>1,\quad\quad(1) \end{equation*} where $\alpha_1$ and $\alpha_2$ denote the
(fixed) proportions of vertices in the two smallest communities. In view of
recent work by Abbe et al. and Mossel et al., this establishes that the
proposed spectral algorithms are able to exactly recover communities whenever
this is at all possible in the case of networks with two communities with equal
sizes. We conjecture that condition (1) is actually necessary to obtain less
than $s$ misclassified vertices asymptotically, which would establish the
optimality of spectral method in more general scenarios.
