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.
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: