Mathematics

effective resistance against pandemics

From the summer of 2020 until the fall of 2022, Alexander Mercier worked with Dr. Cristopher Moore of the Santa Fe Institute on network sparsification of large, complex networks with the aim of approximately preserving the stochastic dynamics of disease spread. In 2021, Dr. Samuel Scarpino of Northeastern and the Pandemic Prevention Institute joined the project. Using a spectral sparsification algorithm using edge effective resistances, about 90% of the original number of edges can be removed while approximately preserving average stochastic dynamics of a continuous-time, event-driven SIR model. A write-up of work was featured on the Santa Fe Institute website here.

Abstract

Network science has increasingly become central to the field of epidemiology and our ability to respond to infectious disease threats. However, many networks derived from modern datasets are not just large, but dense, with a high ratio of edges to nodes. This includes human mobility networks where most locations have a large number of links to many other locations. Simulating large-scale epidemics requires substantial computational resources and in many cases is practically infeasible. One way to reduce the computational cost of simulating epidemics on these networks is sparsification, where a representative subset of edges is selected based on some measure of their importance. We test several sparsification strategies, ranging from naive thresholding to random sampling of edges, on mobility data from the U.S. Following recent work in computer science, we find that the most accurate approach uses the effective resistances of edges, which prioritizes edges that are the only efficient way to travel between their endpoints. The resulting sparse network preserves many aspects of the behavior of an SIR model, including both global quantities, like the epidemic size, and local details of stochastic events, including the probability each node becomes infected and its distribution of arrival times. This holds even when the sparse network preserves fewer than 10% of the edges of the original network. In addition to its practical utility, this method helps illuminate which links of a weighted, undirected network are most important to disease spread.

The work is published in the Public Library of Science (PLoS) Computational Biology and is found here.

Relevant Papers: Daniel A. Spielman and Nikhil Srivastava | Swarup et al.

White-nose syndrome [wns] modeling

From spring 2019 through fall 2019, Alexander Mercier worked with Dr. Andrew Kramer at the Kramer Ecology Lab in order to build a model of the spread of P. destructans in the brown bat (Myotis lucifugus). As P. destructans is a cryophilic fungus, pathogenesis is thought to be temperature-dependent. For this reason, Alexander Mercier has worked with climatic data and geospatial data obtained from the National Oceanic Atmospheric Association (NOAA). Additionally, statistical analysis on various hypotheses regarding spread and transition in relation to climatic data has been performed.

Abstract

White-nose syndrome (WNS) is caused by a highly pathogenic cryophilic fungus, Pseudogymnoascus destructans, which affects the little brown bat, Myotis lucifugus. Previous work has shown that WNS spread is dependent on the spatial distribution of hibernacula and is higher in colder regions. Understanding how weather and climate influence disease spread is vital to managing infected populations and preventing spread to vulnerable bat colonies. It is unclear if the mechanism driving risk of WNS infection is due to general climate or weather at the time of spread. Utilizing a geographic database of WNS spread from the Fish and Wildlife Service, a generalized gravity model examining pairwise interactions between counties was formulated based on the density and distance of caves in a county. Maximum likelihood (ML) was employed to fit a series of models to the data on a county-scale to study the spread of WNS through the contiguous United States. Covariates describing weather were extracted from high-resolution climatic data obtained from the National Oceanic and Atmospheric Administration. Several combinations of dimensions were implemented, including the yearly length of winter, the yearly start of winter, average winter length, and bat species richness to uncover the predictive power of different combinations of variables. From reported AIC scores, stronger support for models including the length of winter during the year when WNS was detected. This finding implicates that the mechanics of WNS spread are driven by winter conditions which result in a variable risk of infection, with fitted data indicating that longer winters increase spread transmission risk. However, as it is more difficult to predict future weather than climate, it may still be more convenient to use climatic data than weather for future predictions. 

Currently, the work on WNS syndrome is being written for review and is anticipated to be submitted for publication in spring, 2023.

Relavent Papers: Sean P. Maher et al. | Kate E. Langwig et al.

Network Sparsification and compression

From the fall of 2019 through the present, Alexander Mercier is working with Dr. Andrew Kramer at the Kramer Ecology Lab in order to explore the fascinating notion of network compression through sparsification. Network sparsification is the concept of extracting a subset of the graph – called a backbone – that retains the important underlying network structure. This is accomplished by removing “weak” edges while retaining the topological structure. Specifically examining sparsification methods such as best path, iterative refitting, and Lorelai Adaptive Sparsification (LAS). Network compression is a vital tool for working with large complex networks such as those found in species interaction networks, transport networks, social networks, epidemiolocal networks, and other macrosystems.

The prevalence of large spatial or interaction networks, wherein a plethora of casual relationships between nodes are observed, necessitates the ability to work with large complex networks both computationally and intuitively. This ability is crucial to many fields such as computational epidemiology, transport system modeling, and other macrosystems. In order to work with large complex networks, a variety of dimensionality reduction techniques have been formulated. Some techniques are graph spectrum-based compression, motif profiles, and sparsification or backbone extraction. Sparsification is uniquely appealing, as it permits an intuitive, graphical or visual appraisal of a network, showing which edges and nodes in a network are the most important. A new method for backbone extraction to be investigated is through algorithmic complexity. Measuring Kolmogorov complexity approximated through the Block Decomposition Method (BDM), a large complex graph can be broken down through BDM and be systematically pared down to essential vertices and edges by strategically removing edges which increase K-complexity of the network under a determined threshold to uncover which edges are crucial to the overall complexity of a network. However, many unanswered questions remain. Principally, does the method successfully extract a backbone? More pressingly, how should successful network compression be measured? Additionally, how well does this method of network compression work on multiple types of networks – both theoretical and applied – and can it be utilized for both global and local-based network sparsification?

This work cumulated in the R package, simplifyNet, available on CRAN.

Relevant Papers: Hector Zenil et al. | Steven H. Strogatz