Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms

Understand

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.