Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks

Abstract

Though much work has been done on ensemble clustering in data mining, the application of ensemble methods to community detection in networks is in its infancy. In this paper, we propose two ensemble methods: ENDISCO and MEDOC. ENDISCO performs disjoint community detection. In contrast, MEDOC performs disjoint, overlapping, and fuzzy community detection and represents the first ever ensemble method for fuzzy and overlapping community detection. We run extensive experiments with both algorithms against both synthetic and several real-world datasets for which community structures are known. We show that ENDISCO and MEDOC both beat the best-known existing standalone community detection algorithms (though we emphasize that they leverage them). In the case of disjoint community detection, we show that both ENDISCO and MEDOC beat an existing ensemble community detection algorithm both in terms of multiple accuracy measures and run-time. We further show that our ensemble algorithms can help explore core-periphery structure of network communities, identify stable communities in dynamic networks and help solve the "degeneracy of solutions" problem, generating robust results.

References in corpus (19)

• Fast unfolding of communities in large networks
• Modularity and community structure in 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
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• Detect overlapping and hierarchical community structure in networks
• Mixture models and exploratory analysis in networks
• Weighted network modules
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Enhancing community detection using a network weighting strategy
• Spectral tripartitioning of networks
• Fundamental statistical features and self-similar properties of tagged networks
• Leveraging disjoint communities for detecting overlapping community structure
• On the Permanence of Vertices in Network Communities
• Efficient Bayesian Community Detection using Non-negative Matrix Factorisation