Maximizing the Spread of Cascades Using Network Design

2012/03/15 by Daniel Sheldon, Sheldon, Daniel, Bistra Dilkina +19 · 1 citation
Medicine · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Evolutionary Game Theory and Cooperation #FOS: Computer and information sciences #FOS: Physical sciences #Mathematical and Theoretical Epidemiology and Ecology Models #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.1203.3514

openalex publication_date 2012/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dynamics by adding nodes or edges to the network. Our motivating application is one in spatial conservation planning, where a cascade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formulation that combines elements from network design and stochastic optimization. Our approach results in solutions with stochastic optimality guarantees and points to conservation strategies that are fundamentally different from naive approaches.

Citations

• An analysis of approximations for maximizing submodular set functions—I
• The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study
• The Complexity of Enumeration and Reliability Problems

Cited by

• Influence Minimization Under Budget and Matroid Constraints: Extended Version

Related

• Robust Optimization for Tree-Structured Stochastic Network Design
• Selecting nodes and buying links to maximize the information diffusion in a network
• What Makes a Good Plan? An Efficient Planning Approach to Control Diffusion Processes in Networks
• Multi-Stage Sparse Resource Allocation for Control of Spreading Processes over Networks
• Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently