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 O(1/ √ 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. 1. Introduction. The community detection problem aims to retrieve the underlying community/cluster structure of a network from the observed nodes connection data. This network structure inference technique has been reinvigorated because of the modern applications of large scale networks, including social networks, energy distribution networks and economic networks, etc. The standard frameworks for studying community detection in networks are the stochastic block model (SBM) [14] and the degree-correlated stochastic block model (DCSBM) [17, 8] . Both of them are random graph models based on an underlying disjoint community structure. To solve the community detection problem, there have been a variety of greedy methods which aim to maximize some quality function of the community structure; see [33] and the references therein. Although these methods are numerically efficient, their theoretical analysis is still largely missing. An important class of methods for community detection are the so-called spectral clustering methods, which exploit either the spectral decomposition of the adjacency matrix [21, 30, 16] , or the normalized adjacency or graph Laplacian matrix [8, 7, 13, 29, 3, 27] . A significant advantage of the spectral clustering methods is that they are numerically efficient and scalable. Although many of them are shown to be statistically consistent with the SBM and the DCSBM conditions under certain conditions, their numerical performance on synthetic and real data does not fully support such hypothesis. This can also be observed in the numerical experiments where the spectral methods SCORE [16] and OCCAM [35] are tested. It is worth mentioning that spectral clustering methods may fail to detect the communities for large sparse networks. Another closely connected class of methods are based on the nonnegative matrix factorization (NMF) methods. In [10] , an interesting equivalence is shown between some specific NMF-based methods, the kernel K-means method and a specific spectral clustering method.
J. Zhang et al. REF study the community detection problem in the stochastic block model (SBM) or the degree-correlated SBM assumption and propose a modularity maximization problem which is sparse and low-rank completely positive relaxation.
A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection
ArXiv
ArXiv
Mathematics Computer Science