Title: A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection,
Abstract: In this paper, we consider the community detection problem under either the
stochastic block model (SBM) assumption or the degree-correlated stochastic
block model (DCSBM) assumption. The modularity maximization formulation for the
community detection problem is NP-hard in general. In this paper, we propose a
sparse and low-rank completely positive relaxation for the modularity
maximization problem, we then develop an efficient row-by-row (RBR) type block
coordinate descent (BCD) algorithm to solve the relaxation and prove an
$\mathcal{O}(1/\sqrt{N})$ convergence rate to a stationary point where $N$ is
the number of iterations. A fast rounding scheme is constructed to retrieve the
community structure from the solution. Non-asymptotic high probability bounds
on the misclassification rate are established to justify our approach. We
further develop an asynchronous parallel RBR algorithm to speed up the
convergence. Extensive numerical experiments on both synthetic and real world
networks show that the proposed approach enjoys advantages in both clustering
accuracy and numerical efficiency. Our numerical results indicate that the
newly proposed method is a quite competitive alternative for community
detection on sparse networks with over 50 million nodes.