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

作     者：黄春林 刘兴武 邓明华 周杨 卜东波 HUANG Chun-Lin;LIU Xing-Wu;DENG Ming-Hua;ZHOU Yang;BU Dong-Bo

作者机构：中国科学院计算技术研究所北京100190 中国科学院大学北京100049 国家计算机网络应急技术处理协调中心北京100029 北京大学定量生物学中心北京100871 北京大学数学科学学院北京100871 北京大学统计科学中心北京100871 中国疾病预防控制中心北京102206 内梅亨大学 

基　　金：国家科技重大专项(2008ZX10003009-005) 国家"九七三"重点基础研究发展规(2012CB316502) 国家自然科学基金(11175224 11121403 31270834 31671369 31770775 61272318) 中国科学院理论物理研究所理论物理国家重点实验室开放工程项目(Y4KF171CJ1)资助~~ 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2018年第41卷第6期

页      码：1376-1399页

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

主 题 词：复杂网络 疾病溯源 极大似然 置信传播 蒙特卡洛 

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 0808[工学-自动化类] 0839[0839] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2018.01376

馆 藏 号：203292532...