Quickest Inference of Network Cascades With Noisy Information

DOI10.1109/TIT.2022.3220185arXiv2110.08115OpenAlexW4309125260MaRDI QIDQ6153682FDOQ6153682

Authors: Anirudh Sridhar, H. Vincent Poor 

Publication date: 19 March 2024

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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. The cascade evolution is hidden, but one can observe a time series of noisy signals from each vertex. The time series of a vertex is assumed to be a sequence of i.i.d. samples from a pre-change distribution $Q_0$ before the cascade affects the vertex, and the time series is a sequence of i.i.d. samples from a post-change distribution $Q_1$ once the cascade has affected the vertex. Given the time series of noisy signals, which can be viewed as a noisy measurement of the cascade evolution, we aim to devise a procedure 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, an estimator which observes samples until the error of the Bayes-optimal estimator falls below a threshold achieves optimal performance. In the minimax setting, optimal performance is achieved by designing a novel multi-hypothesis sequential probability ratio test (MSPRT). We find that these optimal estimators require $loglogn/log(k-1)$ observations of the noisy time series when the network topology is a $k$-regular tree, and $(logn{)}^{frac1ell+1}$ observations are required for $ell$-dimensional lattices. Finally, we discuss how our methods may be extended to cascades on arbitrary graphs.

Full work available at URL: https://arxiv.org/abs/2110.08115

zbMATH Keywords

Bayesian methodsgraph theoryadaptive algorithmsinference algorithmsminimax techniques

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

This page was built for publication: Quickest Inference of Network Cascades With Noisy Information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153682)