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 (29)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Error and attack tolerance of complex networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Mixing patterns in networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Link communities reveal multiscale complexity in networks
- Immunization of complex networks
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Consensus clustering in complex networks
- Finding overlapping communities in networks by label propagation
- 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
- Extending the definition of modularity to directed graphs with overlapping communities
- 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
- Normalized Mutual Information to evaluate overlapping community finding algorithms
- Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
- Fuzzy overlapping communities in networks
- Quantifying and identifying the overlapping community structure in networks
- Modularity measure of networks with overlapping communities
- Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
- 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