It can take weeks or even months to run the simulations needed to predict how a pandemic of this magnitude will spread. A new method for epidemic modeling is presented in a recent paper published in PLOS Computational Biology, and it could significantly speed up the procedure.
The study employs sparsification, a technique from computer science and graph theory, to determine which connections in a network are crucial for the transmission of disease.
The scientists discovered they could cut the calculation time for simulating the transmission of diseases over extremely complex social networks by 90% or more by concentrating on crucial links.
“Epidemic simulations require substantial computational resources and time to run, which means your results might be outdated by the time you are ready to publish,” says lead author Alexander Mercier, a former Undergraduate Research Fellow at the Santa Fe Institute and now a Ph.D. student at the Harvard T.H. Chan School of Public Health. “Our research could ultimately enable us to use more complex models and larger data sets while still acting on a reasonable timescale when simulating the spread of pandemics such as COVID-19.”
For the study, Mercier, with SFI researchers Samuel Scarpino and Cristopher Moore, used data from the U.S. Census Bureau to develop a mobility network describing how people across the country commute.
It’s common in the life sciences to naively ignore low-weight links in a network, assuming that they have a small probability of spreading a disease. But as in the catchphrase ‘the strength of weak ties,’ even a low-weight link can be structurally important in an epidemic for instance, if it connects two distant regions or distinct communities.
Samuel Scarpino
They then tried a variety of sparsification techniques to see if they could lessen the network’s density while still maintaining the dynamics of a disease moving throughout the system.
They discovered effective resistance to be the most effective sparsification method. This method, which has its roots in computer science, is based on the sum of the resistances at the ends of an electrical circuit.
According to the current research, efficient resistance prioritizes disease-transmission-prone mobility network edges, or linkages, while ignoring those that can be readily avoided by taking alternative routes.
“It’s common in the life sciences to naively ignore low-weight links in a network, assuming that they have a small probability of spreading a disease,” says Scarpino. “But as in the catchphrase ‘the strength of weak ties,’ even a low-weight link can be structurally important in an epidemic for instance, if it connects two distant regions or distinct communities.”
The researchers preserved overall epidemic dynamics while creating a network with 25 million fewer edges, or around 7% of the original U.S. commuting network, using their efficient resistance sparsification method.
“Computer scientists Daniel Spielman and Nikhil Srivastava had shown that sparsification can simplify linear problems, but discovering that it works even for nonlinear, stochastic problems like an epidemic was a real surprise,” says Moore.
Although the research is still in its early stages, it already helps to lower the computational cost of simulating large-scale pandemics and preserves crucial information about disease spread, such as the likelihood that a particular census tract will become infected and when the epidemic is likely to arrive there.
