Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method
Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method
Prathyush Sambaturu, Marco Minutoli, Mahantesh Halappanavar, Ananth Kalyanaraman, Anil Vullikanti
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
AI for Good. Pages 5164-5170.
https://doi.org/10.24963/ijcai.2022/717
We study the problem of designing scalable algorithms to find effective intervention strategies for controlling stochastic epidemic processes on networks. This is a common problem arising in agent based models for epidemic spread.
Previous approaches to this problem focus on either heuristics with no guarantees or approximation algorithms that scale only to networks corresponding to county-sized populations, typically, with less than a million nodes. In particular, the mathematical-programming based approaches need to solve the Linear Program (LP) relaxation of the problem using an LP solver, which restricts the scalability of this approach. In this work, we overcome this restriction by designing an algorithm that adapts the multiplicative weights update (MWU) framework, along with the sample average approximation (SAA) technique, to approximately solve the linear program (LP) relaxation for the problem. To scale this approach further, we provide a memory-efficient algorithm that enables scaling to large networks, corresponding to country-size populations, with over 300 million nodes and 30 billion edges. Furthermore, we show that this approach provides near-optimal solutions to the LP in practice.
Keywords:
Agent-based and Multi-agent Systems: Resource Allocation
AI Ethics, Trust, Fairness: Fairness & Diversity
Data Mining: Networks
Multidisciplinary Topics and Applications: Health and Medicine