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

王建輝,蔣 勇

(1.長(zhǎng)沙南方職業(yè)學(xué)院 民航學(xué)院,湖南 長(zhǎng)沙410208;2.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙410208;3.湖南化工職業(yè)技術(shù)學(xué)院 自動(dòng)化與信息工程學(xué)院,湖南 株洲412000)

1 前言

1.1 疾病傳播免疫的研究

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

1.2 復(fù)雜網(wǎng)絡(luò)研究的興起

疾病傳播給人類帶來(lái)了巨大災(zāi)難,為了抑制疾病的傳播,人們提出了不同類型的免疫策略,并逐漸思考如何站在系統(tǒng)的角度來(lái)控制疾病的傳播.隨著復(fù)雜系統(tǒng)、復(fù)雜網(wǎng)絡(luò)研究的興起,人們聚焦于在復(fù)雜網(wǎng)絡(luò)平臺(tái)上,開展疾病模型的實(shí)驗(yàn)分析與探索.

復(fù)雜網(wǎng)絡(luò)可以通過抽象成圖的方式來(lái)描述其網(wǎng)絡(luò)結(jié)構(gòu),最早的圖表示方法是由歐拉對(duì)著名七橋問題的研究開始.在20世紀(jì)60年代,Erdos和Renyi建立的隨機(jī)圖理論系統(tǒng)研究了復(fù)雜網(wǎng)絡(luò).Watts和Strogatz在Nature[1]揭示了復(fù)雜網(wǎng)絡(luò)的小世界特性,Barabasi和Albert在Science[2]揭示了復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度特征.這些復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)研究對(duì)實(shí)現(xiàn)疾病傳播的模擬分析,以及面向拓?fù)涿庖卟呗匝芯?在免疫效果的深化研究上,提供了良好的數(shù)學(xué)理論與統(tǒng)計(jì)分析的基礎(chǔ).例如劉影等[3]考慮結(jié)構(gòu)拓?fù)?張樂延等[4]提出節(jié)點(diǎn)活躍度計(jì)算,陳端兵等[5]基于SIR的模擬測(cè)試,柳彤[6]提出面向交互頻次策略,聶力[7]提出局部中心性策略,方寶平[8]挖掘的臨近節(jié)點(diǎn)等.

1.3 面向社交網(wǎng)絡(luò)的研究

疾病傳播的主體是社會(huì)關(guān)系的行動(dòng)者,通過接觸、交互來(lái)傳播.社交網(wǎng)絡(luò)主要關(guān)注的是行動(dòng)者之間的交互與聯(lián)系,這種交互與聯(lián)系級(jí)聯(lián)地影響到其他行動(dòng)者的社會(huì)行為.圍繞社交網(wǎng)絡(luò)如何構(gòu)建傳播模型、如何設(shè)計(jì)免疫策略、如何搭建評(píng)價(jià)標(biāo)準(zhǔn)等問題,專家展開了相關(guān)研究.Parish等人使用“社交網(wǎng)絡(luò)”概念分析挪威漁村的社會(huì)結(jié)構(gòu),姚雙龍[9]提出通過控制疊加子網(wǎng)絡(luò)中的重復(fù)節(jié)點(diǎn)來(lái)抑制疫情的傳播蔓延,宋會(huì)敏[10]提出在社區(qū)間通過免疫橋節(jié)點(diǎn)來(lái)控制信息傳播,王龍?chǎng)L[11]提出了一種基于節(jié)點(diǎn)強(qiáng)度的網(wǎng)絡(luò)模型,通過SIS模型仿真驗(yàn)證了高連接節(jié)點(diǎn)的免疫策略.

2 面向疾病傳播免疫策略的相關(guān)研究

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

2.1 傳播模型的研究

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

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

(2)信息傳播模型的相關(guān)研究.在拓?fù)浣Y(jié)構(gòu)的分析中,研究者發(fā)現(xiàn)網(wǎng)絡(luò)中的一些關(guān)鍵節(jié)點(diǎn)在傳播過程中發(fā)揮更大的作用.一些研究者從信息傳播模型的角度出發(fā),針對(duì)這些關(guān)鍵節(jié)點(diǎn)進(jìn)行目標(biāo)性的免疫,能夠有效抑制流行病的傳播和爆發(fā).Domingos等[12-13]提出社交網(wǎng)絡(luò)中的個(gè)人網(wǎng)絡(luò)價(jià)值概念,Kempe等、[14]Chen等[15]討論研究了兩類影響力傳播模型,即獨(dú)立級(jí)聯(lián)模型[16]和線性閾值模型,它們是目前研究最為廣泛的兩個(gè)模型.同時(shí)也存在一些其他的傳播模型,例如Even-Dar等人[17]提出的概率投票模型,以及Rodriguez等人[18]提出時(shí)變因素的傳播模型等.

(3)傳播模型小結(jié).從傳染病模型到信息傳播模型,更加注重了社會(huì)行動(dòng)者的交互行為分析,深化了傳播機(jī)理的探索;隨著社交網(wǎng)絡(luò)的興起,個(gè)體之間的拓?fù)潢P(guān)系在傳播過程中發(fā)揮了重要作用.

2.2 免疫機(jī)制研究

圍繞傳染病模型或信息傳播模型,人們?cè)诩膊鞑サ拿庖卟呗陨险归_了一系列的理論分析與實(shí)證探索,并形成了很多重要的研究成果,常見的包括:隨機(jī)免疫、目標(biāo)免疫、熟人免疫等,以及多種改進(jìn)型的免疫策略例如接觸免疫、環(huán)狀免疫等.

總體而言,以上免疫策略總體可分為兩類,[3]一類是面向全局屬性進(jìn)行免疫,該方法需要預(yù)先掌握網(wǎng)絡(luò)上的所有信息,涉及節(jié)點(diǎn)、鏈接以及主題等相關(guān)信息;另一類是面向局部屬性進(jìn)行免疫,該方法需要了解某些局部區(qū)域的節(jié)點(diǎn)相關(guān)信息.因此,如何利用網(wǎng)絡(luò)的局部信息進(jìn)行免疫,降低時(shí)間復(fù)雜性、提高免疫效果,設(shè)計(jì)出高效的免疫策略成為研究的重點(diǎn).

(1)面向全局屬性的免疫.全局屬性需要統(tǒng)籌網(wǎng)絡(luò)拓?fù)涞娜謱傩?雖然可以準(zhǔn)確地識(shí)別關(guān)鍵節(jié)點(diǎn),免疫效果最優(yōu).但是全局屬性信息的計(jì)算難度很大,難以快速實(shí)現(xiàn).當(dāng)前全局屬性的計(jì)算主要有以下方法:介數(shù)中心性,接近中心性,[19]特征向量中心性,k-殼中心性.[20]

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

(3)免疫機(jī)制小結(jié).免疫策略是通過對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行定向免疫,以便阻斷進(jìn)一步的傳播路徑、抑制疾病的傳播擴(kuò)散.當(dāng)前研究的重點(diǎn)在如何選取最少的免疫節(jié)點(diǎn),進(jìn)而實(shí)現(xiàn)最大化的抑制疾病傳播.當(dāng)前從全局屬性到局部屬性的免疫策略,不斷地降低了時(shí)間復(fù)雜性,但是當(dāng)前的局部信息仍需要進(jìn)一步的集成計(jì)算節(jié)點(diǎn)屬性或者拓?fù)鋵傩?對(duì)于時(shí)效性敏感的免疫策略而言,還存在較大的提升空間.

3 基于局部屬性計(jì)算的免疫機(jī)制研究

3.1 問題定義

基于目前的研究,我們考慮疾病傳播中的目標(biāo)免疫機(jī)制,實(shí)驗(yàn)方法以蒙特卡洛模擬為基準(zhǔn)進(jìn)行測(cè)試.問題定義為:面對(duì)初始化節(jié)點(diǎn)集為d的疾病傳播,如何快速選擇或者部署規(guī)模為k的免疫節(jié)點(diǎn)集,使得最大化的抑制疾病傳播(或最終疾病傳播的范圍最少)?

3.2 主要思想

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

3.3 變量定義

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

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

3.4 計(jì)算過程

3.4.1 初始疾病傳播節(jié)點(diǎn)設(shè)置

在疾病傳播節(jié)點(diǎn)的初始設(shè)置上,選擇兩種方式,一種是基于隨機(jī)節(jié)點(diǎn)集的疾病傳播,另一種是基于最大度節(jié)點(diǎn)集的疾病傳播,對(duì)比兩種疾病傳播模式情況,不同免疫策略對(duì)其產(chǎn)生的抑制效果.(為了便于實(shí)驗(yàn)的統(tǒng)一計(jì)算,在疾病傳播節(jié)點(diǎn)的定位上,按照社區(qū)分別選取,避免疾病擴(kuò)散可能出現(xiàn)的交叉重疊,以便測(cè)試在盡量促使初始疾病節(jié)點(diǎn)擴(kuò)散的基礎(chǔ)上,開展不同類型免疫策略的對(duì)比分析.)

3.4.2 免疫傳播節(jié)點(diǎn)集的選擇

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

(1)基于標(biāo)簽的社區(qū)劃分.

從社區(qū)的角度來(lái)選擇節(jié)點(diǎn),需要在社交網(wǎng)絡(luò)上劃分有意義的社區(qū)結(jié)構(gòu).但是傳統(tǒng)的面向圖劃分、聚類等方法不適于直接社區(qū)劃分,因?yàn)樗枰A(yù)先知道社區(qū)的全局屬性.本文采用基于標(biāo)簽傳播的方法進(jìn)行快速的社區(qū)劃分.[25]

(2)區(qū)域性中心節(jié)點(diǎn)選擇.

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

3.4.3 免疫效果模擬評(píng)估

(1)信息模型構(gòu)建.

算法需要在信息傳播模型的一種(本文選取獨(dú)立級(jí)聯(lián)模型)進(jìn)行驗(yàn)證,在每條邊(u,v)上隨機(jī)選擇概率,分別調(diào)節(jié)著影響級(jí)別的強(qiáng)弱.

(2)蒙特卡洛模擬.

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

(3)算法執(zhí)行步驟.

算法1 LAC算法執(zhí)行過程如下所示:

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

雖然多數(shù)學(xué)者原則上支持會(huì)聚研究和組織結(jié)構(gòu)創(chuàng)新，但在涉及本人或部門利益時(shí)往往退縮。因此，探索有效的機(jī)構(gòu)組織形式，在兼顧現(xiàn)有組織文化的同時(shí)創(chuàng)建以科學(xué)或社會(huì)挑戰(zhàn)為核心的新型研究組織方式，制定合理的會(huì)聚項(xiàng)目評(píng)審標(biāo)準(zhǔn)、任務(wù)分配制度和績(jī)效考核指標(biāo)，以促進(jìn)不同學(xué)科背景的科研人員間高效的合作伙伴關(guān)系，是科研機(jī)構(gòu)亟待解決的問題。

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算法具體執(zhí)行過程如下所示:

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:主要進(jìn)行面向區(qū)域定位的免疫節(jié)點(diǎn)發(fā)現(xiàn).第2步是進(jìn)行面向標(biāo)簽傳播的社區(qū)劃分,時(shí)間復(fù)雜性為O(E);第3～6步是對(duì)疾病傳播節(jié)點(diǎn)進(jìn)行社區(qū)定位,時(shí)間復(fù)雜性為O(d);第7～14步是在每個(gè)社區(qū)中輪循選擇區(qū)域中心節(jié)點(diǎn),時(shí)間復(fù)雜性為O(dh);第15～17步是在候選集中按照排序選擇k個(gè)免疫節(jié)點(diǎn),時(shí)間復(fù)雜性為O(k).此時(shí),總體復(fù)雜性=O(E)+O(d)+O(dh)+O(k)=O(E).

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

(1)實(shí)驗(yàn)環(huán)境.

處理器:Intel的雙核CPU,2.60 GHz主頻;內(nèi)存:16 G;操作系統(tǒng):Windows 7 64位.

(2)實(shí)驗(yàn)數(shù)據(jù).

實(shí)驗(yàn)數(shù)據(jù)來(lái)自Arxiv的學(xué)術(shù)論文的合作數(shù)據(jù)集,為了進(jìn)行基準(zhǔn)對(duì)比,對(duì)網(wǎng)絡(luò)規(guī)模進(jìn)行了統(tǒng)一,將3個(gè)數(shù)據(jù)集的節(jié)點(diǎn)規(guī)模限制為2000.其中,Gr Qc:廣義相對(duì)論領(lǐng)域,邊數(shù)目是3963;Dblp:計(jì)算機(jī)領(lǐng)域,邊數(shù)目是4035;Phy:物理學(xué)領(lǐng)域,邊數(shù)目是6660.

(3)初始設(shè)置.

初始傳染節(jié)點(diǎn)種子集個(gè)數(shù):5.

初始傳染節(jié)點(diǎn)生成方式:隨機(jī)生成方法和最大度生成方法.

免疫種子集個(gè)數(shù):100.

蒙特卡洛模擬次數(shù):2000.

(4)對(duì)比方法.

隨機(jī)點(diǎn)免疫:本文使用Random來(lái)代替,試驗(yàn)中簡(jiǎn)寫為RanIM.

最大度免疫:本文使用MaxDegree來(lái)代替,試驗(yàn)中簡(jiǎn)寫為MdIM.

度折扣方法免疫:本文使用DDiscount Heuristic來(lái)代替,試驗(yàn)中簡(jiǎn)寫為DdIM.

介數(shù)中心性免疫:本文使用Betweeness來(lái)代替,試驗(yàn)中簡(jiǎn)寫為BetIM.

社區(qū)中心性免疫:本文使用LAC來(lái)代替(本文算法1),試驗(yàn)中簡(jiǎn)寫為L(zhǎng)acIM.

熟人免疫:基于初始感染節(jié)點(diǎn)和免疫節(jié)點(diǎn)的不同數(shù)量,考慮到初始感染節(jié)點(diǎn)的分布性,無(wú)法在同一標(biāo)準(zhǔn)下選擇該策略下的免疫節(jié)點(diǎn),因此本文忽略此對(duì)比方法.

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

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

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

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

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

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

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

4.2 結(jié)果分析

4.2.1 時(shí)間復(fù)雜性評(píng)價(jià)

隨機(jī)節(jié)點(diǎn)免疫的時(shí)間復(fù)雜性是常數(shù)項(xiàng),可忽略;最大度免疫(MdIM)的時(shí)間復(fù)雜性為O(N),度折扣方法免疫(DdIM)時(shí)間復(fù)雜性為O(k·log(N)+E),介數(shù)中心性免疫(BetIM)最大時(shí)間復(fù)雜性為O(N3),最小時(shí)間復(fù)雜性為O(N*E),本文所提出的社區(qū)中心性免疫(LacIM)的時(shí)間復(fù)雜性為O(E).

4.2.2 抑制傳播范圍評(píng)價(jià)

分別從隨機(jī)和最大度的方法生成初始感染節(jié)點(diǎn),分別對(duì)免疫策略進(jìn)行對(duì)比分析.

(1)基于隨機(jī)方法生成初始感染節(jié)點(diǎn).

從整體上而言,本文提出的LAC免疫策略在降低疾病傳播上效果最優(yōu).如圖1、圖2和圖3所示.基于Gr Qc、dblp、phy數(shù)據(jù)集上,LAC免疫策略在免疫節(jié)點(diǎn)集達(dá)到98、80、60個(gè)的時(shí)候,開始與其他的策略拉開距離,并隨后逐漸體現(xiàn)出了較好的免疫效果.對(duì)于介數(shù)中心性免疫策略,在Gr Qc數(shù)據(jù)集上的效果較好(如圖1所示),在dblp數(shù)據(jù)上效果居中,在phy數(shù)據(jù)集上效果最差,說明該策略受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響不穩(wěn)定.而最大度免疫、度折扣免疫等策略,在不同數(shù)據(jù)集上效果不一;3個(gè)數(shù)據(jù)集屬于無(wú)標(biāo)度網(wǎng)絡(luò),在均勻網(wǎng)絡(luò)上性能較優(yōu)的隨機(jī)免疫策略,在該數(shù)據(jù)集上的效果最差.

(2)基于最大度策略生成初始感染節(jié)點(diǎn).

從整體上而言,與隨機(jī)感染方式類似,本文提出的LAC免疫策略在降低疾病傳播上效果最優(yōu).如圖4、圖5和圖6所示,基于Gr Qc、dblp、phy數(shù)據(jù)集上,LAC免疫策略在免疫節(jié)點(diǎn)集達(dá)到98、78、80個(gè)的時(shí)候,開始與其他的策略拉開距離,并隨后逐漸體現(xiàn)出了較好的免疫效果.與隨機(jī)感染方式類似,對(duì)于介數(shù)中心性免疫策略,在Gr Qc數(shù)據(jù)集上的效果較好(如圖4所示),其余2個(gè)數(shù)據(jù)集效果不佳,說明該策略受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響較大.而最大度策略、度折扣策略等免疫效果,在3個(gè)數(shù)據(jù)上效果居中;基于相同的原因,隨機(jī)免疫策略的效果最差.

小結(jié):從兩種初始感染節(jié)點(diǎn)的傳播范圍來(lái)看,隨機(jī)節(jié)點(diǎn)集的初始疾病傳播范圍要大于最大度節(jié)點(diǎn)集的初始疾病傳播范圍,主要是社交網(wǎng)絡(luò)具有的無(wú)尺度特性,一些高度數(shù)節(jié)點(diǎn)往往基于“優(yōu)先鏈接”特性,存在很大的高節(jié)點(diǎn)鄰居特性,造成了相互之間的初始疾病傳播存在很大的重疊空間,消減了一部分的擴(kuò)散范圍.從多種免疫策略的對(duì)比來(lái)看,面向不同數(shù)據(jù)集本文提出的LAC免疫策略效果顯示最優(yōu),且在兩種初始感染節(jié)點(diǎn)方式上的性能穩(wěn)定,時(shí)間復(fù)雜度可規(guī)約為線性級(jí).

5 結(jié)論

本文從信息傳播模型,提出了基于社區(qū)的局部屬性免疫策略能夠在有效降低疾病的傳播范圍,維持了線性級(jí)的時(shí)間復(fù)雜性;在與最大度免疫、介數(shù)中心性免疫、度折扣免疫等免疫策略相比,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提方法的有效性.下一步的研究是聚焦社交網(wǎng)絡(luò)的動(dòng)態(tài)變化特性,來(lái)加速免疫節(jié)點(diǎn)集的發(fā)現(xiàn)過程.