基于反向感染的复合种群网络传播溯源算法  

RIA-based tracing algorithm for propagation of metapopulation networks

作　　者：阳成 王建波 许小可 杜占玮 Yang Cheng;Wang Jianbo;Xu Xiaoke;Du Zhanwei(School of Computer Science,Southwest Petroleum University,Chengdu 610500,China;School of Public Health,University of Hong Kong,Hong Kong 999077,China;Center for Computational Communication Research,Beijing Normal University,Zhuhai Guangdong 519085,China;School of Journalism&Communication,Beijing Normal University,Beijing 100875,China)

机构地区：[1]西南石油大学计算机科学学院,成都610500 [2]香港大学公共卫生学院,中国香港999077 [3]北京师范大学计算传播学研究中心,广东珠海519085 [4]北京师范大学新闻传播学院,北京100875

出　　处：《计算机应用研究》2023年第9期2681-2687,2693,共8页Application Research of Computers

基　　金：国家自然科学基金面上项目(62173065)。

摘　　要：流行病的传播会对整个人类社会构成巨大威胁,因此迅速识别传播源并及时采取控制措施至关重要。然而,由于流行病传播过程具有多样性、信息不确定性等因素,使得快速准确识别传播源成为一项挑战。结合反向感染算法、复合种群网络模型以及马尔可夫链理论,提出了一个在复合种群网络中识别传播源的新算法。该算法首先利用马尔可夫链来初步估计子种群被感染的时间,被感染子种群根据感染时间获得自己的身份信息,然后遍历所有获得感染子种群身份信息的子种群,将收集到的感染子种群身份信息传播给其所有邻居,最后根据获得所有感染子种群身份信息的时间顺序推断出复合种群网络的传播源。在真实的航空网和人造复合种群网络上进行大量仿真实验,发现无论在已知全部感染快照还是部分感染快照的情况下,该算法与其他传播溯源算法相比,识别传播源的准确性都有显著提升。该算法非常适合用于航空网这类复合种群网络,对现实世界中的流行病传播溯源和控制也具有参考意义。The spread of epidemics poses a significant threat to the entire human community.Therefore,it is critical to identify the sources of transmission quickly and take timely control measures.However,the diversity of epidemic transmission processes and information uncertainty makes it challenging to identify the sources of transmission quickly and accurately.This paper proposed a new algorithm for identifying transmission sources in a metapopulation network by combining the reverse infection algorithm and Markov chain theory.The algorithm firstly used a Markov chain to initially estimate the time when a subpopulation was infected,and the infected subpopulation obtained its own identity information based on the infection time.Then,it traversed all subpopulations that obtained the identity information of the infected subpopulation and spreaded the collected identity information of the infected subpopulation to all its neighbors.Finally,the spreading source of the metapopulation network could be inferred based on the temporal order in which all the identity information of the infected subpopulation was obtained.Simulation experiments conducted on real airports networks and artificial networks show that the accuracy of this algorithm is significantly improved compared to other algorithms,regardless of whether all or partial of the infection snapshots are known.This algorithm is well-suited for metapopulation networks such as aviation networks and is also useful for real-world epidemic transmission tracing and control.

关 键 词：复合种群网络 传播溯源算法 反向感染 计算机仿真 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]