Quickest Inference of Network Cascades with Noisy Information

Anirudh Sridhar, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

Abstract

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 <italic>n</italic>/ log(<italic>k</italic> - 1) observations for a <italic>k</italic>-regular tree network, and (log <italic>n</italic>) 1/&#x2113;+1 observations for a &#x2113;-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&#x0151;s-R&#x00E9;nyi graphs.

Original languageEnglish (US)
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Information Theory
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

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

Keywords

  • Adaptive algorithms
  • Bayesian methods
  • Graph theory
  • Inference algorithms
  • Minimax techniques

Fingerprint

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

Cite this