Global Pervasive Computational Epidemiology Seminar Series: Anirudh Sridhar

Finding Super-spreaders in Network Cascades

Speaker: Anirudh Sridhar, Department of Mathematics, MIT

Abstract: Suppose that a cascade (e.g. an epidemic) spreads on an unknown graph, and only the infection times of vertices are observed. What can be learned about the graph from the infection times caused by multiple distinct cascades? Most of the literature on this topic focuses on the task of recovering the entire graph, which requires Ω(log n) cascades for an n-vertex bounded degree graph. Here we ask a different question: can the important parts of the graph be estimated from just a few (i.e. constant number) of cascades, even as n grows large?

In this work, we focus on identifying super-spreaders (i.e high-degree vertices) from infection times caused by a Susceptible-Infected process on a graph. Our first main result shows that vertices of degree greater than n^3/4 can indeed be estimated from a constant number of cascades. Our algorithm for doing so leverages a novel connection between vertex degrees and the second derivative of the cumulative infection curve. Conversely, we show that estimating vertices of degree smaller than n^1/2 requires at least log(n)/loglog(n) cascades. Surprisingly this matches (up to loglog(n) factors) the number of cascades needed to learn the entire graph if it is a tree. This is joint work with Elchanan Mossel (MIT).

Bio: Anirudh Sridhar (Ani) is a postdoctoral associate at MIT's Department of Mathematics. Previously, he completed his PhD from Princeton's Department of Electrical and Computer Engineering, where he was advised by H. Vincent Poor and Miklós Rácz. Broadly, Ani's research develops statistical methods for the analysis of networks, with a focus on information-theoretic characterizations. His awards include the Yan Huo *94 Graduate Fellowship in Electrical Engineering from Princeton University in 2022 and a Spotlight Presentation at NeurIPS 2021. He was also a finalist for the Informs-APS Best Student Paper Award in 2020.

Join the webinar here.