Detecting Overlapping Communities in Networks Using Spectral Methods
Yuan Zhang, Elizaveta Levina, Ji Zhu
Abstract
Community detection has been well studied in network analysis, but the more realistic case of overlapping communities remains a challenge. Here we propose a general, flexible, and interpretable generative model for overlapping communities, which can be viewed as generalizing several previous models in different ways. We develop an efficient spectral algorithm for estimating the community memberships, which deals with the overlaps by employing the $K$-medians algorithm rather than the usual $K$-means for clustering in the spectral domain. We show that the algorithm is asymptotically consistent when the network is not too sparse and the overlaps between communities are not too large. Numerical experiments on both simulated networks and many real social networks demonstrate that our method performs well compared to a number of benchmark methods for overlapping community detection.