Identifying Infection Sources and Regions in Large Networks
Identifying Infection Sources and Regions in Large Networks
复制标题
DOI：
10.1109/tsp.2013.2256902
复制
发表时间：
2013-06-01
影响因子：
5.4
通讯作者：
Leng, Mei
中科院分区：
文献类型：
--
作者：
Luo, Wuqiong;Tay, Wee Peng;Leng, Mei
识别网络中的感染源，包括将传染病引入人口网络的索引病例，将计算机病毒注入计算机网络的服务器，或在社交网络中开始谣言的个人，在通过及时隔离感染源来限制感染造成的损害方面起着关键作用。我们考虑的问题，估计感染源和感染区域（每个源感染的节点的子集）在网络中，仅基于知识的节点被感染和它们的连接，当源的数量是未知的先验。我们得到的感染源及其感染区域的估计的基础上近似的感染序列计数。我们证明，如果有最多两个感染源的几何树，我们的估计识别真正的源或源的概率去一个感染节点的数量增加。当有两个以上的感染源，当最大可能的感染源的数量是已知的，我们提出了一个算法的二次复杂性估计的实际数量和身份的感染源。对树型网络、小世界网络和真实的世界电网网络进行了仿真，并在两个真实的数据集上进行了测试，验证了估计器的性能。
Identifying the infection sources in a network, including the index cases that introduce a contagious disease into a population network, the servers that inject a computer virus into a computer network, or the individuals who started a rumor in a social network, plays a critical role in limiting the damage caused by the infection through timely quarantine of the sources. We consider the problem of estimating the infection sources and the infection regions (subsets of nodes infected by each source) in a network, based only on knowledge of which nodes are infected and their connections, and when the number of sources is unknown a priori. We derive estimators for the infection sources and their infection regions based on approximations of the infection sequences count. We prove that if there are at most two infection sources in a geometric tree, our estimator identifies the true source or sources with probability going to one as the number of infected nodes increases. When there are more than two infection sources, and when the maximum possible number of infection sources is known, we propose an algorithm with quadratic complexity to estimate the actual number and identities of the infection sources. Simulations on various kinds of networks, including tree networks, small-world networks and real world power grid networks, and tests on two real data sets are provided to verify the performance of our estimators.