Efficient methods for the distance-based critical node detection problem in complex networks

Research output: Contribution to journalArticlepeer-review

Abstract

An important problem in network survivability assessment is the identification of critical nodes. The distance-based critical node detection problem addresses the issues of internal cohesiveness and actual distance connectivity overlooked by the traditional critical node detection problem. In this study, we consider the distance-based critical node detection problem which seeks to optimise some distance-based connectivity metric subject to budgetary constraints on the critical node set. We exploit the structure of the problem to derive new path-based integer linear programming formulations that are scalable when compared to an existing compact model. We develop an efficient algorithm for the separation problem that is based on breadth first search tree generation. We also study some valid inequalities to strengthen the formulations and a heuristic to improve primal bounds. We have applied our models and algorithm to two different classes of the problems determined by the distance based connectivity functions. Extensive computational experiments on both real-world and randomly generated network instances, show that the proposed approach is computationally more efficient than the existing compact model especially for larger instances where connections between nodes consist of a small number of hops. Our computational experiments on both classes of distance-based critical node detection problem provide good numerical evidence to support the importance of defining appropriate metrics for specific network applications.
Original languageEnglish
Article number105254
Number of pages34
JournalComputers & Operations Research
Volume131
Early online date24 Feb 2021
DOIs
Publication statusE-pub ahead of print - 24 Feb 2021

Keywords

  • critical node problem
  • distance connectivity
  • integer programming
  • lazy constraints
  • breadth first search

Fingerprint Dive into the research topics of 'Efficient methods for the distance-based critical node detection problem in complex networks'. Together they form a unique fingerprint.

Cite this