IC Colloquium: Which links matter most? Sparsifying epidemic models with effective resistance
By: Cris Moore - Sante Fe Institute
Abstract
Network science has increasingly become central to the field of epidemiology. However, many networks derived from modern datasets are not just large, but dense, with a high average degree. One way to reduce the computational cost of simulating epidemics on these networks is sparsification, where a subset of edges is selected and reweighted based on some measure of their importance. Following recent work in computer science, we find that the most accurate approach uses the effective resistances of edges, which can be computed from the graph Laplacian. The resulting sparse network preserves both the local and global behavior of the SIR model, including the probability each node becomes infected and its distribution of arrival times. This holds even when the sparse network preserves less than 10% of the edges of a mobility network from the United States. Our work helps illuminate which links of a network are most important to disease spread. Defining edge importance using purely topological methods, or by thresholding edge weights, does not perform nearly as well.
This is joint work with Alexander Mercier (Harvard School of Public Health) and Sam Scarpino (Northeastern).
Bio
Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. Since 2012, he has been a resident professor at the Santa Fe Institute. He has also held visiting positions at the Niels Bohr Institute, École Normale Superieure, École Polytechnique, Université Paris 7, Northeastern University, the University of Michigan, and Microsoft Research.
Moore has written over 160 papers at the boundary between mathematics, physics, and computer science, including on quantum computing, social networks, phase transitions in NP-complete problems, Bayesian inference, and risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.
More information
Abstract
Network science has increasingly become central to the field of epidemiology. However, many networks derived from modern datasets are not just large, but dense, with a high average degree. One way to reduce the computational cost of simulating epidemics on these networks is sparsification, where a subset of edges is selected and reweighted based on some measure of their importance. Following recent work in computer science, we find that the most accurate approach uses the effective resistances of edges, which can be computed from the graph Laplacian. The resulting sparse network preserves both the local and global behavior of the SIR model, including the probability each node becomes infected and its distribution of arrival times. This holds even when the sparse network preserves less than 10% of the edges of a mobility network from the United States. Our work helps illuminate which links of a network are most important to disease spread. Defining edge importance using purely topological methods, or by thresholding edge weights, does not perform nearly as well.
This is joint work with Alexander Mercier (Harvard School of Public Health) and Sam Scarpino (Northeastern).
Bio
Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. Since 2012, he has been a resident professor at the Santa Fe Institute. He has also held visiting positions at the Niels Bohr Institute, École Normale Superieure, École Polytechnique, Université Paris 7, Northeastern University, the University of Michigan, and Microsoft Research.
Moore has written over 160 papers at the boundary between mathematics, physics, and computer science, including on quantum computing, social networks, phase transitions in NP-complete problems, Bayesian inference, and risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.
More information
Practical information
- General public
- Free
Contact
- Host: Lenka Zdeborova