Community detection is a fundamental problem in network analysis which ismade more challenging by overlaps between communities which often occur inpractice. Here we propose a general, flexible, and interpretable generativemodel for overlapping communities, which can be thought of as a generalizationof the degree-corrected stochastic block model. We develop an efficientspectral algorithm for estimating the community memberships, which deals withthe overlaps by employing the K-medians algorithm rather than the usual K-meansfor clustering in the spectral domain. We show that the algorithm isasymptotically consistent when networks are not too sparse and the overlapsbetween communities not too large. Numerical experiments on both simulatednetworks and many real social networks demonstrate that our method performsvery well compared to a number of benchmark methods for overlapping communitydetection.
展开▼
