复杂网络上疾病传播溯源算法综述
发布时间：2018-11-16 10:10
【摘要】：流感、肺结核等呼吸道传染病严重威胁人类的健康,因此当疫情爆发时,快速、准确地推断疾病起源,对于疾病防控具有重要的理论意义和应用价值.和社交网络上的谣言传播以及计算机网络上的病毒传播不同,呼吸道疾病依赖于人际物理接触,而且具有更为复杂的疾病传播模型.在该篇综述里,作者首先介绍了人际接触网络、疾病传播模型和疾病传播溯源问题的形式化定义,以及溯源问题在传播时间、快照覆盖程度、传播源数量和传播源候选节点这四个层面上的推广,给出了溯源算法的评价指标(准确率和错误距离)和基于贝叶斯极大似然估计的设计脉络;然后分别分析了现有的溯源算法,包括基于传染源中心性的算法、基于置信传播的算法、基于蒙特卡洛的算法以及基于最小描述长度的算法.在这四类算法中,基于传染源中心性的算法最多,使用了包括传播中心性、Jordan中心性、动态年龄和无偏中介中心性共4种中心性指标,并且基于传播中心性和Jordan中心性的算法被推广到更为一般的情形,如多个传播源、快照信息不完全等.作者分别在四种理想网络和两种真实人际接触网络下,实现并比较了常用溯源算法的性能.评估结果(包括准确率、错误距离、运行时间)表明:(1)溯源算法普遍对网络结构较为敏感;(2)多数算法对疾病传播参数具有鲁棒性;(3)相对于其他算法而言,动态消息传递算法尽管耗时几乎最长,但具有最高的准确度;(4)在耗时较短的算法中,无偏中介中心性具有相对较小的误差距离.根据实验结果,根据不同的使用场景推荐了不同的算法:(1)当运行时间不重要时,推荐动态消息传递算法;(2)相反,当希望快速溯源时,应该考虑基于无偏中介中心性的算法,当网络是随机树时,Jordan中心估计算法更优;(3)反向贪心算法和动态年龄算法分别在随机网络和无标度网络上兼顾了准确率和运行时间.最后,作者总结了该文中介绍的所有溯源算法的适用性和时间空间复杂度,讨论了它们的实际应用以及后续的免疫措施,并提出未来的研究趋势,包括研究更准确的极大似然估计算法以提高算法的准确度、挖掘并利用传播过程中的信息以提高现有溯源算法的效率,以及考虑动态人际接触网络以提高算法的实用性等.
[Abstract]:Respiratory infectious diseases such as influenza tuberculosis and other respiratory diseases seriously threaten human health so it is of great theoretical significance and practical value to infer the origin of disease quickly and accurately when the epidemic occurs. Unlike the spread of rumors on social networks and the spread of viruses on computer networks, respiratory diseases depend on interpersonal physical contact and have more complex disease transmission models. In this review, the author first introduces the formal definition of interpersonal contact network, disease transmission model and disease transmission traceability, as well as the transmission time and snapshot coverage of traceability problems. Based on the generalization of the number of propagating sources and the candidate nodes of propagating sources, the evaluation index (accuracy and error distance) of traceability algorithm and the design context based on Bayesian maximum likelihood estimation are given. Then the existing traceability algorithms are analyzed, including the algorithm based on the centrality of the source of infection, the algorithm based on confidence propagation, the algorithm based on Monte Carlo and the algorithm based on the minimum description length. Among the four kinds of algorithms, the algorithm based on the centrality of source of infection is the most, and uses four kinds of central indexes, including transmission centrality, Jordan centrality, dynamic age and unbiased intermediary centrality. Moreover, the algorithms based on propagation centrality and Jordan centrality are extended to more general cases, such as multiple propagation sources, incomplete snapshot information, and so on. Under four kinds of ideal networks and two kinds of real interpersonal contact networks, the performance of common traceability algorithms is implemented and compared. The evaluation results (including accuracy, error distance, running time) show that: (1) traceability algorithms are generally sensitive to network structure, (2) most algorithms are robust to disease transmission parameters; (3) compared with other algorithms, the dynamic messaging algorithm has the highest accuracy although it takes the longest time; (4) in the algorithm with shorter time consuming, the unbiased intermediary center has a relatively small error distance. According to the experimental results, different algorithms are recommended according to different usage scenarios: (1) when the running time is not important, the dynamic messaging algorithm is recommended; (2) on the contrary, when we want to trace the source quickly, we should consider the algorithm based on unbiased intermediary centrality. When the network is a random tree, the Jordan center estimation algorithm is better; (3) the reverse greedy algorithm and the dynamic age algorithm take into account the accuracy and the running time in the random network and the scale-free network, respectively. Finally, the author summarizes the applicability and time space complexity of all the traceability algorithms introduced in this paper, discusses their practical application and the following immune measures, and puts forward the future research trend. It includes studying more accurate maximum likelihood estimation algorithm to improve the accuracy of the algorithm, mining and utilizing the information in the process of propagation to improve the efficiency of the existing traceability algorithm, and considering dynamic interpersonal contact network to improve the practicability of the algorithm.
【作者单位】： 中国科学院计算技术研究所 中国科学院大学 国家计算机网络应急技术处理协调中心 北京大学定量生物学中心 北京大学数学科学学院 北京大学统计科学中心 中国疾病预防控制中心 内梅亨大学
【基金】：国家科技重大专项(2008ZX10003009-005) 国家“九七三”重点基础研究发展规(2012CB316502) 国家自然科学基金(11175224,11121403,31270834,31671369,31770775,61272318) 中国科学院理论物理研究所理论物理国家重点实验室开放工程项目(Y4KF171CJ1)资助~~
【分类号】：O157.5;R319
[Abstract]:Respiratory infectious diseases such as influenza tuberculosis and other respiratory diseases seriously threaten human health so it is of great theoretical significance and practical value to infer the origin of disease quickly and accurately when the epidemic occurs. Unlike the spread of rumors on social networks and the spread of viruses on computer networks, respiratory diseases depend on interpersonal physical contact and have more complex disease transmission models. In this review, the author first introduces the formal definition of interpersonal contact network, disease transmission model and disease transmission traceability, as well as the transmission time and snapshot coverage of traceability problems. Based on the generalization of the number of propagating sources and the candidate nodes of propagating sources, the evaluation index (accuracy and error distance) of traceability algorithm and the design context based on Bayesian maximum likelihood estimation are given. Then the existing traceability algorithms are analyzed, including the algorithm based on the centrality of the source of infection, the algorithm based on confidence propagation, the algorithm based on Monte Carlo and the algorithm based on the minimum description length. Among the four kinds of algorithms, the algorithm based on the centrality of source of infection is the most, and uses four kinds of central indexes, including transmission centrality, Jordan centrality, dynamic age and unbiased intermediary centrality. Moreover, the algorithms based on propagation centrality and Jordan centrality are extended to more general cases, such as multiple propagation sources, incomplete snapshot information, and so on. Under four kinds of ideal networks and two kinds of real interpersonal contact networks, the performance of common traceability algorithms is implemented and compared. The evaluation results (including accuracy, error distance, running time) show that: (1) traceability algorithms are generally sensitive to network structure, (2) most algorithms are robust to disease transmission parameters; (3) compared with other algorithms, the dynamic messaging algorithm has the highest accuracy although it takes the longest time; (4) in the algorithm with shorter time consuming, the unbiased intermediary center has a relatively small error distance. According to the experimental results, different algorithms are recommended according to different usage scenarios: (1) when the running time is not important, the dynamic messaging algorithm is recommended; (2) on the contrary, when we want to trace the source quickly, we should consider the algorithm based on unbiased intermediary centrality. When the network is a random tree, the Jordan center estimation algorithm is better; (3) the reverse greedy algorithm and the dynamic age algorithm take into account the accuracy and the running time in the random network and the scale-free network, respectively. Finally, the author summarizes the applicability and time space complexity of all the traceability algorithms introduced in this paper, discusses their practical application and the following immune measures, and puts forward the future research trend. It includes studying more accurate maximum likelihood estimation algorithm to improve the accuracy of the algorithm, mining and utilizing the information in the process of propagation to improve the efficiency of the existing traceability algorithm, and considering dynamic interpersonal contact network to improve the practicability of the algorithm.
【作者单位】： 中国科学院计算技术研究所 中国科学院大学 国家计算机网络应急技术处理协调中心 北京大学定量生物学中心 北京大学数学科学学院 北京大学统计科学中心 中国疾病预防控制中心 内梅亨大学
【基金】：国家科技重大专项(2008ZX10003009-005) 国家“九七三”重点基础研究发展规(2012CB316502) 国家自然科学基金(11175224,11121403,31270834,31671369,31770775,61272318) 中国科学院理论物理研究所理论物理国家重点实验室开放工程项目(Y4KF171CJ1)资助~~
【分类号】：O157.5;R319
【相似文献】
相关期刊论文 前8条
1 付立东;高琳;马小科;;基于社团检测的复杂网络中心性方法[J];中国科学:信息科学;2012年05期
2 李静茹;喻莉;赵佳;;加权社交网络节点中心性计算模型[J];电子科技大学学报;2014年03期
3 江健;淦文燕;赵东杰;张海粟;;基于拓扑势的社会通信网局域中心性分析[J];系统工程学报;2010年06期
4 陈国强;陈亮;;一种基于资源分配策略的复杂网络中心性测度[J];计算机科学;2011年08期
5 邵浩;陈东方;刘欣;;复杂网络算法中K-shell与介数中心性算法的实现[J];现代计算机(专业版);2014年17期
6 徐健;;基于复杂网络的节点影响力评价模型研究[J];软件导刊;2014年03期
7 周涛;;专栏评述[J];电子科技大学学报;2014年03期
8 李泽荃;张瑞新;杨w，
本文编号：2335225
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2335225.html
