Sequential Estimation of Network Cascades

Anirudh Sridhar, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We consider the problem of locating the source of a network cascade, given a noisy time-series of network data. Initially, the cascade starts with one unknown, affected vertex and spreads deterministically at each time step. The goal is to find an adaptive procedure that outputs an estimate for the source as fast as possible, subject to a bound on the estimation error. For a general class of graphs, we describe a family of matrix sequential probability ratio tests (MSPRTs) that are first-order asymptotically optimal up to a constant factor as the estimation error tends to zero. We apply our results to lattices and regular trees, and show that MSPRTs are asymptotically optimal for regular trees. We support our theoretical results with simulations.

Original languageEnglish (US)
Title of host publicationConference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Number of pages5
ISBN (Electronic)9780738131269
StatePublished - Nov 1 2020
Externally publishedYes
Event54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020 - Pacific Grove, United States
Duration: Nov 1 2020Nov 5 2020

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


Conference54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020
Country/TerritoryUnited States
CityPacific Grove

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Networks and Communications


  • Network cascade
  • asymptotic optimality
  • hypothesis testing
  • sequential estimation


Dive into the research topics of 'Sequential Estimation of Network Cascades'. Together they form a unique fingerprint.

Cite this