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 .
This paper studies the problem of detecting the presence of a small dense community planted in a large Erd o s-R 'enyi random graph @math , where the edge probability within the community exceeds @math by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size @math grows and the graph becomes sparser according to @math , there exists a critical value of @math , below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest @math -subgraph.