Optimal Detection of Critical Nodes: Improvements to Model Structure and Performance

Gokhan Karakose and Ronald G. McGarvey ()
Additional contact information
Gokhan Karakose: University of Missouri
Ronald G. McGarvey: University of Missouri

Networks and Spatial Economics, 2019, vol. 19, issue 1, No 1, 26 pages

Abstract: Abstract The identification of critical network components is of interest to both interdictors wishing to degrade the network’s performance, and to defenders aiming to preserve network performance in the face of disruption. In this study, novel formulations for the defender’s problem, based on the dual to the multi-commodity flow problem, are developed to solve the critical node problem (CNP), in which the nodes can be disabled, for a variety of commonly-studied objectives, including minimum connectivity, cardinality-constraint CNP, and β-disruptor problem. These objectives have applications in many types of networks, including transportation, communications, public health, and terrorism. Extensive computational experiments are presented, demonstrating that the proposed models dramatically reduce the computational time needed to solve such problems when compared to the best-performing models in the current literature. The proposed CNP models perform particularly well for networks that are originally disconnected (before interdiction) and for networks with a large number of two-degree nodes.

Keywords: Network vulnerability; Node disruption; Mixed-integer linear programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-018-9407-0 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:19:y:2019:i:1:d:10.1007_s11067-018-9407-0

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-018-9407-0

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().