GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
arXiv:1604.03454 · doi:10.1109/TKDE.2016.2554119
Abstract
Detection of non-overlapping and overlapping communities are essentially the same problem. However, current algorithms focus either on finding overlapping or non-overlapping communities. We present a generalized framework that can identify both non-overlapping and overlapping communities, without any prior input about the network or its community distribution. To do so, we introduce a vertex-based metric, GenPerm, that quantifies by how much a vertex belongs to each of its constituent communities. Our community detection algorithm is based on maximizing the GenPerm over all the vertices in the network. We demonstrate, through experiments over synthetic and real-world networks, that GenPerm is more effective than other metrics in evaluating community structure. Further, we show that due to its vertex-centric property, GenPerm can be used to unfold several inferences beyond community detection, such as core-periphery analysis and message spreading. Our algorithm for maximizing GenPerm outperforms six state-of-the-art algorithms in accurately predicting the ground-truth labels. Finally, we discuss the problem of resolution limit in overlapping communities and demonstrate that maximizing GenPerm can mitigate this problem.
This paper (final version) is accepted in IEEE Transactions on Knowledge and Data Engineering (TKDE). 13 Figures, 6 tables
References in corpus (13)
- Fast unfolding of communities in large networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Finding statistically significant communities in networks
- Consensus clustering in complex networks
- Detect overlapping and hierarchical community structure in networks
- Mixture models and exploratory analysis in networks
- Extending the definition of modularity to directed graphs with overlapping communities
- Quantifying and identifying the overlapping community structure in networks
- Fundamental statistical features and self-similar properties of tagged networks
- Extension of Modularity Density for Overlapping Community Structure
- On the Permanence of Vertices in Network Communities