Activities per year
Abstract
An important problem in network survivability assessment is the identification of critical nodes. The distancebased 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 distancebased critical node detection problem which seeks to optimise some distancebased connectivity metric subject to budgetary constraints on the critical node set. We exploit the structure of the problem to derive new pathbased 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 realworld 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 distancebased 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  Epub 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 distancebased critical node detection problem in complex networks'. Together they form a unique fingerprint.
Activities
 1 Participation in conference

15th INFORMS Telecommunication and Network Analytics Conference
Glory Uche Alozie (Participant)
20 Oct 2020Activity: Participating in or organising an event types › Participation in conference