Identifying critical nodes’ group in complex networks

Recently, network vulnerability or security has attracted much attention in various networked systems, and especially in security related attacks or protections, there are a set of influential nodes that can remarkably break the network connectivity. In this work, we firstly present eight attack mechanisms including target attack, random failure, betweenness based attack, closeness based attack, PageRank based attack, k-shell based attack, greedy algorithm, and low-degree attack. Secondly, inspired by the dynamic node removal process, we propose to recalculate the metrics for every node removal strategy, and evaluate the network robustness against all these heuristic attack strategies with and without recalculations in scale-free networks, random networks, and many real network models. The simulations indicate that most of the attack strategies with recalculations appear to imperil the network structure security more. Furthermore, considering that key node set mining is very critical for network structure protections, we employ minimum number of key nodes (MNKN) metric to further discuss the network vulnerability against all the attack strategies with or without recalculations. The results show that the critical nodes’ group can be more efficiently found under the PageRank based attack with recalculations than under other attack disciplines with or without recalculations in most of the classic and real network models. This work investigates network structure vulnerability and security from a new perspective, and has potential applications into network structure protection or planning.