Finding Spatial Clusters Susceptible to Epidemic Outbreaks due to Undervaccination

Geographical clusters of undervaccinated populations have emerged in various parts of the United States in recent years. Public health response involves surveillance and field work, which is very resource intensive. Given that public health resources are often limited, identifying and rank-ordering critical clusters can help prioritize and allocate scarce resources for surveillance and quick intervention. We quantify the criticality of a cluster as the additional number of infections caused if the cluster is underimmunized. We focus on finding clusters that maximize this measure and develop efficient approximation algorithms for finding critical clusters by exploiting structural properties of the problem. Our methods involve solving a more general problem of maximizing a submodular function on a graph with connectivity constraints. We apply our methods to the state of Minnesota, where we find clusters with significantly higher criticality than those obtained by heuristics used in public health.