Bayes-optimal methods for finding the source of a cascade

Anirudh Sridhar, H. Vincent Poor

Research output: Contribution to journalConference articlepeer-review

Abstract

We study the problem of estimating the source of a network cascade. The cascade initially starts from a single vertex and spreads deterministically over time, but only a noisy version of the propagation is observable. The goal is then to design a stopping time and estimator that will estimate the source well while ensuring the number of affected vertices is not too large. We rigorously formulate a Bayesian approach to the problem. If vertices can be labelled by vectors in Euclidean space (which is natural in spatial networks), the optimal estimator is the conditional mean estimator, and we derive an explicit form for the optimal stopping time under minimal assumptions on the cascade dynamics. We study the performance of the optimal stopping time on lattices, and show that a computationally efficient but suboptimal stopping time which compares the posterior variance to a threshold has near-optimal performance.

Original languageEnglish (US)
Pages (from-to)5190-5194
Number of pages5
JournalICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2021-June
DOIs
StatePublished - 2021
Event2021 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2021 - Virtual, Toronto, Canada
Duration: Jun 6 2021Jun 11 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Network cascade
  • Optimal stopping theory
  • Sequential estimation
  • Stochastic optimization

Cite this