Which links matter most? Sparsifying network dynamics with effective resistance

“Sparsification” is the act of reducing a network to a subset of its edges while approximately preserving its properties: either to reduce the computational cost of solving problems about it, or to identify which edges are the most important in some sense. Computer scientists have developed beautiful techniques for sparsifying a graph using physics-related ideas like the effective resistance. However, while these methods preserve the spectral properties of the Laplacian, it is not obvious to what extent they preserve the behavior of nonlinear dynamical systems. Using a mobility network from the United States as an example, I’ll show that they do very well for the SIR epidemic model, including the probability each node becomes infected and its distribution of arrival times, even when the sparse network includes less than 10% of the original edges. Choosing edges using purely topological methods, or by thresholding edge weights, does not perform nearly as well. I will end by discussing the possibility of using sparsification to “denoise” networks from bioinformatics, and present some preliminary results on the Kuramoto model of coupled oscillators.

 

This is joint work with Alexander Mercier (Harvard School of Public Health), Emmie Fitz-Gibbons (Brown), and Sam Scarpino (Northeastern).