On a linear programming approach to the optimal seeding of cascading failures

Makan Fardad, Griffin Kearney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We consider the threshold model of cascading behavior in networks, in which a node fails if at least a certain fraction of its neighbors have failed in the previous time step. Our goal is to solve the optimal cascade seeding problem: For a given network and specified time horizon, find the set of nodes whose failure at time zero maximizes the failure amplification ratio-the ratio between the number of final and initial failures. The optimal cascade seeding problem is combinatorial and thus intractable for large networks. We propose an approximation of the threshold model that lends itself to the application of tools from dynamical systems theory and convex optimization. Through a sequence of relaxations we write the approximate optimal cascade seeding problem as a linear program, which has the benefit of scaling gracefully in network size. Our approach retains the original network topology and accommodates the specification of a wide range of additional constraints on the initialization and propagation of failures, such as which nodes are immune from initial failure and which are required to be in failed state by the end of the time horizon.

Original languageEnglish (US)
Title of host publication2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages102-107
Number of pages6
Volume2018-January
ISBN (Electronic)9781509028733
DOIs
StatePublished - Jan 18 2018
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: Dec 12 2017Dec 15 2017

Other

Other56th IEEE Annual Conference on Decision and Control, CDC 2017
CountryAustralia
CityMelbourne
Period12/12/1712/15/17

Keywords

  • Boolean networks
  • cascading behavior
  • convex optimization
  • diffusion of innovations
  • epidemics
  • linear programming
  • reweighted ℓ
  • social contagion
  • sparsity
  • threshold model
  • viral marketing

ASJC Scopus subject areas

  • Decision Sciences (miscellaneous)
  • Industrial and Manufacturing Engineering
  • Control and Optimization

Fingerprint Dive into the research topics of 'On a linear programming approach to the optimal seeding of cascading failures'. Together they form a unique fingerprint.

Cite this