Quickest Inference of Network Cascades
Anirudh Sridhar
Abstract:
We study the problem of estimating the source of a network cascade given a time series of noisy information about the spread. The cascade evolution is hidden, but one can observe a time series of noisy signals from each 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. 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 $(log n)^{1/(ell + 1)}$ observations are required for $ell$-dimensional lattices. Finally, we extend our estimators to the case of arbitrary networks and potentially unknown cascade dynamics, and provide a rigorous analysis of their performance.