@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",

note = "Funding Information: Financial support from the National Science Foundation under awards EAGER ECCS-1545270 and ECCS-1609916 is gratefully acknowledged. Publisher Copyright: {\textcopyright} 2017 IEEE.; 56th IEEE Annual Conference on Decision and Control, CDC 2017 ; Conference date: 12-12-2017 Through 15-12-2017",

year = "2018",

month = jan,

day = "18",

doi = "10.1109/CDC.2017.8263650",

language = "English (US)",

series = "2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "102--107",

booktitle = "2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017",

}