  Community detection in graphs that are generated according to stochastic
block models (SBMs) has received much attention lately. In this paper, we focus
on the binary symmetric SBM -- in which a graph of $n$ vertices is randomly
generated by first partitioning the vertices into two equal-sized communities
and then connecting each pair of vertices with probability that depends on
their community memberships -- and study the associated exact community
recovery problem. Although the maximum-likelihood formulation of the problem is
non-convex and discrete, we propose to tackle it using a popular iterative
method called projected power iterations. To ensure fast convergence of the
method, we initialize it using a point that is generated by another iterative
method called orthogonal iterations, which is a classic method for computing
invariant subspaces of a symmetric matrix. We show that in the logarithmic
sparsity regime of the problem, with high probability the proposed two-stage
method can exactly recover the two communities down to the
information-theoretic limit in $\mathcal{O}(n\log^2n/\log\log n)$ time, which
is competitive with a host of existing state-of-the-art methods that have the
same recovery performance. We also conduct numerical experiments on both
synthetic and real data sets to demonstrate the efficacy of our proposed method
and complement our theoretical development.
