Fortification Against Cascade Propagation Under Uncertainty

Colin P. Gillen (), Alexander Veremyev (), Oleg A. Prokopyev () and Eduardo L. Pasiliao ()
Additional contact information
Colin P. Gillen: Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Alexander Veremyev: Industrial Engineering and Management Systems, University of Central Florida, Orlando, Florida 32816
Oleg A. Prokopyev: Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Eduardo L. Pasiliao: Munitions Directorate, Air Force Research Laboratory, Eglin Air Force Base, Florida 32542

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1481-1499

Abstract: Network cascades represent a number of real-life applications: social influence, electrical grid failures, viral spread, and so on. The commonality between these phenomena is that they begin from a set of seed nodes and spread to other regions of the network. We consider a variant of a critical node detection problem dubbed the robust critical node fortification problem, wherein the decision maker wishes to fortify nodes (within a budget) to limit the spread of cascading behavior under uncertain conditions. In particular, the arc weights—how much influence one node has on another in the cascade process—are uncertain but are known to lie in some range bounded by a worst-case budget uncertainty. This problem is shown to be N P -hard even in the deterministic case. We formulate a mixed-integer program (MIP) to solve the deterministic problem and improve its continuous relaxation via nonlinear constraints and convexification. The robust problem is computationally more difficult, and we present an MIP-based expand-and-cut exact solution algorithm, in which the expansion is enhanced by cutting planes, which are themselves tied to the expansion process. Insights from these exact solutions motivate two novel (interrelated) centrality measures , and a centrality-based heuristic that obtains high-quality solutions within a few seconds. Finally, extensive computational results are given to validate our theoretical developments as well as provide insights into structural properties of the robust problem and its solution.

Keywords: critical elements detection; cascade propagation; robust optimization; centrality measures (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0992 (application/pdf)

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:inm:orijoc:v:33:y:2021:i:4:p:1481-1499

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().