Identifying critical nodes in complex networks based on neighborhood information

Authors:

Abstract
The identification of important nodes in complex networks has always been a prominent topic in the field of network science. Nowadays, the emergence of large-scale networks has sparked our research interest in complex network centrality methods that balance accuracy and efficiency. Therefore, this paper proposes a novel centrality method called Spon (Sum of the Proportion of Neighbors) Centrality, which combines algorithmic efficiency and accuracy. Spon only requires information within the three-hop neighborhood of a node to assess its centrality, thereby exhibiting lower time complexity and suitability for large-scale networks. To evaluate the performance of Spon, we conducted connectivity tests on 16 empirical unweighted networks and compared the monotonicity and algorithmic efficiency of Spon with other methods. Experimental results demonstrate that Spon achieves both accuracy and algorithmic efficiency, outperforming eight other methods, including CycleRatio, collective influence, and Social Capital. Additionally, we present a method called W-Spon to extend Spon to weighted networks. Comparative experimental results on 10 empirical weighted networks illustrate that W-Spon also possesses advantages compared to methods such as I-Core and M-Core.
Funding Information
  • Key Research and Development Program of Yunnan Province (202102AA100021)
  • demonstration project of comprehensive government management and large-scale industrial application of the major special project of CHEOS (89-Y50G31-9001-22/23)
  • National Natural Science Foundation of China (62066048)
  • Key Laboratory for Crop Production and Smart Agriculture of Yunnan Province
  • Science Foundation of Yunnan Province (202101AT070167)

This publication has 57 references indexed in Scilit: