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

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