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

PI : Qin Zhang
NSF IIS-1633215 (September 2016 - August 2020)


A number of phenomena of societal importance, such as the spread of diseases and contagion processes, can be modeled by stochastic processes on networks. The analysis and control of such network phenomena involve, at their heart, fundamental graph-theoretic problems. The graphs encountered are typically of large-scale (having tens of millions of nodes); further, typical experimental analyses involve large designs with a number of parameters, leading to hundreds of thousands of graph computations. Novel methods for solving these problems are needed, since fast response times are critical to effective decision making.

The overarching goal of this project is to develop efficient distributed algorithms and associated lower bounds for graph-theoretic problems that arise in computational epidemiology and contagion dynamics. This will have a significant impact on these specific applications, through more efficient algorithmic tools for enabling complex analyses.

This is a collaborative project with Prof. Gopal Pandurangan (University of Houston) and Prof. Anil Vullikanti (Virginia Tech).


  1. Distributed Partial Clustering
    with S. Guha and Y. Li
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 17), to appear. Washington D.C., U.S.A., July 2017.
    Best Paper Award

  2. Communication-Optimal Distributed Clustering
    with J. Chen, H. Sun and D. Woodruff
    Proc. Annual Conference on Neural Information Processing Systems (NIPS 16), pages 3720-3728. Barcelona, Spain, December 2016.

Invited/Conference Talks