Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
arXiv:1712.02370
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 (38)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting 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
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Link communities reveal multiscale complexity in 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
- The performance of modularity maximization in practical contexts
- An information-theoretic framework for resolving community structure in complex networks
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Detect overlapping and hierarchical community structure in networks
- Mixture models and exploratory analysis in networks
- Fuzzy communities and the concept of bridgeness in complex networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Detecting highly overlapping community structure by greedy clique expansion
- Weighted network modules
- Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
- Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
- Community detection and graph partitioning
- Enhancing community detection using a network weighting strategy
- Spectral tripartitioning of 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
- Towards Linear Time Overlapping Community Detection in Social Networks
- Leveraging disjoint communities for detecting overlapping community structure
- LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation
- Ensemble approaches for improving community detection methods
- On the Permanence of Vertices in Network Communities
- Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
- Intrinsically Dynamic Network Communities
- YASCA: A collective intelligence approach for community detection in complex networks