A Nearly-Linear Time Algorithm for Exact Community Recovery in Stochastic Block Model

Learning community structures in graphs that are randomly generated by stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the problem of exactly recovering the communities in a binary symmetric SBM, where a graph of n vertices is partitioned into two equal-sized communities and the vertices are connected with probability p = α log(n)/n within communities and q = β log(n)/n across communities for some α > β > 0. We propose a two-stage iterative algorithm for solving this problem, which employs the power method with a random starting point in the first stage and turns to a generalized power method that can identify the communities in a finite number of iterations in the second stage. It is shown that for any fixed α and β such that √ α -√ β > √ 2, which is known to be the information-theoretic limit for exact recovery, the proposed algorithm exactly identifies the underlying communities in Õ(n) time with probability tending to one as n → ∞. We also present numerical results of the proposed algorithm to support and complement our theoretical development.