Distance-based critical node detection and its application to network vulnerability assessment

Abstract A popular strategy for network vulnerability assessment is to identify critical nodes, whose deletion maximally degrades the connectivity of the original network. Decision makers usually have information about the network structure they intend to obtain, but do not know the number of nodes to target. In this context, we study a distance-based critical node problem with unknown budget, known as the β-distance-based vertex disruptor problem. To solve it, we first derive three integer linear programming formulations, i.e., recursive, triangular connectivity-based, and reduced path-based ones. They are then solved using the CPLEX solver. To approximately solve large instances that an exact solver fails to solve, we propose a simple and effective integrated strategic oscillation search that combines hill climbing and strategic oscillation. It examines a large neighborhood by alternating between a tabu-enhanced destruction procedure and a random order-based improving construction procedure. Extensive experiments on both real-world and synthetic benchmark instances demonstrate the advantages of the proposed formulations and heuristic. In particular, the reduced path-based formulation outperforms both recursive and triangular connectivity-based ones. The proposed heuristic is significantly faster than exact and state-of-the-art algorithms. Finally, we perform a case study on air transportation networks to gain insights into the impacts of COVID-19.