基于局部屬性免疫策略的疾病傳播抑制研究*

王建輝,蔣 勇

(1.長沙南方職業學院 民航學院,湖南 長沙410208;2.湖南大學 信息科學與工程學院,湖南 長沙410208;3.湖南化工職業技術學院 自動化與信息工程學院,湖南 株洲412000)

1 前言

1.1 疾病傳播免疫的研究

從歷史上的西班牙大流感,到2003年的SARS病毒,H5N1禽流感,2009年的甲型H1N1流感,2013年的H7N9的禽流感病毒,2014年的西非埃博拉病毒等疫情均讓世界聞之色變,各國政府高度重視、積極措施布置防控.早期的疾病傳播研究最為廣泛的是以傳染病模型為主,該模型把人群分為三種狀態:易感態S,感染態I和免疫態R.

1.2 復雜網絡研究的興起

疾病傳播給人類帶來了巨大災難,為了抑制疾病的傳播,人們提出了不同類型的免疫策略,并逐漸思考如何站在系統的角度來控制疾病的傳播.隨著復雜系統、復雜網絡研究的興起,人們聚焦于在復雜網絡平臺上,開展疾病模型的實驗分析與探索.

復雜網絡可以通過抽象成圖的方式來描述其網絡結構,最早的圖表示方法是由歐拉對著名七橋問題的研究開始.在20世紀60年代,Erdos和Renyi建立的隨機圖理論系統研究了復雜網絡.Watts和Strogatz在Nature[1]揭示了復雜網絡的小世界特性,Barabasi和Albert在Science[2]揭示了復雜網絡的無標度特征.這些復雜網絡的基礎研究對實現疾病傳播的模擬分析,以及面向拓撲免疫策略研究,在免疫效果的深化研究上,提供了良好的數學理論與統計分析的基礎.例如劉影等[3]考慮結構拓撲,張樂延等[4]提出節點活躍度計算,陳端兵等[5]基于SIR的模擬測試,柳彤[6]提出面向交互頻次策略,聶力[7]提出局部中心性策略,方寶平[8]挖掘的臨近節點等.

1.3 面向社交網絡的研究

疾病傳播的主體是社會關系的行動者,通過接觸、交互來傳播.社交網絡主要關注的是行動者之間的交互與聯系,這種交互與聯系級聯地影響到其他行動者的社會行為.圍繞社交網絡如何構建傳播模型、如何設計免疫策略、如何搭建評價標準等問題,專家展開了相關研究.Parish等人使用“社交網絡”概念分析挪威漁村的社會結構,姚雙龍[9]提出通過控制疊加子網絡中的重復節點來抑制疫情的傳播蔓延,宋會敏[10]提出在社區間通過免疫橋節點來控制信息傳播,王龍鯨[11]提出了一種基于節點強度的網絡模型,通過SIS模型仿真驗證了高連接節點的免疫策略.

2 面向疾病傳播免疫策略的相關研究

目前對疾病傳播免疫的研究聚焦于兩個方面,一個是傳播模型的探討,即深化探索疾病的傳播機理研究;另一個是免疫策略的選擇,如何以最小的成本對某些節點進行定向免疫,大大降低疾病傳播的途徑,進而控制疫情的爆發.

2.1 傳播模型的研究

當前的疾病傳播模型主要圍繞傳染病模型和信息傳播模型展開研究.

(1)傳染病模型的相關研究.復雜網絡的疾病傳播研究是從傳播動力學展開研究的,早期疾病傳播研究最為廣泛的是以傳染病模型為主,其中SI、SIR與SIS三種經典病毒傳播模型的研究最廣.基于以上基本的疾病傳播模型,存在一些改進的模型,本文不再深入探討.

(2)信息傳播模型的相關研究.在拓撲結構的分析中,研究者發現網絡中的一些關鍵節點在傳播過程中發揮更大的作用.一些研究者從信息傳播模型的角度出發,針對這些關鍵節點進行目標性的免疫,能夠有效抑制流行病的傳播和爆發.Domingos等[12-13]提出社交網絡中的個人網絡價值概念,Kempe等、[14]Chen等[15]討論研究了兩類影響力傳播模型,即獨立級聯模型[16]和線性閾值模型,它們是目前研究最為廣泛的兩個模型.同時也存在一些其他的傳播模型,例如Even-Dar等人[17]提出的概率投票模型,以及Rodriguez等人[18]提出時變因素的傳播模型等.

(3)傳播模型小結.從傳染病模型到信息傳播模型,更加注重了社會行動者的交互行為分析,深化了傳播機理的探索;隨著社交網絡的興起,個體之間的拓撲關系在傳播過程中發揮了重要作用.

2.2 免疫機制研究

圍繞傳染病模型或信息傳播模型,人們在疾病傳播的免疫策略上展開了一系列的理論分析與實證探索,并形成了很多重要的研究成果,常見的包括:隨機免疫、目標免疫、熟人免疫等,以及多種改進型的免疫策略例如接觸免疫、環狀免疫等.

總體而言,以上免疫策略總體可分為兩類,[3]一類是面向全局屬性進行免疫,該方法需要預先掌握網絡上的所有信息,涉及節點、鏈接以及主題等相關信息;另一類是面向局部屬性進行免疫,該方法需要了解某些局部區域的節點相關信息.因此,如何利用網絡的局部信息進行免疫,降低時間復雜性、提高免疫效果,設計出高效的免疫策略成為研究的重點.

(1)面向全局屬性的免疫.全局屬性需要統籌網絡拓撲的全局屬性,雖然可以準確地識別關鍵節點,免疫效果最優.但是全局屬性信息的計算難度很大,難以快速實現.當前全局屬性的計算主要有以下方法:介數中心性,接近中心性,[19]特征向量中心性,k-殼中心性.[20]

(2)面向局部屬性的免疫.局部屬性免疫是利用已知的局部屬性信息,進而選擇目標展開快速免疫抑制疾病傳播,更具有實際的可操作性.主要包括:度中心性,隨機免疫,目標免疫,熟人免疫等,以及一些研究者從社區研究的角度出發提出的區域免疫,通過社區橋節點開展免疫研究,[21-24]取得了一定進展.

(3)免疫機制小結.免疫策略是通過對目標節點進行定向免疫,以便阻斷進一步的傳播路徑、抑制疾病的傳播擴散.當前研究的重點在如何選取最少的免疫節點,進而實現最大化的抑制疾病傳播.當前從全局屬性到局部屬性的免疫策略,不斷地降低了時間復雜性,但是當前的局部信息仍需要進一步的集成計算節點屬性或者拓撲屬性,對于時效性敏感的免疫策略而言,還存在較大的提升空間.

3 基于局部屬性計算的免疫機制研究

3.1 問題定義

基于目前的研究,我們考慮疾病傳播中的目標免疫機制,實驗方法以蒙特卡洛模擬為基準進行測試.問題定義為:面對初始化節點集為d的疾病傳播,如何快速選擇或者部署規模為k的免疫節點集,使得最大化的抑制疾病傳播(或最終疾病傳播的范圍最少)?

3.2 主要思想

本文提出基于社區定位的局部屬性免疫策略,期望提升免疫效果,降低時間復雜性.首先,采用標簽傳播的方式進行社區劃分,對初始疾病節點的傳播網絡進行社區級的粗粒度定位;其次,立足每個疾病節點所在的社區內,按照比例輪循選擇社區內具有高鏈接、高中心性的節點,實現局部區域內免疫的候選集快速發現;最后,基于信息傳播模型在社交網絡上展開蒙特卡洛模擬,對疾病傳播下的免疫策略效果進行量化計算與對比評估.

3.3 變量定義

本文所使用的變量定義如表1所示.

表1 所使用的變量Tab.1 Description of variables used

3.4 計算過程

3.4.1 初始疾病傳播節點設置

在疾病傳播節點的初始設置上,選擇兩種方式,一種是基于隨機節點集的疾病傳播,另一種是基于最大度節點集的疾病傳播,對比兩種疾病傳播模式情況,不同免疫策略對其產生的抑制效果.(為了便于實驗的統一計算,在疾病傳播節點的定位上,按照社區分別選取,避免疾病擴散可能出現的交叉重疊,以便測試在盡量促使初始疾病節點擴散的基礎上,開展不同類型免疫策略的對比分析.)

3.4.2 免疫傳播節點集的選擇

本文提出基于社區的局部屬性免疫算法(Local Attribute based on Community,簡稱LAC算法),主要有兩個步驟,具體如算法1所示.

(1)基于標簽的社區劃分.

從社區的角度來選擇節點,需要在社交網絡上劃分有意義的社區結構.但是傳統的面向圖劃分、聚類等方法不適于直接社區劃分,因為它需要預先知道社區的全局屬性.本文采用基于標簽傳播的方法進行快速的社區劃分.[25]

(2)區域性中心節點選擇.

在社區中選取高鏈接、高中心性的節點,我們認為在社區內,節點自身屬性以及鄰居節點屬性都兼顧的節點具有較好的免疫效果.因此通過對疾病傳播節點的社區定位,對位于局部社區內的進行二重屬性的高鏈接節點快速計算;然后,按照社區容量的比例輪循添加,形成候選節點集;最后計算排序選擇免疫節點集.

3.4.3 免疫效果模擬評估

(1)信息模型構建.

算法需要在信息傳播模型的一種(本文選取獨立級聯模型)進行驗證,在每條邊(u,v)上隨機選擇概率,分別調節著影響級別的強弱.

(2)蒙特卡洛模擬.

影響力范圍:為了更好估算這些免疫策略下的抑制效果,我們分別在獨立級聯模型上通過蒙特卡洛模擬來進行量化計算(Monte Carlo Simulation,簡稱MCS),具體如算法2所示.

(3)算法執行步驟.

算法1 LAC算法執行過程如下所示:

Algorithm 1:LAC

Input:Graph:G,the amount of virus seeds:d

Output:Top-kimmune seeds

1:initializeS=?,S C=?

2:community partition and getzcommunities:

C1,C2,…,C x

3:fori=1 toddo

5:compute the amount of vertices of communities

with virus seeds:S C

6:end for

7:fori=1 toddo

8:in communityC i,compute the LAvvalue of

each vertex

9:compute amount of candidate vertices:t

10:compute the selected amount of immune

seeds:h=(t·k)/S C

雖然多數學者原則上支持會聚研究和組織結構創新，但在涉及本人或部門利益時往往退縮。因此，探索有效的機構組織形式，在兼顧現有組織文化的同時創建以科學或社會挑戰為核心的新型研究組織方式，制定合理的會聚項目評審標準、任務分配制度和績效考核指標，以促進不同學科背景的科研人員間高效的合作伙伴關系，是科研機構亟待解決的問題。

11:forj=1 tohdo

12:find the vertex with maximal LAvand add to

Candidate setS C

13:end for

14:end for

15:for j=1 to k do

16:find the vertex with maximal LAvand add to S

17:end for

18:return S

算法2 MCS算法具體執行過程如下所示:

Algorithm 2:Monte Carlo Simulation

Input:Graph:G,the amount of virus seeds:d

Output:Compute the propagation value of simulation

1:initialize S=?,

2:for each vertex v∈Sddo

3: GSv=0

4: for i=1 to R do

5: GSv+=|Sim(S∪{v})|

6: end for

7: GSv=GSv/R and store current vertex v in the Array

8:end for

9:sort the vertices of Array in the descending order by v

(4)算法效率分析.

算法1:主要進行面向區域定位的免疫節點發現.第2步是進行面向標簽傳播的社區劃分,時間復雜性為O(E);第3～6步是對疾病傳播節點進行社區定位,時間復雜性為O(d);第7～14步是在每個社區中輪循選擇區域中心節點,時間復雜性為O(dh);第15～17步是在候選集中按照排序選擇k個免疫節點,時間復雜性為O(k).此時,總體復雜性=O(E)+O(d)+O(dh)+O(k)=O(E).

算法2:主要為免疫策略提供蒙特卡洛模擬評估.第2步是篩選節點集開展循環,第4～6步是開展R次蒙特卡洛模擬計算,第7步是求取平均值.此時,總體復雜性=O(d ER).

4 實驗分析

4.1 實驗設置

(1)實驗環境.

處理器:Intel的雙核CPU,2.60 GHz主頻;內存:16 G;操作系統:Windows 7 64位.

(2)實驗數據.

實驗數據來自Arxiv的學術論文的合作數據集,為了進行基準對比,對網絡規模進行了統一,將3個數據集的節點規模限制為2000.其中,Gr Qc:廣義相對論領域,邊數目是3963;Dblp:計算機領域,邊數目是4035;Phy:物理學領域,邊數目是6660.

(3)初始設置.

初始傳染節點種子集個數:5.

初始傳染節點生成方式:隨機生成方法和最大度生成方法.

免疫種子集個數:100.

蒙特卡洛模擬次數:2000.

(4)對比方法.

隨機點免疫:本文使用Random來代替,試驗中簡寫為RanIM.

最大度免疫:本文使用MaxDegree來代替,試驗中簡寫為MdIM.

度折扣方法免疫:本文使用DDiscount Heuristic來代替,試驗中簡寫為DdIM.

介數中心性免疫:本文使用Betweeness來代替,試驗中簡寫為BetIM.

社區中心性免疫:本文使用LAC來代替(本文算法1),試驗中簡寫為LacIM.

熟人免疫:基于初始感染節點和免疫節點的不同數量,考慮到初始感染節點的分布性,無法在同一標準下選擇該策略下的免疫節點,因此本文忽略此對比方法.

貪心算法免疫:貪心算法在傳染病抑制上可以獲得全局的最優解,但是每次迭代需要在全網計算比較一次最優解,其時間復雜性較高(k·N·E·R),因此本文忽略此對比方法.

圖1 疾病隨機傳播下的免疫策略對比(Gr Qc)Fig.1 Comparison of immunization strategies under random disease spread(Gr Qc)

圖2 疾病隨機傳播下的免疫策略對比(dblp)Fig.2 Comparison of immunization strategies under random disease spread(dblp)

圖3 疾病隨機傳播下的免疫策略對比(phy)Fig.3 Comparison of immunization strategies under random disease spread(phy)

圖4 疾病最大度傳播下的免疫策略對比(Gr Qc)Fig.4 Comparison of immunization strategies under the maximum spread of disease(Gr Qc)

圖5 疾病最大度傳播下的免疫策略對比(dblp)Fig.5 Comparison of immunization strategies under the maximum spread of disease(dblp)

圖6 疾病最大度傳播下的免疫策略對比(phy)Fig.6 Comparison of immunization strategies under the maximum spread of disease(phy)

4.2 結果分析

4.2.1 時間復雜性評價

隨機節點免疫的時間復雜性是常數項,可忽略;最大度免疫(MdIM)的時間復雜性為O(N),度折扣方法免疫(DdIM)時間復雜性為O(k·log(N)+E),介數中心性免疫(BetIM)最大時間復雜性為O(N3),最小時間復雜性為O(N*E),本文所提出的社區中心性免疫(LacIM)的時間復雜性為O(E).

4.2.2 抑制傳播范圍評價

分別從隨機和最大度的方法生成初始感染節點,分別對免疫策略進行對比分析.

(1)基于隨機方法生成初始感染節點.

從整體上而言,本文提出的LAC免疫策略在降低疾病傳播上效果最優.如圖1、圖2和圖3所示.基于Gr Qc、dblp、phy數據集上,LAC免疫策略在免疫節點集達到98、80、60個的時候,開始與其他的策略拉開距離,并隨后逐漸體現出了較好的免疫效果.對于介數中心性免疫策略,在Gr Qc數據集上的效果較好(如圖1所示),在dblp數據上效果居中,在phy數據集上效果最差,說明該策略受網絡拓撲結構的影響不穩定.而最大度免疫、度折扣免疫等策略,在不同數據集上效果不一;3個數據集屬于無標度網絡,在均勻網絡上性能較優的隨機免疫策略,在該數據集上的效果最差.

(2)基于最大度策略生成初始感染節點.

從整體上而言,與隨機感染方式類似,本文提出的LAC免疫策略在降低疾病傳播上效果最優.如圖4、圖5和圖6所示,基于Gr Qc、dblp、phy數據集上,LAC免疫策略在免疫節點集達到98、78、80個的時候,開始與其他的策略拉開距離,并隨后逐漸體現出了較好的免疫效果.與隨機感染方式類似,對于介數中心性免疫策略,在Gr Qc數據集上的效果較好(如圖4所示),其余2個數據集效果不佳,說明該策略受網絡拓撲結構的影響較大.而最大度策略、度折扣策略等免疫效果,在3個數據上效果居中;基于相同的原因,隨機免疫策略的效果最差.

小結:從兩種初始感染節點的傳播范圍來看,隨機節點集的初始疾病傳播范圍要大于最大度節點集的初始疾病傳播范圍,主要是社交網絡具有的無尺度特性,一些高度數節點往往基于“優先鏈接”特性,存在很大的高節點鄰居特性,造成了相互之間的初始疾病傳播存在很大的重疊空間,消減了一部分的擴散范圍.從多種免疫策略的對比來看,面向不同數據集本文提出的LAC免疫策略效果顯示最優,且在兩種初始感染節點方式上的性能穩定,時間復雜度可規約為線性級.

5 結論

本文從信息傳播模型,提出了基于社區的局部屬性免疫策略能夠在有效降低疾病的傳播范圍,維持了線性級的時間復雜性;在與最大度免疫、介數中心性免疫、度折扣免疫等免疫策略相比,實驗結果驗證了本文所提方法的有效性.下一步的研究是聚焦社交網絡的動態變化特性,來加速免疫節點集的發現過程.