A newly developed fast, scalable algorithm can optimize the distribution of vaccines in a simulated epidemic network, potentially bringing the number of infected people down by three to seven times.
A team led by Washington State University and Pacific Northwest National Laboratory researchers used a synthetic social contact network for residents of Portland, Oregon as a test for their computer algorithm to come up with a vaccination strategy to drive down the number of infections. In the test case, the research team compared the strategy provided by the algorithm with a scenario in which doctors vaccinated the same number of people randomly, showing the algorithm could decrease the number of infected people by three to seven times.
The team which includes researchers from the University of Virginia, presented their work at last week’s SC20, the International Conference for High Performance Computing, Networking, Storage, and Analysis.
“In the past, large computer models have used mathematical programming to try to optimize vaccine solutions.” said Ananth Kalyanaraman, WSU’s Boeing Centennial Chair in Computer Science who helped to lead the team. “But the spreading of a disease is incredibly complex, and the mathematical-based models aren’t well suited to take a network view of people actually interacting with other people. Our algorithm provides a network view of a population on the move.”
The researchers said the algorithm is a good start, but it will need to be significantly improved to be used for a real-life scenario, including for the coronavirus pandemic vaccination efforts.
Vaccination is one of the primary intervention strategies for controlling the spread of an epidemic. As vaccines becomes available, policymakers need to prioritize distribution, determining who of the 328 million people in the U.S. should get access to a vaccine first, and who should be next.
Mathematical-based programs can only solve for groups of about 10,000 people at a time in a process that can take hours or even days. The method isn’t feasible for a solution for hundreds of millions of people who interact daily.
For the past seven years, researchers at PNNL and WSU have been collaborating on a number of scalable graph applications in science and engineering, especially under the auspices of the U.S. Department of Energy’s ExaGraph co‑design center. They have recently focused on applications that aim to maximize influence on a network, such as over a protein network or for an ad campaign.
When the pandemic hit earlier this year, they immediately saw that the work could be applied to the epidemic control problem and vaccine placement to minimize or prevent the spread of infections.
“We had a pretty good start,” said Kalyanaraman. “It was a different way of studying a diffusion problem.”
Bringing in collaborators from the University of Virginia who have expertise in epidemiology, the team took a network and graph analytics approach to the problem. Their formulation maps the problem to identifying an optimal set of nodes, or seeds, for vaccination so that the effective number of infections on the network can be minimized.
“This formulation allows us to leverage principles from influence maximization— a well-known problem in network science,” said Marco Minutoli, a WSU graduate student, computer scientist at Pacific Northwest National Laboratory and lead author on the work. “These types of strategies have not been studied for containing epidemics, especially in the context of uncertainties or lack of prior information. This application makes the work relevant to researchers, practitioners and decision makers in the epidemics domain.”
The researchers used the Summit supercomputer at Oak Ridge National Laboratory, which is the world’s second fastest supercomputer. The work was challenging and complex, but the researchers showed how supercomputers can make a significant contribution in solving real-world problems.
“Speed is a critical factor, and we now have the ability to not just compute the largest number of possible solutions but also compute them quickly and accurately, so that critical problems are addressed in as close to real-time as possible,” said Mahantesh Halappanavar, a computer scientist at PNNL with a joint appointment at WSU.
In particular, the work counts individual people in a whole city and their contacts, but it doesn’t include any of the social or economic determinants that play a role in disease spread. For instance, people who are taking mass transit daily would be more likely to get COVID‑19 than somebody who is working remotely.
“Social and economic determinants play a role in disease spread,” said Anil Vullikanti, a computer scientist at the University of Virginia Biocomplexity Institute who also worked on the project. “Algorithmic fairness is a big topic and something we all talk about. We want to make sure everyone in the community has the opportunity to get vaccinated without one community being left out.”
A silver lining in the current COVID‑19 pandemic is that there is more information about it than in any previous epidemic. Scientists have been able to benefit in recent months from a windfall of data that can be used to analyze policies and determine intervention strategies and compliance for similar challenges in the future.
“This information was not available in past epidemics,” said Kalyanaraman. “It will be helpful going forward.”
The work was supported by the U.S. Department of Energy Office of Science, National Science Foundation, and the National Institutes of Health. The research team also included Prathyush Sambathru, a graduate student at the University of Virginia.