### 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 language | English (US) |
---|---|

Title of host publication | 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 102-107 |

Number of pages | 6 |

Volume | 2018-January |

ISBN (Electronic) | 9781509028733 |

DOIs | |

State | Published - Jan 18 2018 |

Event | 56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia Duration: Dec 12 2017 → Dec 15 2017 |

### Other

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

Country | Australia |

City | Melbourne |

Period | 12/12/17 → 12/15/17 |

### Fingerprint

### 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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -