查看文章

The Critical Node Detection Problem (CNDP) consists in finding the set of nodes, defined critical, whose removal maximally degrades the graph. In this work we focus on finding the set of critical nodes whose removal minimizes the pairwise connectivity of a direct graph (digraph). Such problem has been proved to be NP-hard, thus we need efficient heuristics to detect critical nodes in real-world applications. We aim at understanding which is the best heuristic we can apply to identify critical nodes in practice, i.e., taking into account time constrains and real-world networks. We present an in-depth analysis of several heuristics we ran on both real-world and on synthetic graphs. We define and evaluate two different strategies for each heuristic: standard and iterative. Our main findings show that an algorithm recently proposed to solve the CNDP and that can be used as heuristic for the general case provides the best …