Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms.

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