Conquering the Worst Case of Infections in Networks

We develop algorithms to control the scope of an infection spread on a network by allocating a fixed immunization budget to edges of the graph. We assume that the infection propagates according to an independent cascade model and interventions operate by reducing the propensities of edges to transmit the infection. We formulate this problem as a constrained min-max optimization problem with respect to the placements of interventions and the location of the worst-case seed nodes. However, the result is a challenging bilevel mixed integer optimization problem. Furthermore, gradients of the objective function with respect to the continuous variables are unavailable in closed form. We employ tools from derivative-free optimization and stochastic optimization to optimize the objective by iterating between the outer minimization and inner maximization problems. In the inner loop, we use a weighted degree discount (WDD) method to select the seed set of the influence maximization problem. In the outer loop, we utilize two methods: a sample-based simultaneous perturbation Nelder-Mead (SBSP-NM) algorithm and a simultaneous perturbation stochastic approximation (SPSA) algorithm. We perform simulations on synthetic graphs and three larger-scale real-world datasets and illustrate the computational feasibility of our algorithms and their efficacy at controlling epidemic spreads.