Hidden Hazards: Finding Missing Nodes in Large Graph Epidemics
Hidden Hazards: Finding Missing Nodes in Large Graph Epidemics
复制标题
隐藏的危险：寻找大图流行病中缺失的节点
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
B. Prakash
中科院分区：
文献类型：
--
作者：
Shashidhar Sundareisan;Jilles Vreeken;B. Prakash
给定大图中感染的噪声或采样快照，我们能否自动可靠地恢复真正受感染但不知何故丢失的节点？而且，感染开始传播的种子、节点又如何呢？从流行病学到社交媒体，这些都是不同背景下的重要问题。在本文中，我们解决了在给定噪声数据的情况下同时恢复丢失的感染和流行病源节点的问题。我们通过最小描述长度原则来制定问题，并提出了NetFill，一种有效的算法，可以自动且高度准确地识别丢失节点和感染种子节点的数量和身份。对合成数据集和真实数据集的实验评估（包括使用超过 9600 万篇博客文章和新闻文章的信息级联数据）表明，我们的方法优于其他基线，可近乎线性扩展，并且在恢复丢失的节点和源方面非常有效。
Given a noisy or sampled snapshot of an infection in a large graph, can we automatically and reliably recover the truly infected yet somehow missed nodes? And, what about the seeds, the nodes from which the infection started to spread? These are important questions in diverse contexts, ranging from epidemiology to social media. In this paper, we address the problem of simultaneously recovering the missing infections and the source nodes of the epidemic given noisy data. We formulate the problem by the Minimum Description Length principle, and propose NetFill, an efficient algorithm that automatically and highly accurately identifies the number and identities of both missing nodes and the infection seed nodes. Experimental evaluation on synthetic and real datasets, including using data from information cascades over 96 million blog posts and news articles, shows that our method outperforms other baselines, scales near-linearly, and is highly effective in recovering missing nodes and sources.