Large-Scale Epidemic Control via Matrix Balancing

• Activity Number: 130 - Advances in Resource Allocation for Epidemic Control: Estimation, Optimization, and Counterfactuals
• Type: Topic Contributed
• Date/Time: Monday, August 3, 2020 : 1:00 PM to 2:50 PM
• Sponsor: Section on Statistics in Epidemiology
• Author(s): Van Sy Mai* and Abdella Battou
• Companies: National Institute of Standards and Technology and National Institute of Standards and Technology
• Keywords: spreading process; contact network; epidemic control; optimization; matrix balancing; random graph

Abstract

We consider a problem of optimally allocating resources for suppressing epidemic spreads in a directed weighted network, where the spreading dynamic exhibits a phase transition depending on the contact network structure and the heterogeneous infection and curing rates. This phase transition is captured by a critical threshold: below which the spread dies out quickly; otherwise an outbreak occurs. We show that solutions to this problem can be derived from that of a matrix balancing problem, for which efficient centralized algorithms exist. For large scale networks, we propose an improved variant of a classical matrix balancing algorithm that admits a better convergence rate and is more amenable for parallel and even asynchronous distributed implementations. Moreover, we show that for a large class of graphs, including random graphs, our algorithm runs in nearly linear time.