Detecting Overlapping Communities in Networks Using Spectral Methods

Abstract

Community detection is a fundamental problem in network analysis which is made more challenging by overlaps between communities which often occur in practice. Here we propose a general, flexible, and interpretable generative model for overlapping communities, which can be thought of as a generalization of the degree-corrected stochastic block model. 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 networks are not too sparse and the overlaps between communities not too large. Numerical experiments on both simulated networks and many real social networks demonstrate that our method performs very well compared to a number of benchmark methods for overlapping community detection.

29 pages, 2 figures, 3 tables

References in corpus (13)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral methods for network community detection and graph partitioning
• An efficient and principled method for detecting communities in networks
• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Stochastic blockmodels with growing number of classes
• Community extraction for social networks
• Impact of regularization on Spectral Clustering
• How Many Communities Are There?

Cited by in corpus (22)

• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Inference for multiple heterogeneous networks with a common invariant subspace
• Mixed Membership Estimation for Social Networks
• Improvements on SCORE, Especially for Weak Signals
• Consistent Estimation of Mixed Memberships with Successive Projections
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Community detection with nodal information
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• A Sharp Lower Bound for Mixed-membership Estimation
• On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
• Hierarchical community detection by recursive partitioning
• Asymptotic Theory of Eigenvectors for Random Matrices with Diverging Spikes
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• Provable Overlapping Community Detection in Weighted Graphs
• A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection
• A Semidefinite Program for Structured Blockmodels
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Clustering Degree-Corrected Stochastic Block Model with Outliers
• Network Representation Learning: From Traditional Feature Learning to Deep Learning