Quickest Inference of Network Cascades With Noisy Information
Quickest Inference of Network Cascades With Noisy Information
复制标题
DOI：
10.1109/tit.2022.3220185
复制
发表时间：
2021-10
影响因子：
2.5
通讯作者：
Anirudh Sridhar;H. Poor
中科院分区：
文献类型：
--
作者：
Anirudh Sridhar;H. Poor
我们研究的问题，估计源的网络级联给定的时间序列的噪声信息的传播。最初，有一个顶点受到级联（源）的影响，级联以离散的时间步长在网络中传播。虽然级联演化是隐藏的，但在每个时间步长观察到演化的噪声测量。有了这些信息，我们的目标是尽可能快地可靠地估计级联源。我们调查贝叶斯和极大极小公式的源估计问题，并获得近似最优估计简单的级联动态和网络拓扑结构。在贝叶斯设置中，采样直到贝叶斯最优估计量的误差福尔斯降到阈值以下。对于极大极小化情形，我们设计了一种新的多假设序贯概率比检验。这些最优估计需要$k$ -正则树网络的$\log \log n / \log（k - 1）$观测值和$\ell $维格点的$（\log n）^{\frac {1}{\ell + 1}}$观测值。然后，我们讨论了一般拓扑结构中的源估计。最后，我们提供了模拟，验证我们的理论结果的树和格，并说明我们的方法的有效性估计级联的来源Erdens-Rényi图。
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 n / \log (k - 1)$ observations for a $k$ -regular tree network, and $(\log n)^{\frac {1}{\ell + 1}}$ observations for a $\ell $ -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ős-Rényi graphs.