Overlapping Community Detection based on Network Decomposition
Open Access
- 12 April 2016
- journal article
- Published by Springer Nature in Scientific Reports
- Vol. 6 (1) , 24115
Abstract
Community detection in complex network has become a vital step to understand the structure and dynamics of networks in various fields. However, traditional node clustering and relatively new proposed link clustering methods have inherent drawbacks to discover overlapping communities. Node clustering is inadequate to capture the pervasive overlaps, while link clustering is often criticized due to the high computational cost and ambiguous definition of communities. So, overlapping community detection is still a formidable challenge. In this work, we propose a new overlapping community detection algorithm based on network decomposition, called NDOCD. Specifically, NDOCD iteratively splits the network by removing all links in derived link communities, which are identified by utilizing node clustering technique. The network decomposition contributes to reducing the computation time and noise link elimination conduces to improving the quality of obtained communities. Besides, we employ node clustering technique rather than link similarity measure to discover link communities, thus NDOCD avoids an ambiguous definition of community and becomes less time-consuming. We test our approach on both synthetic and real-world networks. Results demonstrate the superior performance of our approach both in computation time and accuracy compared to state-of-the-art algorithms.Keywords
This publication has 61 references indexed in Scilit:
- Overlapping community detection in networksACM Computing Surveys, 2013
- Link Clustering with Extended Link Similarity and EQ Evaluation DivisionPLOS ONE, 2013
- Classification of Knee Joint Vibration Signals Using Bivariate Feature Distribution Estimation and Maximal Posterior Probability Decision CriterionEntropy, 2013
- Clustering and overlapping modules detection in PPI network based on IBFOProteomics, 2012
- Multifunctional proteins revealed by overlapping clustering in protein interaction networkBioinformatics, 2011
- Link communities reveal multiscale complexity in networksNature, 2010
- Modularity optimization in community detection of complex networksEurophysics Letters, 2009
- Proteome survey reveals modularity of the yeast cell machineryNature, 2006
- MIPS: analysis and annotation of proteins from whole genomes in 2005Nucleic Acids Research, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005