Ensemble-based Overlapping Community Detection using Disjoint Community Structures

Abstract

While there has been a plethora of approaches for detecting disjoint communities from real-world complex networks, some methods for detecting overlapping community structures have also been recently proposed. In this work, we argue that, instead of developing separate approaches for detecting overlapping communities, a promising alternative is to infer the overlapping communities from multiple disjoint community structures. We propose an ensemble-based approach, called EnCoD, that leverages the solutions produced by various disjoint community detection algorithms to discover the overlapping community structure. Specifically, EnCoD generates a feature vector for each vertex from the results of the base algorithms and learns which features lead to detect densely connected overlapping regions in an unsupervised way. It keeps on iterating until the likelihood of each vertex belonging to its own community maximizes. Experiments on both synthetic and several real-world networks (with known ground-truth community structures) reveal that EnCoD significantly outperforms nine state-of-the-art overlapping community detection algorithms. Finally, we show that EnCoD is generic enough to be applied to networks where the vertices are associated with explicit semantic features. To the best of our knowledge, EnCoD is the second ensemble-based overlapping community detection approach after MEDOC [1].

31 pages, 7 tables, 3 figures, Knowledge-Based Systems

References in corpus (15)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Detect overlapping and hierarchical community structure in networks
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Fundamental statistical features and self-similar properties of tagged networks
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Towards Linear Time Overlapping Community Detection in Social Networks
• Leveraging disjoint communities for detecting overlapping community structure
• Ensemble approaches for improving community detection methods
• On the Permanence of Vertices in Network Communities
• On the Formation of Circles in Co-authorship Networks