Divisive Algorithm Based on Node Clustering Coefficient for Community Detection
Open Access
- 31 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 142337-142347
Abstract
This paper studies the relationship between the clustering coefficient of nodes and the community structure of the network. Communities in a network are regarded as node-induced subgraphs of the network in this study. We define the border of a subgraph and the node network density of a node and present a formal definition of community from the view of examining the subgraph borders. Afterward, we analyze the relationship between the change in node clustering coefficients and in node network density and set the rule for identifying intercommunity edges. Finally, we propose a novel divisive algorithm for community detection by iteratively removing intercommunity edges. The time complexity of our algorithm is O(Nd2), which increases linearly with the network size. Experiments on both synthetic and real-world networks show that introducing node clustering coefficients into the divisive algorithm can greatly improve the time efficiency of the algorithm while guaranteeing the accuracy of community detection.Keywords
Funding Information
- National Basic Research Program of China (2016YFD0501500)
- National Sciences Foundation of China (61672331)
- Key Research and Development Program of Shanxi Province through the International Cooperation (201803D421024, 201903D421041)
- Special fund project for guiding local science and technology development by the central government (YDZX20191400002563)
This publication has 53 references indexed in Scilit:
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Evaluating local community methods in networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Communicability in complex networksPhysical Review E, 2008
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Finding community structure in very large networksPhysical Review E, 2004
- Self-contained algorithms to detect communities in networksThe European Physical Journal B, 2004
- The maximum clique problemJournal of Global Optimization, 1994