复杂网络上疾病传播溯源算法综述

• 作者: 刘兴武 卜东波 周杨 邓明华 黄春林
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 复杂网络 疾病溯源 极大似然 置信传播 蒙特卡洛
• 年，卷（期）: 2018,（6）
• 所属期刊栏目: 云计算
• 页码范围: 1376-1399
• 页数: 24页
• 分类号: TP18
• 字数: 23619字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.01376

摘要

流感、肺结核等呼吸道传染病严重威胁人类的健康,因此当疫情爆发时,快速、准确地推断疾病起源,对于疾病防控具有重要的理论意义和应用价值.和社交网络上的谣言传播以及计算机网络上的病毒传播不同,呼吸道疾病依赖于人际物理接触,而且具有更为复杂的疾病传播模型.在该篇综述里,作者首先介绍了人际接触网络、疾病传播模型和疾病传播溯源问题的形式化定义,以及溯源问题在传播时间、快照覆盖程度、传播源数量和传播源候选节点这四个层面上的推广,给出了溯源算法的评价指标(准确率和错误距离)和基于贝叶斯极大似然估计的设计脉络;然后分别分析了现有的溯源算法,包括基于传染源中心性的算法、基于置信传播的算法、基于蒙特卡洛的算法以及基于最小描述长度的算法.在这四类算法中,基于传染源中心性的算法最多,使用了包括传播中心性、Jordan中心性、动态年龄和无偏中介中心性共4种中心性指标,并且基于传播中心性和Jordan中心性的算法被推广到更为一般的情形,如多个传播源、快照信息不完全等.作者分别在四种理想网络和两种真实人际接触网络下,实现并比较了常用溯源算法的性能.评估结果(包括准确率、错误距离、运行时间)表明:(1)溯源算法普遍对网络结构较为敏感;(2)多数算法对疾病传播参数具有鲁棒性;(3)相对于其他算法而言,动态消息传递算法尽管耗时几乎最长,但具有最高的准确度;(4)在耗时较短的算法中,无偏中介中心性具有相对较小的误差距离.根据实验结果,根据不同的使用场景推荐了不同的算法:(1)当运行时间不重要时,推荐动态消息传递算法;(2)相反,当希望快速溯源时,应该考虑基于无偏中介中心性的算法,当网络是随机树时,Jordan中心估计算法更优;(3)反向贪心算法和动态年龄算法分别在随机网络和无标度网络上兼顾了准确率和运行时间.最后,作者总结了该文中介绍的所有溯源算法的适用性和时间空间复杂度,讨论了它们的实际应用以及后续的免疫措施,并提出未来的研究趋势,包括研究更准确的极大似然估计算法以提高算法的准确度、挖掘并利用传播过程中的信息以提高现有溯源算法的效率,以及考虑动态人际接触网络以提高算法的实用性等.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卜东波	中国科学院计算技术研究所	13	455	7.0	13.0
2	黄春林	中国科学院计算技术研究所	33	765	13.0	27.0
8	刘兴武	中国科学院计算技术研究所	6	59	3.0	6.0
9	邓明华	北京大学定量生物学中心	16	115	5.0	10.0