Diffusion Source Identification on Networks with Statistical Confidence
Diffusion Source Identification on Networks with Statistical Confidence
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Quinlan Dawkins;Tianxi Li;Haifeng Xu
中科院分区：
文献类型：
--
作者：
Quinlan Dawkins;Tianxi Li;Haifeng Xu
网络扩散源识别在谣言控制和病毒识别等广泛的应用中具有重要意义。虽然这个问题最近受到了极大的关注，但大多数研究都只关注非常严格的设置，缺乏更现实的网络的理论保证。我们引入了一个统计框架的研究扩散源识别和发展的置信集推理方法的假设检验的启发。我们的方法有效地产生了一个小的节点子集，它可证明覆盖源节点与任何预先指定的置信水平，没有限制性的假设网络结构。此外，我们提出了多个Monte Carlo策略的推理过程的基础上，网络拓扑结构和概率属性，显着提高了可扩展性。据我们所知，这是第一个扩散源识别方法，在一般网络上有实际有用的理论保证。我们通过对著名的随机网络模型、数百个真实网络的大型数据集以及城市之间关于COVID-19传播的移动网络进行广泛的合成实验来展示我们的方法。
Diffusion source identification on networks is a problem of fundamental importance in a broad class of applications, including rumor controlling and virus identification. Though this problem has received significant recent attention, most studies have focused only on very restrictive settings and lack theoretical guarantees for more realistic networks. We introduce a statistical framework for the study of diffusion source identification and develop a confidence set inference approach inspired by hypothesis testing. Our method efficiently produces a small subset of nodes, which provably covers the source node with any prespecified confidence level without restrictive assumptions on network structures. Moreover, we propose multiple Monte Carlo strategies for the inference procedure based on network topology and the probabilistic properties that significantly improve the scalability. To our knowledge, this is the first diffusion source identification method with a practically useful theoretical guarantee on general networks. We demonstrate our approach via extensive synthetic experiments on well-known random network models, a large data set of hundreds of real-world networks, as well as a mobility network between cities concerning the COVID-19 spreading.