Abstract:
|
Community detection in networks, the problem of finding groups of nodes that have more connections to each other than to the rest of the network, has received a lot of attention in the literature, but many methods only allow for a node to belong to exactly one community. In practice, nodes in a network may belong to multiple communities. Here we propose a new efficient algorithm for overlapping community detection based on sparse principal component analysis. The algorithm has a computational cost similar to that of estimating the largest eigenvectors of the adjacency matrix, and does not require an additional clustering step like spectral clustering techniques. We show that our method is consistent in selecting the community memberships under an overlapping version of the stochastic blockmodel and evaluate the method empirically on simulated and real-world networks, showing good statistical performance and computational efficiency.
|