Detecting Overlapping Communities in Networks with Spectral Methods

• Activity Number: 568
• Type: Contributed
• Date/Time: Wednesday, August 6, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Yuan Zhang*+ and Elizaveta Levina and Ji Zhu
• Companies: University of Michigan and University of Michigan and University of Michigan
• Keywords: networks ; overlapping communities ; spectral clustering

Abstract

Community detection is a fundamental problem in network analysis, and while many methods have been proposed to partition networks into disjoint communities, there is a need for more flexible models that allow overlapping communities, which are common in practice. Here we propose a flexible generative model that describes networks with overlapping communities. The overlapping community membership parameters can be efficiently estimated via a spectral clustering type algorithm we propose. We show that the estimation is consistent under mild conditions, and demonstrate the effectiveness of our method in numerical experiments and data applications.