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

1 Citation (Scopus)

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

Fingerprint

Cascading Failure
Linear programming
Convex optimization
Cascade
System theory
Threshold Model
Amplification
Dynamical systems
Topology
Horizon
Specifications
Vertex of a graph
Systems Theory
Convex Optimization
Initialization
Linear Program
Network Topology
Dynamical system
Maximise
Scaling

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

Cite this

Fardad, M., & Kearney, G. (2018). On a linear programming approach to the optimal seeding of cascading failures. In 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017 (Vol. 2018-January, pp. 102-107). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2017.8263650

On a linear programming approach to the optimal seeding of cascading failures. / Fardad, Makan; Kearney, Griffin.

2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017. Vol. 2018-January Institute of Electrical and Electronics Engineers Inc., 2018. p. 102-107.

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

Fardad, M & Kearney, G 2018, On a linear programming approach to the optimal seeding of cascading failures. in 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017. vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 102-107, 56th IEEE Annual Conference on Decision and Control, CDC 2017, Melbourne, Australia, 12/12/17. https://doi.org/10.1109/CDC.2017.8263650
Fardad M, Kearney G. On a linear programming approach to the optimal seeding of cascading failures. In 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017. Vol. 2018-January. Institute of Electrical and Electronics Engineers Inc. 2018. p. 102-107 https://doi.org/10.1109/CDC.2017.8263650
Fardad, Makan ; Kearney, Griffin. / On a linear programming approach to the optimal seeding of cascading failures. 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017. Vol. 2018-January Institute of Electrical and Electronics Engineers Inc., 2018. pp. 102-107
@inproceedings{4c6a31593cd3416dbbfb3debcb4f0891,
title = "On a linear programming approach to the optimal seeding of cascading failures",
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.",
keywords = "Boolean networks, cascading behavior, convex optimization, diffusion of innovations, epidemics, linear programming, reweighted ℓ, social contagion, sparsity, threshold model, viral marketing",
author = "Makan Fardad and Griffin Kearney",
year = "2018",
month = "1",
day = "18",
doi = "10.1109/CDC.2017.8263650",
language = "English (US)",
volume = "2018-January",
pages = "102--107",
booktitle = "2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - GEN

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

AU - Fardad, Makan

AU - Kearney, Griffin

PY - 2018/1/18

Y1 - 2018/1/18

N2 - 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.

AB - 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.

KW - Boolean networks

KW - cascading behavior

KW - convex optimization

KW - diffusion of innovations

KW - epidemics

KW - linear programming

KW - reweighted ℓ

KW - social contagion

KW - sparsity

KW - threshold model

KW - viral marketing

UR - http://www.scopus.com/inward/record.url?scp=85046118476&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046118476&partnerID=8YFLogxK

U2 - 10.1109/CDC.2017.8263650

DO - 10.1109/CDC.2017.8263650

M3 - Conference contribution

VL - 2018-January

SP - 102

EP - 107

BT - 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017

PB - Institute of Electrical and Electronics Engineers Inc.

ER -