A heuristic approach for the distance-based critical node detection problem in complex networks

Alozie, Glory Uche and Arulselvan, Ashwin and Akartunali, Kerem and Pasiliao, Jr., Eduardo L (2022) A heuristic approach for the distance-based critical node detection problem in complex networks. Journal of the Operational Research Society, 73 (6). pp. 1347-1361. ISSN 0160-5682 (https://doi.org/10.1080/01605682.2021.1913078)

[thumbnail of Alozie-etal-JORS-2021-A-heuristic-approach-for-the-distance-based-critical-node-detection-problem-in-complex-networks]
Preview
 Text. Filename: Alozie_etal_JORS_2021_A_heuristic_approach_for_the_distance_based_critical_node_detection_problem_in_complex_networks.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

The distance-based critical node problem involves identifying a subset of nodes in a network whose removal minimises a pre-defined distance-based connectivity measure. Having the classical critical node problem as a special case, the distance-based critical node problem is computationally challenging. In this article, we study the distance-based critical node problem from a heuristic algorithm perspective. We consider the distance-based connectivity objective whose goal is to minimise the number of node pairs connected by a path of length at most k, subject to budgetary constraints. We propose a centrality based heuristic which combines a backbone-based crossover procedure to generate good offspring solutions and a centrality-based neighbourhood search to improve the solution. Extensive computational experiments on real-world and synthetic graphs show the effectiveness of the developed heuristic in generating good solutions when compared to exact solution. Our empirical results also provide useful insights for future algorithm development.

CORE (COnnecting REpositories)