Sequential Estimation of Network Cascades

Anirudh Sridhar, H. Vincent Poor

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

Abstract

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
Pages1507-1511
Number of pages5
ISBN (Electronic)9780738131269
DOIs
StatePublished - Nov 1 2020
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
Volume2020-November
ISSN (Print)1058-6393

Conference

Conference54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020
Country/TerritoryUnited States
CityPacific Grove
Period11/1/2011/5/20

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Networks and Communications

Keywords

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

Fingerprint

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

Cite this