復(fù)雜網(wǎng)絡(luò)上疾病傳播溯源算法綜述
發(fā)布時(shí)間：2018-11-16 10:10
【摘要】：流感、肺結(jié)核等呼吸道傳染病嚴(yán)重威脅人類的健康,因此當(dāng)疫情爆發(fā)時(shí),快速、準(zhǔn)確地推斷疾病起源,對(duì)于疾病防控具有重要的理論意義和應(yīng)用價(jià)值.和社交網(wǎng)絡(luò)上的謠言傳播以及計(jì)算機(jī)網(wǎng)絡(luò)上的病毒傳播不同,呼吸道疾病依賴于人際物理接觸,而且具有更為復(fù)雜的疾病傳播模型.在該篇綜述里,作者首先介紹了人際接觸網(wǎng)絡(luò)、疾病傳播模型和疾病傳播溯源問題的形式化定義,以及溯源問題在傳播時(shí)間、快照覆蓋程度、傳播源數(shù)量和傳播源候選節(jié)點(diǎn)這四個(gè)層面上的推廣,給出了溯源算法的評(píng)價(jià)指標(biāo)(準(zhǔn)確率和錯(cuò)誤距離)和基于貝葉斯極大似然估計(jì)的設(shè)計(jì)脈絡(luò);然后分別分析了現(xiàn)有的溯源算法,包括基于傳染源中心性的算法、基于置信傳播的算法、基于蒙特卡洛的算法以及基于最小描述長(zhǎng)度的算法.在這四類算法中,基于傳染源中心性的算法最多,使用了包括傳播中心性、Jordan中心性、動(dòng)態(tài)年齡和無(wú)偏中介中心性共4種中心性指標(biāo),并且基于傳播中心性和Jordan中心性的算法被推廣到更為一般的情形,如多個(gè)傳播源、快照信息不完全等.作者分別在四種理想網(wǎng)絡(luò)和兩種真實(shí)人際接觸網(wǎng)絡(luò)下,實(shí)現(xiàn)并比較了常用溯源算法的性能.評(píng)估結(jié)果(包括準(zhǔn)確率、錯(cuò)誤距離、運(yùn)行時(shí)間)表明:(1)溯源算法普遍對(duì)網(wǎng)絡(luò)結(jié)構(gòu)較為敏感;(2)多數(shù)算法對(duì)疾病傳播參數(shù)具有魯棒性;(3)相對(duì)于其他算法而言,動(dòng)態(tài)消息傳遞算法盡管耗時(shí)幾乎最長(zhǎng),但具有最高的準(zhǔn)確度;(4)在耗時(shí)較短的算法中,無(wú)偏中介中心性具有相對(duì)較小的誤差距離.根據(jù)實(shí)驗(yàn)結(jié)果,根據(jù)不同的使用場(chǎng)景推薦了不同的算法:(1)當(dāng)運(yùn)行時(shí)間不重要時(shí),推薦動(dòng)態(tài)消息傳遞算法;(2)相反,當(dāng)希望快速溯源時(shí),應(yīng)該考慮基于無(wú)偏中介中心性的算法,當(dāng)網(wǎng)絡(luò)是隨機(jī)樹時(shí),Jordan中心估計(jì)算法更優(yōu);(3)反向貪心算法和動(dòng)態(tài)年齡算法分別在隨機(jī)網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)上兼顧了準(zhǔn)確率和運(yùn)行時(shí)間.最后,作者總結(jié)了該文中介紹的所有溯源算法的適用性和時(shí)間空間復(fù)雜度,討論了它們的實(shí)際應(yīng)用以及后續(xù)的免疫措施,并提出未來(lái)的研究趨勢(shì),包括研究更準(zhǔn)確的極大似然估計(jì)算法以提高算法的準(zhǔn)確度、挖掘并利用傳播過(guò)程中的信息以提高現(xiàn)有溯源算法的效率,以及考慮動(dòng)態(tài)人際接觸網(wǎng)絡(luò)以提高算法的實(shí)用性等.
[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.
【作者單位】： 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院大學(xué) 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 北京大學(xué)定量生物學(xué)中心 北京大學(xué)數(shù)學(xué)科學(xué)學(xué)院 北京大學(xué)統(tǒng)計(jì)科學(xué)中心 中國(guó)疾病預(yù)防控制中心 內(nèi)梅亨大學(xué)
【基金】：國(guó)家科技重大專項(xiàng)(2008ZX10003009-005) 國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)(2012CB316502) 國(guó)家自然科學(xué)基金(11175224,11121403,31270834,31671369,31770775,61272318) 中國(guó)科學(xué)院理論物理研究所理論物理國(guó)家重點(diǎn)實(shí)驗(yàn)室開放工程項(xiàng)目(Y4KF171CJ1)資助~~
【分類號(hào)】：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.
【作者單位】： 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院大學(xué) 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 北京大學(xué)定量生物學(xué)中心 北京大學(xué)數(shù)學(xué)科學(xué)學(xué)院 北京大學(xué)統(tǒng)計(jì)科學(xué)中心 中國(guó)疾病預(yù)防控制中心 內(nèi)梅亨大學(xué)
【基金】：國(guó)家科技重大專項(xiàng)(2008ZX10003009-005) 國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)(2012CB316502) 國(guó)家自然科學(xué)基金(11175224,11121403,31270834,31671369,31770775,61272318) 中國(guó)科學(xué)院理論物理研究所理論物理國(guó)家重點(diǎn)實(shí)驗(yàn)室開放工程項(xiàng)目(Y4KF171CJ1)資助~~
【分類號(hào)】：O157.5;R319
【相似文獻(xiàn)】
相關(guān)期刊論文 前8條
1 付立東;高琳;馬小科;;基于社團(tuán)檢測(cè)的復(fù)雜網(wǎng)絡(luò)中心性方法[J];中國(guó)科學(xué):信息科學(xué);2012年05期
2 李靜茹;喻莉;趙佳;;加權(quán)社交網(wǎng)絡(luò)節(jié)點(diǎn)中心性計(jì)算模型[J];電子科技大學(xué)學(xué)報(bào);2014年03期
3 江健;淦文燕;趙東杰;張海粟;;基于拓?fù)鋭?shì)的社會(huì)通信網(wǎng)局域中心性分析[J];系統(tǒng)工程學(xué)報(bào);2010年06期
4 陳國(guó)強(qiáng);陳亮;;一種基于資源分配策略的復(fù)雜網(wǎng)絡(luò)中心性測(cè)度[J];計(jì)算機(jī)科學(xué);2011年08期
5 邵浩;陳東方;劉欣;;復(fù)雜網(wǎng)絡(luò)算法中K-shell與介數(shù)中心性算法的實(shí)現(xiàn)[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2014年17期
6 徐健;;基于復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)影響力評(píng)價(jià)模型研究[J];軟件導(dǎo)刊;2014年03期
7 周濤;;專欄評(píng)述[J];電子科技大學(xué)學(xué)報(bào);2014年03期
8 李澤荃;張瑞新;楊w，
本文編號(hào)：2335225
本文鏈接：http://sikaile.net/kejilunwen/zidonghuakongzhilunwen/2335225.html
最近更新
教材專著
