Diffusion archeology for diffusion progression history reconstruction.
Diffusion archeology for diffusion progression history reconstruction.
复制标题
DOI：
10.1007/s10115-015-0904-x
复制
发表时间：
2016-11
影响因子：
2.7
通讯作者：
Kingsford, Carl
中科院分区：
文献类型：
--
作者：
Sefer, Emre;Kingsford, Carl
通过图的扩散可以用来模拟许多现实世界的过程，例如疾病的传播，社交网络模因，计算机病毒或水污染物。通常情况下，现实世界中的扩散在发生时无法直接观察到-可能直到一段时间后才被注意到，连续监控成本太高，或者隐私问题限制了数据访问。这就需要从部分扩散数据中重建扩散的当前状态。在这里，我们解决的问题，重建的扩散历史从一个或多个快照的扩散状态。这种能力对于了解某些计算机节点何时被感染或哪些人是最初的疾病传播者以控制未来的扩散非常有用。我们制定这个问题的离散时间SEIRS型扩散模型的最大似然。我们设计的方法，是基于子模块和一种新的奖品收集支配集顶点覆盖（PCDSVC）松弛，可以识别可能的扩散步骤与一些可证明的性能保证。我们的方法是第一个能够重建完整的扩散历史准确地在真实的和模拟的情况。作为一种特殊情况，它们也可以比现有的方法更好地识别初始传播者。我们的研究结果为模因和污染物扩散表明，部分扩散数据的问题，可以克服适当的建模和方法，隐藏的时间特性的扩散可以预测从有限的数据。
Diffusion through graphs can be used to model many real-world processes, such as the spread of diseases, social network memes, computer viruses, or water contaminants. Often, a real-world diffusion cannot be directly observed while it is occurring — perhaps it is not noticed until some time has passed, continuous monitoring is too costly, or privacy concerns limit data access. This leads to the need to reconstruct how the present state of the diffusion came to be from partial diffusion data. Here, we tackle the problem of reconstructing a diffusion history from one or more snapshots of the diffusion state. This ability can be invaluable to learn when certain computer nodes are infected or which people are the initial disease spreaders to control future diffusions. We formulate this problem over discrete-time SEIRS-type diffusion models in terms of maximum likelihood. We design methods that are based on submodularity and a novel prize-collecting dominating-set vertex cover (PCDSVC) relaxation that can identify likely diffusion steps with some provable performance guarantees. Our methods are the first to be able to reconstruct complete diffusion histories accurately in real and simulated situations. As a special case, they can also identify the initial spreaders better than the existing methods for that problem. Our results for both meme and contaminant diffusion show that the partial diffusion data problem can be overcome with proper modeling and methods, and that hidden temporal characteristics of diffusion can be predicted from limited data.
登录
查看更多内容
DOI：
10.1073/pnas.1009094108
发表时间：
2010-12-21
影响因子：
11.1
作者：
Salathe, Marcel;Kazandjieva, Maria;Jones, James H.
通讯作者：
Jones, James H.
DOI：
10.1109/tpami.2004.60
发表时间：
2004-09-01
影响因子：
23.6
作者：
Boykov, Y;Kolmogorov, V
通讯作者：
Kolmogorov, V
影响因子：
56.9
作者：
Barabási, AL;Albert, R
通讯作者：
Albert, R
DOI：
10.1088/1742-5468/2008/10/p10008
发表时间：
2008-10-01
影响因子：
2.4
作者：
Blondel, Vincent D.;Guillaume, Jean-Loup;Lefebvre, Etienne
通讯作者：
Lefebvre, Etienne
影响因子：
4.3
作者：
Holme P
通讯作者：
Holme P