Activities per year
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 language | English |
---|---|
Article number | 105254 |
Number of pages | 34 |
Journal | Computers & Operations Research |
Volume | 131 |
Early online date | 24 Feb 2021 |
DOIs | |
Publication status | Published - 31 Jul 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.-
Women in Operational Research and Analytics (WORAN) event: OR for a Better world
Alozie, G. (Speaker)
26 Aug 2021Activity: Talk or presentation types › Invited talk
-
15th INFORMS Telecommunication and Network Analytics Conference
Alozie, G. U. (Participant)
20 Oct 2020Activity: Participating in or organising an event types › Participation in conference