• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>2013 Information Theory and Applications Workshop >Information source detection in the SIR model: A sample path based approach
【24h】

Information source detection in the SIR model: A sample path based approach

机译：SIR模型中的信息源检测：基于样本路径的方法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper studies the problem of detecting the information source in a network in which the spread of information follows the popular Susceptible-Infected-Recovered (SIR) model. We assume all nodes in the network are in the susceptible state initially except the information source which is in the infected state. Susceptible nodes may then be infected by infected nodes, and infected nodes may recover and will not be infected again after recovery. Given a snapshot of the network, from which we know all infected nodes but cannot distinguish susceptible nodes and recovered nodes, the problem is to find the information source based on the snapshot and the network topology. We develop a sample path based approach where the estimator of the information source is chosen to be the root node associated with the sample path that most likely leads to the observed snapshot. We prove for infinite-trees, the estimator is a node that minimizes the maximum distance to the infected nodes. A reverse-infection algorithm is proposed to find such an estimator in general graphs. We prove that for g-regular trees such that gq > 1, where g is the node degree and q is the infection probability, the estimator is within a constant distance from the actual source with high probability, independent of the number of infected nodes and the time the snapshot is taken. Our simulation results show that for tree networks, the estimator produced by the reverse-infection algorithm is closer to the actual source than the one identified by the closeness centrality heuristic.
机译：本文研究了在信息传播遵循流行的易感感染恢复（SIR）模型的网络中检测信息源的问题。我们假定网络中的所有节点最初都处于易受感染状态，但处于感染状态的信息源除外。然后，易受感染的节点可能会感染受感染的节点，并且受感染的节点可能会恢复，并且恢复后不会再次被感染。给定网络快照，我们可以从中了解所有受感染的节点，但无法区分易受感染的节点和已恢复的节点，问题在于根据快照和网络拓扑查找信息源。我们开发了一种基于样本路径的方法，在该方法中，信息源的估计量被选择为与样本路径相关联的根节点，该根节点最有可能导致观察到的快照。我们证明了对于无限树，估计器是一个节点，该节点使与感染节点的最大距离最小。提出了一种反向感染算法来在一般图中找到这种估计量。我们证明对于g-规则树，使得gq> 1，其中g是节点度，q是感染概率，估计量与实际来源之间的距离很可能是高概率，与感染节点的数量和拍摄快照的时间。我们的仿真结果表明，对于树形网络，反向感染算法产生的估计量比接近度中心性启发式算法所确定的估计量更接近实际来源。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号