二維Kleinberg網(wǎng)絡(luò)上疾病傳播的最優(yōu)局部控制策略

鮑中奎，張海峰

（安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院 合肥 230601）

二維Kleinberg網(wǎng)絡(luò)上疾病傳播的最優(yōu)局部控制策略

鮑中奎，張海峰

（安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院 合肥 230601）

研究二維Kleinberg網(wǎng)絡(luò)上的疾病傳播及最優(yōu)控制問題?；贛anhattan距離提出了一種局部的控制策略抑制疾病在Kleinberg網(wǎng)絡(luò)上的傳播，并進(jìn)一步研究該策略對系統(tǒng)總的代價（定義為最終感染比例和治愈人數(shù)比例之和）的影響。通過研究發(fā)現(xiàn)，當(dāng)Kleinberg網(wǎng)絡(luò)中長程邊數(shù)量和疾病傳播率在一定范圍內(nèi)時，會存在一個最優(yōu)控制半徑，使系統(tǒng)代價最小。當(dāng)控制半徑小于最優(yōu)控制半徑，局部控制策略不能有效地抑制疾病的傳播，導(dǎo)致很多節(jié)點(diǎn)被感染；當(dāng)控制半徑大于最優(yōu)控制半徑，雖然疾病的傳播范圍被有效地控制，但是會花費(fèi)更多的代價用于控制疾病傳播。并且最優(yōu)控制半徑會隨著疾病的傳播率以及刻畫網(wǎng)絡(luò)的參數(shù)改變而發(fā)生變化。

代價函數(shù)； 疾病傳播； Kleinberg網(wǎng)絡(luò)； 局部控制

通信網(wǎng)絡(luò)中的病毒傳播以及社會網(wǎng)絡(luò)中的疾病傳播都可以抽象為復(fù)雜網(wǎng)絡(luò)上的傳播動力學(xué)問題，因此對復(fù)雜網(wǎng)絡(luò)上傳播動力學(xué)行為的研究是復(fù)雜網(wǎng)絡(luò)領(lǐng)域的一個重要命題［1-7］。研究疾病傳播的根本目的是為了有效地預(yù)防、控制疾病的大范圍擴(kuò)散，減小疾病爆發(fā)帶來的危害，因此學(xué)者們提出了多種免疫策略，如目標(biāo)免疫［8］、熟人免疫［9］、基于隨機(jī)游走的免疫策略［10］以及刪邊免疫策略等［11-12］。

已有的免疫策略雖然在某些條件下可以有效地控制疾病在網(wǎng)絡(luò)上的傳播，但是這些免疫策略存在以下共同問題：1） 這些免疫策略是在疾病還沒有發(fā)生之前就實(shí)施，在現(xiàn)實(shí)情況中，很多突如其來的疾病往往缺乏及時、充分有效的疫苗，因此免疫或者治愈措施往往是發(fā)生在疾病爆發(fā)之后；2） 已有的免疫策略多關(guān)注能否最終控制疾病傳播范圍而忽視免疫或控制措施自身帶來的成本代價問題；3） 已有的免疫策略都要求人們掌握網(wǎng)絡(luò)的結(jié)構(gòu)信息，而對于一個充分大的網(wǎng)絡(luò)，要想獲取網(wǎng)絡(luò)的結(jié)構(gòu)信息較為困難。因此需要更為合理的控制策略。

文獻(xiàn)［13］提出了一種局部控制策略（類似于環(huán)狀免疫策略）。在該模型中，假設(shè)感染者分為隱形感染者和顯性感染者，隱性感染者以一定概率變?yōu)轱@性感染者。顯性感染者以一定的概率恢復(fù)為恢復(fù)者，同時顯性感染者也可以以一定的概率被治愈，并且將其周圍一定半徑內(nèi)的所有個體也一并治愈（包含易感染者和感染者）。然后定義系統(tǒng)總的代價為恢復(fù)者和治愈人數(shù)之和，通過研究發(fā)現(xiàn)，對于一維和二維的Newman-Watts小世界網(wǎng)絡(luò)（簡稱NW網(wǎng)絡(luò)［14］），均存在一個最優(yōu)的控制半徑。

NW網(wǎng)絡(luò)雖然可以部分地刻畫現(xiàn)實(shí)網(wǎng)絡(luò)中的小世界性——平均距離小、聚類系數(shù)大的特征［15］，但是對于網(wǎng)絡(luò)上的長程邊是隨機(jī)加上去的，導(dǎo)致網(wǎng)絡(luò)的可搜索性不夠好；且NW網(wǎng)絡(luò)是無向網(wǎng)絡(luò)?；谝陨显颍琄leinberg對二維的NW網(wǎng)絡(luò)進(jìn)行改進(jìn)，提出了經(jīng)典的Kleinberg網(wǎng)絡(luò)模型。通過研究發(fā)現(xiàn)對于二維的Kleinberg網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模趨向無窮大時，存在一個最優(yōu)的參數(shù)α，使網(wǎng)絡(luò)中任意兩點(diǎn)之間的平均傳遞步數(shù)最小［16-17］。

基于以上原因，本文通過研究發(fā)現(xiàn)，當(dāng)m和疾病的傳播率在一定范圍內(nèi)時，二維Kleinberg網(wǎng)絡(luò)上同樣存在一個最優(yōu)的控制半徑，使系統(tǒng)總的代價最??；且該最優(yōu)半徑隨著傳播率的增加而增加，當(dāng)傳播率很大時，這種最優(yōu)現(xiàn)象會消失。尤為重要的是，該最優(yōu)現(xiàn)象隨著α的增加變得更加明顯。

1 二維Kleinberg模型

二維Kleinberg模型是對二維NW進(jìn)行改進(jìn)，具體如下［5，15-16］：

1） 從規(guī)則網(wǎng)絡(luò)開始，首先構(gòu)造一個具有周期邊界條件的二維方格，每個節(jié)點(diǎn)和最近鄰的4個鄰居互為鄰居，即假設(shè)每個節(jié)點(diǎn)和周邊4個鄰居的連邊是雙向邊。

2） 偏好性加長程邊，為了保證網(wǎng)絡(luò)的小世界特性和可搜索性，定義每個節(jié)點(diǎn)都有m條“有向”的長程邊指向網(wǎng)絡(luò)中其他的m個節(jié)點(diǎn)（保證不重連）。不同于NW網(wǎng)絡(luò)中的隨機(jī)加邊，要求每個節(jié)點(diǎn)i指向其他節(jié)點(diǎn)j的概率與這兩個節(jié)點(diǎn)的Manhattan距離有關(guān)，具體定義如下［5］：

文獻(xiàn)［15］指出當(dāng)N→∞時，α=2是唯一的最優(yōu)值，此時分散式算法所需的平均傳遞步數(shù)至多是log（N） 的多項(xiàng)式函數(shù)，即對于規(guī)模很大的網(wǎng)絡(luò)，平均而言每個個體可以經(jīng)過很短的步數(shù)，找到網(wǎng)絡(luò)中需要搜索的目標(biāo)節(jié)點(diǎn)。

2 疾病傳播模型

在疾病傳播部分，本文采用了改進(jìn)的SIR模型［13］。它將包括幾種狀態(tài)：隱形感染狀態(tài)（I）、顯性感染狀態(tài)（D）、恢復(fù)狀態(tài)（R）、治愈狀態(tài)（V）、易感狀態(tài)（S）。隱形感染狀態(tài)與顯性感染狀態(tài)的區(qū)別是后者可以被識別，且有可能激發(fā)局部控制策略，而前者因其隱形特征卻不能被識別。疾病傳播開始階段，模型中隨機(jī)初始化5個節(jié)點(diǎn)為I態(tài)，其他節(jié)點(diǎn)都為S態(tài)。一個S狀態(tài)節(jié)點(diǎn)可以被其鄰居中的I或D狀態(tài)節(jié)點(diǎn)以概率p感染，成功感染后成為I狀態(tài)。當(dāng)一個I節(jié)點(diǎn)被診斷后，I狀態(tài)節(jié)點(diǎn)以概率q成為D狀態(tài)。一個D狀態(tài)節(jié)點(diǎn)或以概率r恢復(fù)成R狀態(tài)或以概率v引發(fā)局部控制策略。局部控制的范圍是與此D狀態(tài)節(jié)點(diǎn)的Manhattan距離小于或等于z的節(jié)點(diǎn)（S態(tài)節(jié)點(diǎn)或者I態(tài)節(jié)點(diǎn)）。既沒變成R狀態(tài)也沒變成V狀態(tài)的節(jié)點(diǎn)在下一步有可能恢復(fù)，也有可能再去感染其他節(jié)點(diǎn)。模型流程如圖1所示［13］。

圖1 在傳播模型示意圖

整個傳播過程直到隱形感染狀態(tài)與顯性感染狀態(tài)節(jié)點(diǎn)個數(shù)之和為零，即I（t）+D（t）=0時停止。

3 仿真及分析

本文在N=50×50的二維Kleinberg網(wǎng)絡(luò)上進(jìn)行了疾病傳播過程，同時考慮了每個節(jié)點(diǎn)長程邊數(shù)目m=1和m=2的情況。

首先引入一個代價函數(shù)X =V （∞） + R（∞），用來衡量疾病爆發(fā)所付出的代價。X表示在整個疾病傳播過程中，最終導(dǎo)致染病個體（ R（∞） ）比例與治愈個體（V（∞） ）比例（治愈的代價）之和。

隨機(jī)加有向長程邊如圖2a所示，更傾向連接距離近的節(jié)點(diǎn)如圖2b～圖2c所示。從圖2可以發(fā)現(xiàn)，對于m=1和不同的傳播率p，無論α=0或者α＞0，當(dāng)z值小時，代價X偏高，而隨著z到達(dá)最優(yōu)控制半徑z=zc，最優(yōu)半徑 隨著傳播率p的增加而增加。這

是因?yàn)殡S著傳播p進(jìn)一步增加，疾病更容易在網(wǎng)絡(luò)上傳播，此時需要控制更大范圍的節(jié)點(diǎn)才能抑制疾病爆發(fā)。若進(jìn)一步增加p會導(dǎo)致疾病在整個網(wǎng)絡(luò)爆發(fā)，此時要么大范圍控制疾病傳播，即增加控制半徑z；要么完全不控制，這兩種情形都會導(dǎo)致系統(tǒng)總的代價趨于1，因此最優(yōu)半徑現(xiàn)象會逐漸消失。

通過比較圖2a～圖2d可以發(fā)現(xiàn)，隨著α的增加，最優(yōu)現(xiàn)象變得更加明顯，即X剛開始隨著z的增加下降更快，然后又隨著z的增加上升更快。這種現(xiàn)象的原因在于：當(dāng)α＞0時，長程邊更傾向指向離自己近的節(jié)點(diǎn)，因此網(wǎng)絡(luò)局域化效應(yīng)更明顯。在此情況下，一方面疾病不容易傳播，另一方面，局部控制策略可以更有效地阻止疾病通過長程邊向遠(yuǎn)處擴(kuò)散。參數(shù)為m=1，q=0.5，r=0.1，v=0.1。

為了分析出現(xiàn)最優(yōu)半徑的原因，本文分別研究了最終傳播比例R（∞）（如圖3a所示）、治愈比例V（∞）（如圖3b所示）及總代價X（如圖3c所示）與z的關(guān)系。從圖3可以發(fā)現(xiàn)，隨著z的增加，最終傳播比例R（∞）快速下降，導(dǎo)致治愈比例V（∞）也相應(yīng)降低，因此總的代價X達(dá)到一個最小值。從圖3a～圖3b可以發(fā)現(xiàn)，隨著進(jìn)一步增加控制半徑z，傳播比例 R（∞）→ 0，再增加z只會導(dǎo)致更多的人被治愈，即V（∞）增加，最終導(dǎo)致系統(tǒng)總的代價X增加。參數(shù)為m=1，q=0.5，p=0.08，r=0.1，v=0.1。

圖2 在不同參數(shù)α以及傳播率p的情況下，總的代價X（X=R（∞）+V（∞）與局部控制半徑z的關(guān)系

圖3 對于不同參數(shù)α，控制半徑z對最終傳播比例、治愈比例以及總的代價的影響

圖4所示為代價函數(shù)X與控制半徑z以及參數(shù)α的關(guān)系，參數(shù)為m=1，q=0.5，r=0.1，v=0.1。由圖可以發(fā)現(xiàn)，隨著α的增加，最優(yōu)現(xiàn)象更加明顯，同時總的代價函數(shù)X也變得越來越小。隨著α的增加，個體更傾向指向距離近的鄰居，使網(wǎng)絡(luò)的局域化現(xiàn)象更加明顯，導(dǎo)致一方面疾病不容易傳播，另一方面局域控制策略更有效地控制疾病向遠(yuǎn)處傳播。

圖4 在p=0.1的情形下，總的代價X與參數(shù)α及局部控制半徑z的關(guān)系

進(jìn)一步研究m=2的情況，即每個節(jié)點(diǎn)有兩條長程邊指向遠(yuǎn)處節(jié)點(diǎn)。通過圖5和圖6可以觀察到m=2的定性性質(zhì)和m=1的完全一樣。在圖5中，參數(shù)m=1，q=0.5，r=0.1，v=0.1。在圖6中，參數(shù)為m=2，q=0.5，r=0.1，v=0.1。

圖5 在不同參數(shù)α以及傳播率p的情況下，總的代價X（X=R（∞）+V（∞）與局部控制半徑z的關(guān)系

圖6 在p=0.1的情形下，總的代價X與參數(shù)α及局部控制半徑z的關(guān)系

圖7進(jìn)一步比較了m=1、m=2與m=3的情況，參數(shù)為q=0.5，p=0.08，r=0.1，v=0.1。通過比較可發(fā)現(xiàn)，隨著m的增加，即長程邊數(shù)量的增加，疾病更容易擴(kuò)散（相同的傳播率p），因此總的代價函數(shù)X也相應(yīng)增加，即需要更多的成本區(qū)控制疾病的傳播，這是因?yàn)殚L程邊的增加導(dǎo)致疾病更容易傳播。隨著m的增加，最優(yōu)現(xiàn)象也變得不太明顯，尤其對完全隨機(jī)（α = 0 ）及m=3、p=0.1的情況（如圖7a中三角形曲線所示），此時最優(yōu)現(xiàn)象已經(jīng)基本消失。

圖7 比較長程邊數(shù)對代價指標(biāo)X的影響

4 結(jié) 束 語

對復(fù)雜網(wǎng)絡(luò)上疾病傳播問題的研究方興未艾［18-20］，而如何有效地控制網(wǎng)絡(luò)上疾病傳播是其中的一個重要課題。已有的研究雖然提出了很多控制策略，但是這些控制策略要么缺乏對控制成本代價的考慮，要么需要充分了解網(wǎng)絡(luò)的結(jié)構(gòu)信息?；谝陨显颍疚脑诙S的Kleinberg網(wǎng)絡(luò)上研究一種局部控制策略，通過定義系統(tǒng)總的代價為治愈比例和最終感染比例之和，刻畫了控制半徑z和總代價X之間的函數(shù)關(guān)系。

1） 在二維的Kleinberg網(wǎng)絡(luò)上，當(dāng)傳播率和長程邊數(shù)量在一定范圍內(nèi)，存在一個最優(yōu)的控制半徑zc使總的代價X最小。當(dāng)控制半徑z過小時，疾病會大范圍爆發(fā)；當(dāng)控制半徑過大時，雖然疾病被控制，但治愈的成本也會大幅度增加。因而存在最優(yōu)的控制半徑使總的代價最低。2） 最優(yōu)現(xiàn)象隨著參數(shù)α的增加變得更為明顯，且總的代價也會相應(yīng)降低。3）最優(yōu)半徑隨著傳播率的增加而增加，如果進(jìn)一步增加傳播率會導(dǎo)致最優(yōu)控制半徑消失。4） 增加網(wǎng)絡(luò)中的長程邊連接會導(dǎo)致傳播范圍上升，且最優(yōu)現(xiàn)象逐漸削弱。

考慮到網(wǎng)絡(luò)結(jié)構(gòu)、傳播動力學(xué)、控制成本以及個體自身行為等多種因素的影響，如何最有效地控制疾病傳播是值得深入探討的問題［21-22］，本文將做進(jìn)一步的探討。

本文的研究工作得到安徽大學(xué)博士基金（01001951）和青年骨干教師培養(yǎng)基金（01005102）的資助，在此表示感謝。

［1］ 李翔. 復(fù)雜動態(tài)網(wǎng)絡(luò)傳播動力學(xué)［J］. 力學(xué)進(jìn)展， 2008，38（6）： 723-732. LI Xiang. Spreading dynamics on complex dynamical network［J］. Advance in Mechanics， 2008， 38（6）： 723-732.

［2］ NEWMAN M E J. Networks： an introduction［M］. New York， USA： Oxford University Press， 2010.

［3］ FU Xin-chu， SMALL M， CHEN Guan-rong. Propagation dynamics on complex networks： models， methods and stability analysis［M］. New York， USA： Wiley Press， 2014.

［4］ ZHOU Tao， FU Zhong-qian， WANG Bing-hong. Epidemic dynamics on complex networks［J］. Progress in Natural Science， 2006， 16（5）： 452-457.

［5］ 汪小帆， 李翔， 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論［M］. 北京： 高等教育出版社， 2012. WANG Xiao-fan， LI Xiang， CHEN Guan-rong. Network science： an introduction［M］. Beijing： Higher Education Press， 2012.

［6］ 榮智海， 唐明， 汪小帆， 等. 復(fù)雜網(wǎng)絡(luò)2012年盤點(diǎn)［J］. 電子科技大學(xué)學(xué)報， 2012， 41（6）： 801-806. RONG Zhi-hai， TANG Ming， WANG Xiao-fan， et al. Review of complex network researches in 2012［J］. Journal of University of Electronic Science and Technology of China， 2012， 41（6）： 801-806.

［7］ WANG Lin， LI Xiang. Spatial epidemiology of networked metapopulation： an overview［J］. Chin Sci Bull， 2014， 59（28）：3511-3522.

［8］ PASTOR-SATORRAS R， VESPIGNANI A. Immunization of complex networks［J］. Phys Rev E， 2002， 65： 036104.

［9］ COHEN R， HAVLIN S， BEN-AVRAHAM D. Efficient immunization strategies for computer networks and populations［J］. Phys Rev Lett， 2003， 91： 247901.

［10］ GONG Kai， TANG Ming， HUI P M， et al. An efficient immunization strategy for community networks［J］. PLOS ONE， 2013， 8（12）： e89066.

［11］ ZHANG Hai-feng， LI Ke-zan， FU Xin-chu， et al. An efficient control strategy of epidemic spreading on scale-free networks［J］. Chin Phys Lett， 2009， 26（6）：068901.

［12］ MüLLER J， SCH?NFISHCH B， KIRKILIONIS M. Ring vaccination［J］. J Math Biol， 2000， 41（2）： 143-171.

［13］ DYBIEC B， KLECZKOWSK A， GILLIGAN C A. Controlling disease spread on networks with incomplete knowledge［J］. Phys Rev E， 2004， 70： 066145.

［14］ NEWMAN M E J， WATTS D J. Renormalization group analysis of the small-world network model［J］. Phy Lett A，1999， 263（4）： 341-346.

［15］ KLEINBERG J. Navigation in a small world［J］. Nature，2000， 406（6798）： 845.

［16］ KLEINBERG J. The small-world phenomenon： an algorithmic perspective［C］//Proc of 32nd Annual ACM Symposium on Theory of Computing. New York， USA：ACM Press， 2000.

［17］ WATTA D J， STROGATZ S H. Collective dynamics of‘small-world' networks［J］. Nature， 1998（393）： 440-442.

［18］ SUN Ye， LIU Chuang， ZHANG Chu-xu， et al. Epidemic spreading on weighted complex networks［J］. Phys Lett A，2014， 378（7）： 635-640.

［19］ ZHANG Zi-ke， ZHANG Chu-xu， HAN Xiao-pu， et al. Emergence of blind areas in information spreading［J］. PLoS ONE， 2014， 9（4）： e95785.

［20］ 王偉， 楊慧， 龔凱， 等. 復(fù)雜網(wǎng)絡(luò)上的局域免疫研究［J］.電子科技大學(xué)學(xué)報， 2013， 42（6）： 817-830. WANG Wei， YANG Hui， GONG Kai， et al. Local immunization algorithm on complex networks［J］. Journal of University of Electronic Science and Technology of China， 2013， 42（6）： 817-830.

［21］ BULDYREV S V， PARSHANI R， PAUL G， et al. Catastrophic cascade of failures in interdependent networks［J］. Nature， 2010， 464： 1025-1028.

［22］ FUNK S， SALATHé M， JANSEN V A A. Modeling the influence of human behavior on the spread of infectious diseases： a review［J］. R Soc Interface， 2010， 7（50）：1257-1274.

編 輯 黃 莘

OEpptiidmeaml iLc oinca Tl wCoo-nDtr imole Sntsriaotneagly K foleri nthbee rSgp Nreeatdwionrgk osf

BAO Zhong-kui and ZHANG Hai-feng
（School of Mathematical Science， Anhui University Hefei 230601）

In this paper we study the spreading of epidemic and its optimal control strategy in two-dimensional Kleinberg networks. We propose a local control strategy based on the Manhattan distance to inhibit the spreading of epidemic in Kleinberg networks， and then study the effect of this strategy on the cost function of total system （defined as the sum of the density of infection and the density of cured individuals）. We find that， when the number of long-distance edges and the transmission rate are in a certain range， there will be an optimal control radius that makes the cost function of total system be minimum. When the control radius is smaller than the optimal radius， the epidemic cannot be effectively controlled， leading to the outbreak of epidemic. However， when the control radius is larger than the optimal radius， the cost of controlling is very high though the epidemic can be controlled. Meanwhile， we also show that the optimal control radius is influenced by the transmission rate and the parameter depicting the Kleinberg network.

cost function； epidemic spreading； Kleinberg networks； local control strategy

TN92； O41

A

10.3969/j.issn.1001-0548.2016.02.028

2014 - 09 - 22；

2015 - 09 - 13

國家自然科學(xué)基金（61473001）

鮑中奎（1982 - ），男，博士，主要從事信息處理、信息傳播動力學(xué)等方面的研究.