An Interplay between Critical Node Detection and Epidemic Models For a given graph and a positive number k, the goal of the Critical Node Detection Problem (CNDP) is to find the set of  k  nodes, named critical nodes, whose removal minimize the connectivity between the surviving nodes. The CNDP has been extensively studied in the literature and is gaining special attention in the vulnerability evaluation of telecommunication networks. More recently, a worstcase analysis of an epidemic model was introduced, where a disease is spread among a given population. The goal is to find a set of nodes to be immunized that minimize the number of deadnodes as a result. This extremal analysis is captured by a combinatorial optimization problem, called Graph Fragmentation Problem (GFP). In this paper, we show that the CNDP and the GFP are identical combinatorial problems, in the sense that the globally optimal solution is identical under the same instances. As corollary, we conclude universal inapproximability results for the CNDP.

Critical Nodes Identification in Complex Networks Critical nodes identification in complex networks is significance for studying the survivability and robustness of networks. The previous studies on structural hole theory uncovered that structural holes are gaps between a group of indirectly connected nodes and intermediaries that fill the holes and serve as brokers for information exchange. In this paper, we leverage the property of structural hole to design a heuristic algorithm based on local information of the network topology to identify node importance in undirected and unweighted network, whose adjacency matrix is symmetric. In the algorithm, a node with a larger degree and greater number of structural holes associated with it, achieves a higher importance ranking. Six real networks are used as test data. The experimental results show that the proposed method not only has low computational complexity, but also outperforms degree centrality, kshell method, mapping entropy centrality, the collective influence algorithm, DDN algorithm that based on node degree and their neighbors, and random ranking method in identifying node importance for network connectivity in complex networks.