Ani Sridhar

2024

1. COLT 2024

   Finding Super-spreaders in Network Cascades

   Elchanan Mossel, and Anirudh Sridhar

   Proceedings of the Conference on Learning Theory, Jul 2024

   Abs Bib HTML

   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 \emphentire 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) / \log \log (n) cascades. Surprisingly, this matches (up to \log \log n factors) the number of cascades needed to learn the \emphentire graph if it is a tree.

   @article{mossel2024finding,
     title = {Finding {S}uper-spreaders in {N}etwork {C}ascades},
     author = {Mossel, Elchanan and Sridhar, Anirudh},
     journal = {Proceedings of the Conference on Learning Theory},
     month = jul,
     year = {2024},
   }

2023

1. SICON

   Mean-field Approximations for Stochastic Population Processes with Heterogeneous Interactions

   Anirudh Sridhar, and Soummya Kar

   SIAM Journal on Control and Optimization, Nov 2023

   Abs Bib HTML

   This paper studies a general class of stochastic population processes in which agents interact with one another over a network. Agents update their behaviors in a random and decentralized manner according to a policy that depends only on the agent’s current state and an estimate of the macroscopic population state, given by a weighted average of the neighboring states. When the number of agents is large and the network is a complete graph (has all-to-all information access), the macroscopic behavior of the population can be well-approximated by a set of deterministic differential equations called a \it mean-field approximation. For incomplete networks such characterizations remained previously unclear, i.e., in general whether a suitable mean-field approximation exists for the macroscopic behavior of the population. The paper addresses this gap by establishing a generic theory describing when various mean-field approximations are accurate for \empharbitrary interaction structures. Our results are threefold. Letting W be the matrix describing agent interactions, we first show that a simple mean-field approximation that incorrectly assumes a homogeneous interaction structure is accurate provided W has a large spectral gap. Second, we show that a more complex mean-field approximation which takes into account agent interactions is accurate as long as the Frobenius norm of W is small. Finally, we compare the predictions of the two mean-field approximations through simulations, highlighting cases where using mean-field approximations that assume a homogeneous interaction structure can lead to inaccurate qualitative and quantitative predictions.

   @article{sridhar2023meanfield,
     title = {Mean-field {A}pproximations for {S}tochastic {P}opulation {P}rocesses with {H}eterogeneous {I}nteractions},
     author = {Sridhar, Anirudh and Kar, Soummya},
     journal = {{SIAM} {J}ournal on {C}ontrol and {O}ptimization},
     year = {2023},
     month = nov,
     volume = {61},
     number = {6},
     pages = {3442 -- 3466},
   }

2. PNAS

   Spreading Processes with Mutations over Multi-Layer Networks

   Mansi Sood, Anirudh Sridhar, Rashad Eletreby, Chai Wah Wu, Simon A. Levin, H. Vincent Poor, and Osman Yagan

   Proceedings of the National Academy of Sciences, Jun 2023

   Abs Bib HTML

   A key scientific challenge during the outbreak of novel infectious diseases is to predict how the course of the epidemic changes under countermeasures that limit interaction in the population. Most epidemiological models do not consider the role of mutations and heterogeneity in the type of contact events. However, pathogens have the capacity to mutate in response to changing environments, especially caused by the increase in population immunity to existing strains, and the emergence of new pathogen strains poses a continued threat to public health. Further, in the light of differing transmission risks in different congregate settings (e.g., schools and offices), different mitigation strategies may need to be adopted to control the spread of infection. We analyze a multilayer multistrain model by simultaneously accounting for i) pathways for mutations in the pathogen leading to the emergence of new pathogen strains, and ii) differing transmission risks in different settings, modeled as network layers. Assuming complete cross-immunity among strains, namely, recovery from any infection prevents infection with any other (an assumption that will need to be relaxed to deal with COVID-19 or influenza), we derive the key epidemiological parameters for the multilayer multistrain framework. We demonstrate that reductions to existing models that discount heterogeneity in either the strain or the network layers may lead to incorrect predictions. Our results highlight that the impact of imposing/lifting mitigation measures concerning different contact network layers (e.g., school closures or work-from-home policies) should be evaluated in connection with their effect on the likelihood of the emergence of new strains.

   @article{sood2023spreading,
     title = {Spreading {P}rocesses with {M}utations over {M}ulti-{L}ayer {N}etworks},
     author = {Sood, Mansi and Sridhar, Anirudh and Eletreby, Rashad and Wu, Chai Wah and Levin, Simon A. and Poor, H. Vincent and Yagan, Osman},
     journal = {Proceedings of the National Academy of Sciences},
     month = jun,
     year = {2023},
     volume = {120},
     number = {24},
     pages = {e2302245120},
   }

3. IEEE-IT

   Quickest Inference of Network Cascades with Noisy Information

   Anirudh Sridhar, and H. Vincent Poor

   IEEE Transactions on Information Theory, Apr 2023

   Abs Bib HTML

   We study the problem of estimating the source of a network cascade given a time series of noisy information about the spread. Initially, there is a single vertex affected by the cascade (the source) and the cascade spreads in discrete time steps across the network. Although the cascade evolution is hidden, one observes a noisy measurement of the evolution at each time step. Given this information, we aim to reliably estimate the cascade source as fast as possible. We investigate Bayesian and minimax formulations of the source estimation problem, and derive near-optimal estimators for simple cascade dynamics and network topologies. In the Bayesian setting, samples are taken until the error of the Bayes-optimal estimator falls below a threshold. For the minimax setting, we design a novel multi-hypothesis sequential probability ratio test. These optimal estimators require \log \log n / \log (k- 1) observations for a k-regular tree network, and (\log n)^1 / (\ell + 1) observations for a \ell-dimensional lattice. We then discuss conjectures on source estimation in general topologies. Finally, we provide simulations which validate our theoretical results on trees and lattices, and illustrate the effectiveness of our methods for estimating the sources of cascades on Erdős-Rényi graphs.

   @article{sridhar2023quickesu,
     title = {Quickest {I}nference of {N}etwork {C}ascades with {N}oisy {I}nformation},
     author = {Sridhar, Anirudh and Poor, H. Vincent},
     journal = {IEEE Transactions on Information Theory},
     month = apr,
     year = {2023},
     volume = {69},
     number = {4},
     pages = {2494 -- 2522},
   }

2022

1. COLT 2022

   Exact Community Recovery in Correlated Stochastic Block Models

   Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar

   In Proceedings of the 35th Annual Conference on Learning Theory, Jul 2022

   Abs Bib HTML

   We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.

   @inproceedings{gaudio2022exact,
     title = {{E}xact {C}ommunity {R}ecovery in {C}orrelated {S}tochastic {B}lock {M}odels},
     author = {Gaudio, Julia and Rácz, Miklós Z. and Sridhar, Anirudh},
     month = jul,
     year = {2022},
     booktitle = {Proceedings of the 35th {A}nnual {C}onference on {L}earning {T}heory},
   }