Quickest Inference of Network Cascades With Noisy Information

Anirudh Sridhar, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 n/log (k - 1) observations for a k -regular tree network, and (log n)1/ell + 1 observations for a ℓ-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.

Original languageEnglish (US)
Pages (from-to)2494-2522
Number of pages29
JournalIEEE Transactions on Information Theory
Issue number4
StatePublished - Apr 1 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Library and Information Sciences
  • Computer Science Applications


  • Bayesian methods
  • Graph theory
  • adaptive algorithms
  • inference algorithms
  • minimax techniques


Dive into the research topics of 'Quickest Inference of Network Cascades With Noisy Information'. Together they form a unique fingerprint.

Cite this