Overlapping Community Detection

• Activity Number: 670
• Type: Invited
• Date/Time: Thursday, August 13, 2015 : 10:30 AM to 12:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Yuan Zhang and Elizaveta Levina* and Ji Zhu
• Companies: University of Michigan and University of Michigan and University of Michigan
• Keywords: networks ; community detection ; overlapping communities ; stochastic block model

Abstract

Community detection is a fundamental problem in network analysis, but most of the current literature focuses on partitioning networks in disjoint communities, whereas in practice communities often overlap. Here we propose a general and flexible generative model that describes overlapping communities in a network. We propose an efficient spectral clustering algorithm for estimating the community membership, and show that the estimation is 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 the method's accuracy and efficiency.