Fast identification of critical nodes in complex network based on improved greedy algorithm

Abstract Over the past decades, many critical and complex systems, such as power grid, transportation network, and information network, have been effectively modeled using complex network. However, these networks are susceptible to cascading failure, triggered by minor failure, leading to partial or total collapse. Preventing cascading failure necessitates the protection of critical nodes within the network, making the identification of these nodes particularly crucial. In this paper, we introduce an Improved Greedy algorithm (IGA), inspired by the traditional greedy algorithm and the relationship between the propagation mechanism of cascading failure and N-K failure. This algorithm gets rid of the shortcomings of traditional recognition algorithms for dealing with large-scale networks with long time and low accuracy, and evaluates the critical degree of nodes based on network connectivity and overload rate. The simulation is carried out in Barabsi-Albert (BA) network and IEEE 39-, 118-bus systems, and make comparisons with other different algorithms. The results show that IGA not only has low computational complexity, but also has high accuracy in identifying critical nodes in complex networks.