Detection and Characterization of Critical Under-Immunized Hotspots

Sponsor

National Institutes of Health (NIH)

Emergence of undervaccinated geographical clusters for diseases like measles has become a national concern. A number of measles outbreaks have occurred in recent months, despite high MMR coverage in the United States (95%). Such undervaccinated clusters can act as reservoirs of infection that can transmit the disease to a wider population, magnifying their importance far beyond what their absolute numbers might indicate. The existence and growth of such undervaccinated clusters is often known to public health agencies and health provider networks, but they typically do not have enough resources to target people in each such cluster, to attempt to improve the vaccination rate. Preliminary results show that not all undervaccinated clusters are “equal” in terms of their potential for causing a big outbreak (referred to as its “criticality”), and the rate of undervaccination in a cluster does not necessarily correlate with its criticality. This project uses novel methods to identify these critical clusters.

It brings together a systems science approach, combines agent-based stochastic epidemic models, and techniques from machine learning, high performance computing, data mining, and spatial statistics, along with novel public and private datasets on immunization and incidence, to develop a novel methodology for identifying critical clusters, through the following tasks:

  1. Identify spatial clusters with significantly low immunization rates;
  2. Develop an agent based model for the spread of measles that incorporates detailed immunization data, and is calibrated using a novel source of incidence data;
  3. Develop methods to find and characterize critical spatial clusters, with respect to different metrics, which capture both epidemic and economic burden, and rank order underimmunized clusters based on their criticality; and
  4. Use the methodology to evaluate interventions in terms of their effect on criticality.

A highly interdisciplinary team involving two universities, a health care delivery organization and a state department of Health, will work together to develop this methodology. Characterization of such clusters will enable public health departments and policy makers in targeted surveillance of their regions and a more efficient allocation of resources.

Project Overview

Goals

  1. Identify spatial clusters with significantly low immunization rates
  2. Develop an agent-based model for the spread of measles that incorporates detailed immunization data, and is calibrated using a novel source of incidence data
  3. Develop methods to find and characterize critical spatial clusters, with respect to different metrics, which capture both epidemic and economic burden, and order underimmunized clusters based on their criticality
  4. Use the methodology to evaluate interventions in terms of their effect on criticality
Findings

One fundamental task in network analysis is detecting “hotspots” or “anomalies” in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we provide a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the “effective solution size,” while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1--2 orders of magnitude larger than all prior applications.

Emergence of under-immunized clusters is a growing concern for public health agencies because they can act as reservoirs of infection and increase the risk of infection into the wider population. We use realistic population models for Minnesota and Washington state, and combine this with school level immunization data to estimate vaccine coverage at the level of census block groups. A scan statistic method defined on networks is used for finding significant clusters of under-immunized block groups, without any restrictions on shape. Further we provide the demographic characteristics of these clusters. We find significant under-vaccinated clusters in MN and WA. These are very irregular in shape, in contrast to the circular disks reported in prior work, which rely on the SatScan approach. Some of the clusters found by our method are not contained in those computed using SatScan, a state-of-the-art software tool used in similar studies in other states. Higher resolution clusters computed using our network based approach and population models provide new insights on the structure and characteristics of such clusters and enable targeted interventions (Cadena et al. BMC Medical Informatics and Decision-Making).

Four graphs of under-immunized cluster data in Minnesota and Washington State

Figure 1: Top two significant clusters in MN (top right and top left) are shown. Each dot on the map is a block group. The same clusters are shown as block group polygons on the bottom right and left, with each marker corresponding to a block group. First cluster in Minnesota covers the city of St. Paul (top left and bottom left) and the second cluster covers the rural block groups west of Minneapolis (top right and bottom right)

Finding Critical Clusters

In this research, we formalize the outbreak risk of a cluster by its “criticality", which is defined as the “probability of a large outbreak" caused by a single case of measles in the cluster. We focus on clusters that are most significant in terms of under immunization rates and measure their criticality. Finding significant under immunized clusters and computing their criticality is a challenging computational problem. We use a synthetic social contact network model for Virginia, and school-level immunization data in the state, along with a network scan statistics approach to find significant under immunized clusters. We combine this with a detailed stochastic agent-based simulation framework to estimate the criticality of each significant cluster, by simulating outbreaks that originate in these clusters (Fig. 2). We also examine how the criticality of clusters changes under a hypothetical 5% drop in MMR rate among children (younger than 12 years), possibly due to disruptions caused by COVID- 19. Finally, we study the demographic, geographic, and network factors associated with such clusters, which can help explain the potential risk of a cluster. Identifying critical clusters and the factors associated with it will be of use to public health authorities who can use this information to prioritize mitigation efforts. Note that although this work focuses on measles, as it uses MMR coverage data and a measles specific disease model, the methodology is generic and can be applied to study other infectious diseases.

Figure 2. Four major components of the framework: 1) An activity-based population network G(V,E), where a node represents an individual, and an edge represents a contact between two people; 2) under-immunized spatial clusters in a zip code level network Gz(Vz,Ez), where nodes are zip codes, and a connection between two zip codes represents a geographically shared boundary; 3) Criticality analysis of each cluster using the stochastic network epidemic model; and 4) Understanding criticality by investigating network properties of unvaccinated subnetwork Gu. To find significant clusters and their criticality, we first identify statistically significant under immunized clusters; for this purpose, we develop a zip code level spatial network from a detailed activity-based population contact network and use a network scan statistics method. Next, we investigate the criticality of each cluster by importing a single case of measles and simulating its spread using an agent-based model.

Criticality of a cluster. We define the criticality of the set Vc ⊂V in immunization v, denoted by crit(Vc, v), as the probability of a large outbreak, when the initial infection occurs in subset Vc. Formally, crit(Vc, v) = Pr[I(v, Vc)> OC], where OC is the threshold for a large outbreak (taken to be 500, as mentioned above). We use the probability of an outbreak instead of the more commonly used metric of expected number of infections because the expectation is quite small, as many outbreaks die out due to the high immunization rates.

To understand the potential reasons behind the criticality of clusters, we investigate their characteristics such as geographic and network properties. We explore the impact of geographic location, size, population density, and under-immunization rate on the criticality of a cluster. For network attributes, we measure their degree, node strength, and eigenvector centrality. We also investigate the connected components.

Our analysis shows that the local network properties of a cluster are not enough in measuring its potential risk of an outbreak from a drop in immunization rate. We have considered five local properties: size, degree, node strength, links inside of a cluster, and connections inside to outside. A small drop in immunization coverage (only 0.8%) increases the outbreak risk of one of the clusters many folds; however, surprisingly, the increment in local properties of this cluster is the lowest among all the clusters. We find that while the local properties can be misleading, global network properties like the eigenvector analysis can provide a better understanding of the change in criticality, since it considers the full network connectivity. This research shows that the outbreak risk of under-immunized clusters is vastly different depending on their location, size, immunization rate, and network properties.

For more details on this analysis, please see: S Moon*, A Marathe, A Vullikanti. Are all underimmunized measles clusters equally critical? Royal Society Open Science, August 2023. https://doi.org/10.1098/rsos.230873

Team

Professor

Professor of Public Health Sciences, School of Medicine

Professor

Professor of Computer Science, School of Engineering and Applied Science

Professor

Professor of Public Health Sciences, School of Medicine

Research Associate Professor

Other Team Members

Travis Porco | Professor of Global Health | University of California, San Francisco

Nicola Klein | Senior Research Scientist | Kaiser Permanente

Publications
Network Systems Science and Advanced Computing
Dixit A; Espinoza B; Qiu Z; Vullikanti A; Marathe M . Proceedings of the National Academy of Sciences. National Academy of Sciences. 2023; 120(16)
Network Systems Science and Advanced Computing
Adiga Ani; Lewis B; Levin S; Marathe M; Poor H; Ravi S; Rosenkrantz D; Stearns R; Venkatramanan S; Vullikanti A; Wang L . Artificial Intelligence in Covid-19. Springer, Cham. 2022; :193-228
Network Systems Science and Advanced Computing
Babay A; Dinitz M; Srinivasan A; Tsepenekas L; Vullikanti A . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR . MLResearchPress. 2022; 151:11641-11654
Network Systems Science and Advanced Computing
Mehrab Z; Wilson M; Chang S; Harrison G; Lewis B; Telionis A; Crow J; Kim D; Spillman S; Peters K; Leskovec J; Marathe M . Proceedings of the AAAI Conference on Artificial Intelligence. AAAI. 2022; 36(11):12573-12579
Network Systems Science and Advanced Computing
Bhattacharya P; Chen J; Hoops S; Machi D; Lewis B; Venkatramanan S; Wilson M; Klahn B; Adiga A; Hurt B; Outten J; Adiga A; Warren A; Baek H; Porebski P; Marathe A; Xie D; Swarup S; Vullikanti A; Mortveit H; Eubank S; Barrett C; Marathe M . The International Journal of High Performance Computing Applications. SAGE journals. 2022; 37(1):4-27
Network Systems Science and Advanced Computing
Li G; Li A; Marathe M; Srinivasan A; Tsepenekas L; Vullikanti A . arXiv.org. arXiv. 2022;
Network Systems Science and Advanced Computing
Li G; Li A; Marathe M; Srinivasan A; Tsepenekas L; Vullikanti A . arXiv.org. arXiv. 2022;
Network Systems Science and Advanced Computing
Mohamed M; Nguyen D; Vullikanti A; Tandon R . Proceedings of the 39th International Conference on Machine Learning. MLResearchPress. 2022; 162:15858-15894
Network Systems Science and Advanced Computing
Rosenkrantz D; Adiga A; Marathe M; Qiu Z; Ravi S; Stearns R; Vullikanti A . International Conference on Machine Learning. 2022; :18796-18808
Network Systems Science and Advanced Computing
Dinitz M; Srinivasan A; Tsepenekas L; Vullikanti A . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR . MLResearchPress. 2022; 151:6321-6333
Network Systems Science and Advanced Computing
Rosenkrantz D; Vullikanti A; Ravi S; Stearns R; Levin S; Poor H; Marathe M . Proceedings of the National Academy of Sciences. National Academy of Sciences. 2022; :e2109228119
Network Systems Science and Advanced Computing
Heavey J; Cui J; Prakash B; Vullikanti A . Biocomplexity Institute Spring 2022 Research Symposium. UVA Biocomplexity Institute and Initiative. 2022;
Network Systems Science and Advanced Computing
Li G; Haddadan A; Li A; Marathe M; Srinivasan A; Vullikanti A; Zhao Z . Proc. of the 21st Int’l Conference on Autonomous Agents and Multiagent Systems. ACM. 2022; :1672-1674
Network Systems Science and Advanced Computing
Nguyen D; Vullikanti A . arXiv preprint arXiv:2105.13287. Cornell University. 2021;
Network Systems Science and Advanced Computing
Pilehvari A; Ton J; Mohan M; Marathe A; Vullikanti A . CSSSA 2021: Proceedings of the 2021 Conference of The Computational Social Science Society of the Americas. Springer. 2021;
Network Systems Science and Advanced Computing
Haque A; Thakur M; Bielskas M; Marathe A; Vullikanti A . Proceedings of the AAAI Conference on Artificial Intelligence. PKP Publishing Services. 2021; 35(6):4812-4820
Network Systems Science and Advanced Computing
Chen J; Hoops S; Marathe A; Mortveit H; Lewis B; Venkatramanan S; Haddadan A; Bhattacharya P; Adiga A; Vullikanti A . medRxiv. Cold Spring Harbor Laboratory Press. 2021;
Network Systems Science and Advanced Computing
Cadena J; Marathe A; Vullikanti A . International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction and Behavior Representation in Modeling and Simulation . Springer, Cham/SBP-BRiMS 2020: Social, Cultural, and Behavioral Modeling. 2020;
Network Systems Science and Advanced Computing
Adiga Ani; Chen J; Marathe M; Mortveit H; Venkatramanan S; Vullikanti A . Journal of Indian Institute of Science. the Institute. 2020; 100:901-915
Network Systems Science and Advanced Computing
Cadena J; Marathe A; Vullikanti A . AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. ACM. 2020; :1786-1788
Network Systems Science and Advanced Computing
Adiga Ani; Dubhashi D; Lewis B; Marathe M; Venkatramanan S; Vullikanti A . Journal of the Indian Institute of Science. Springer. 2020; 100:793-807
Network Systems Science and Advanced Computing
Chen J; Vullikanti A; Hoops S; Mortveit H; Lewis B; Venkatramanan S; You W; Eubank S; Marathe M; Barrett C . Scientific reports. Nature Publishing Group. 2020; 10(1):44206
Network Systems Science and Advanced Computing
Wang L; Chen J; Marathe A . World Wide Web. Springer US. 2019; 22(6):2997-3020
Network Systems Science and Advanced Computing
Cadena J; Falcone D; Marathe A; Vullikanti A . BMC medical informatics and decision making. BioMed Central. 2019; 19(1):28
Network Systems Science and Advanced Computing
Adhikari B; Lewis B; Vullikanti A; Jimenez J; Prakash B . PLoS Computational Biology. Public Library of Science. 2019; 15(9):e1007284
Network Systems Science and Advanced Computing
Singh M; Sarkhel P; Kang G; Marathe A; Boyle K; Murray-Tuite P; Abbas K; Swarup S . BMC infectious diseases. BioMed Central. 2019; 19(1):221
Network Systems Science and Advanced Computing
Cadena J; Chen F; Vullikanti A . ACM Transactions on Knowledge Discovery from Data (TKDD). ACM. 2019; 13(2):20
Network Systems Science and Advanced Computing
Venkatramanan S; Chen J; Fadikar A; Gupta S; Higdon D; Lewis B; Marathe M; Mortveit H; Vullikanti A . PLoS computational biology. Public Library of Science. 2019; 15(9):e1007111
Network Systems Science and Advanced Computing
Swarup S; Marathe A; Marathe M; Barrett C . Social-Behavioral Modeling for Complex Systems. John Wiley & Sons. 2019; :617-632
Network Systems Science and Advanced Computing
Cadena J; Chen F; Vullikanti A . SIAM. 2017; :624-632

Other Publications

  1. S Moon*, A Marathe, A Vullikanti. Are all underimmunized measles clusters equally critical? Royal Society Open Science, August 2023. https://doi.org/10.1098/rsos.230873

  2. S Chu*, X Liu*, X Deng, A Marathe. A Latent Process Approach to Change-Point Detection of Mixed-Type Observations. Quality Engineering, 2023, pages 1-20.

  3. Truelove, S., Smith, C.P., Qin, M., Mullany, L.C., Borchering, R.K., Lessler, J., Shea, K., Howerton, E., Contamin, L., Levander, J. and Kerr, J., et al. 2022. Projected resurgence of COVID-19 in the United States in July—December 2021 resulting from the increased transmissibility of the Delta variant and faltering vaccination. Elife, 11, p.e73584. PMID: 35726851

  4. M Thakur*, R Zhou*, M Mohan*, A Marathe, J Chen, S Hoops, D Machi, B Lewis, A Vullikanti. COVID’s collateral damage: Likelihood of measles resurgence in the United States. BMC Infectious Diseases, September 2022. PMID: 36127637

  5. Zirou Qiu*, Baltazar Espinoza*, Vitor V. Vasconcelos, Chen Chen*, Sara Constantino, Stefani Crabtree, Luojun Yang, Anil Vullikanti, Jiangzhuo Chen, Jörgen Weibull, Kaushik Basu, Avinash Dixit, Simon Levin, Madhav Marathe. Understanding the coevolution of mask wearing and epidemics: A network perspective. Proceedings of the National Academy of Sciences. 2022 June; 119(26). PMID: 35733262

  6. Borchering RK, Mullany LC, Howerton E, Chinazzi M, Smith CP, Qin M, Reich NG, Contamin L, Levander J, Kerr J, Espino J, Hochheiser H, Lovett K, Kinsey M, Tallaksen K, Wilson S, Shin L, Lemaitre JC, Hulse JD, Kaminsky J, Lee EC, Hill AL, Davis JT, Mu K, Xiong X, Pastore Y Piontti A, Vespignani A, Srivastava A, Porebski P, Venkatramanan S, Adiga A, Lewis B, Klahn B, Outten J, Hurt B, Chen J, Mortveit H, Wilson A, Marathe M, Hoops S, Bhattacharya P, Machi D, Chen S, Paul R, Janies D, Thill JC, Galanti M, Yamana T, Pei S, Shaman J, España G, Cavany S, Moore S, Perkins A, Healy JM, Slayton RB, Johansson MA, Biggerstaff M, Shea K, Truelove SA, Runge MC, Viboud C, Lessler J. Impact of SARS-CoV-2 vaccination of children ages 5-11 years on COVID-19 disease burden and resilience to new variants in the United States, November 2021-March 2022: A multi-model study. Lancet Reg Health Am. 2023 Jan;17:100398. doi: 10.1016/j.lana.2022.100398. Epub 2022 Nov 22. PubMed PMID: 36437905; PubMed Central PMCID: PMC9679449.

  7. Venkatramanan S, Sadilek A, Fadikar* A, Barrett CL, Biggerstaff M, Chen J, Dotiwalla X, Eastham P, Gipson B, Higdon D, Kucuktunc O, Lieber A, Lewis BL, Reynolds Z, Vullikanti AK, Wang L, Marathe M. Forecasting influenza activity using machine-learned mobility map.

  8. A Basak*, J Cadena*, A Marathe and A Vullikanti. Detection of Spatio-temporal Clusters of Opioid Users with Network Scan Statistics: A Multi-state Analysis. JMIR Public Health and Surveillance, 2019;5(2):e12110 DOI: 10.2196/12110 PMID: 31210142

  9. Harrison G, Alabsi Aljundi A, Chen J, Ravi S, Vullikanti A, Marathe M, Adiga A. Identifying Complicated Contagion Scenarios from Cascade Data. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD '23: 2023; Long Beach CA USA. New York, NY, USA.

  10. Wang, L., Adiga, A., Chen, J., Lewis, B., Sadilek, A., Venkatramanan, S. and Marathe, M., 2022. Combining Theory and Data-Driven Approaches for Epidemic Forecasts. Knowledge Guided Machine Learning (pp. 55-82). Chapman and Hall/CRC.