Information source detection in the SIR model: A sample path based approach
Information source detection in the SIR model: A sample path based approach
复制标题
DOI：
10.1109/ita.2013.6502991
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Kai Zhu;Lei Ying
中科院分区：
文献类型：
--
作者：
Kai Zhu;Lei Ying
本文研究了检测网络中信息源的问题，其中信息传播遵循流行的易感-感染-恢复（SIR）模型。我们假设网络中除了信息源处于感染状态之外的所有节点最初都处于易感状态。易受影响的节点可能会被感染节点感染，而感染节点可能会恢复，恢复后不会再次被感染。给定一个网络快照，我们可以从中知道所有受感染的节点，但无法区分易受影响的节点和恢复的节点，问题是根据快照和网络拓扑找到信息源。我们开发了一种基于样本路径的方法，其中选择信息源的估计器作为与最有可能导致观察到的快照的样本路径相关联的根节点。我们证明对于无限树，估计器是一个最小化到受感染节点的最大距离的节点。提出了一种反向感染算法来在一般图中找到这样的估计器。我们证明，对于 gq > 1 的 g 正则树（其中 g 是节点度，q 是感染概率），估计器以高概率与实际源保持恒定距离，与受感染节点的数量和拍摄快照的时间无关。我们的模拟结果表明，对于树形网络，反向感染算法产生的估计量比紧密中心性启发式识别的估计量更接近实际源。
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.