论文标题
贝叶斯最佳方法用于查找级联的来源
Bayes-optimal Methods for Finding the Source of a Cascade
论文作者
论文摘要
我们研究估计网络级联源的问题。级联对于时间0的一个顶点开始，随着时间的推移传播，但只能观察到繁琐的传播版本。然后，目标是设计一个停止时间和估计器，该时间和估计器将很好地估算源，同时确保级联对系统的成本不大。我们严格地制定了解决该问题的贝叶斯方法。如果可以通过欧几里得空间中的向量（在地理空间网络中的天然）中标记顶点，则最佳估计器是条件均值估计器，并且我们为在级联动力学的最小假设下的最佳停止时间提供了明确的形式。我们研究了晶格上最佳停止时间的性能，并表明计算上有效但次优的停止时间将后差与阈值进行比较的阈值的性能几乎是最佳性能。
We study the problem of estimating the source of a network cascade. The cascade starts from a single vertex at time 0 and spreads over time, but only a noisy version of the propagation is observable. The goal is then to design a stopping time and estimator that will estimate the source well while ensuring the cost of the cascade to the system is not too large. We rigorously formulate a Bayesian approach to the problem. If vertices can be labelled by vectors in Euclidean space (which is natural in geo-spatial networks), the optimal estimator is the conditional mean estimator, and we derive an explicit form for the optimal stopping time under minimal assumptions on the cascade dynamics. We study the performance of the optimal stopping time on lattices, and show that a computationally efficient but suboptimal stopping time which compares the posterior variance to a threshold has near-optimal performance.
