BIG DATA: Efficient Distributed Computation of Large-Scale Graph Problems in Epidemiology and Contagion Dynamics

Project Contact: Anil Vullikanti / Madhav Marathe
Funding Agency: National Science Foundation National Science Foundation logo

We aim to develop a rigorous algorithmic theory of distributed large-scale graph computation, specifically focusing on important graph problems that arise in computational epidemiology and contagion dynamics. At the onset of any epidemic and during the annual flu season, epidemiologists and public health officials are concerned with understanding how the disease spreads, who is likely to get infected, where it originated, and how to control its rapid spread. Mathematical models are commonly used for studying these problems, especially stochastic contagion models on real-world networks. Fundamental graph-theoretic problems arise naturally and crucially in analyzing these models and solving these questions. The graphs encountered are typically large (with tens of millions of nodes). Further, typical experimental analyses involve large designs with many parameters, leading to hundreds of thousands of graph computations. In this domain, fast response times are critical to effective decision making, and distributed and parallel computation meets this need.