Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime @math A critical parameter is the effective signal-to-noise ratio @math , with @math corresponding to the Kesten-Stigum threshold. We show that a belief propagation algorithm achieves weak recovery if @math , beyond the Kesten-Stigum threshold by a factor of @math The belief propagation algorithm only needs to run for @math iterations, with the total time complexity @math , where @math is the iterated logarithm of @math Conversely, if @math , no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying power iteration to the non-backtracking matrix of the graph is shown to attain weak recovery if and only if @math . In addition, the belief propagation algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all @math where @math is a function of @math .
The binary symmetric stochastic block model deals with a random graph of @math vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability @math within clusters and @math across clusters. In the asymptotic regime of @math and @math for fixed @math and @math , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe14 . Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to @math .