Performance Analysis of Single and Multi-objective Approaches for the Critical Node Detection Problem

Critical infrastructures are network-based systems which are prone to various types of threats (e.g., terroristic or cyber-attacks). Therefore, it is paramount to devise modelling frameworks to assess their ability to withstand external disruptions and to develop protection strategies aimed at improving their robustness and security. In this paper, we compare six modelling approaches for identifying the most critical nodes in infrastructure networks. Three are well-established approaches in the literature, while three are recently proposed frameworks. All the approaches take the perspective of an attacker whose ultimate goal is to inflict maximum damage to a network with minimal effort. Specifically, they assume that a saboteur must decide which nodes to disable so as to disrupt network connectivity as much as possible. The formulations differ in terms of the attacker objectives and connectivity metrics (e.g., trade-off between inflicted damage and attack cost, pair-wise connectivity, size and number of disconnected partitions). We apply the six formulations to the IEEE24 and IEEE118 Power Systems and conduct a comparative analysis of the solutions obtained with different parameters settings. Finally, we use frequency analysis to determine the most critical nodes with respect to different attack strategies.