鮑中奎，張海峰

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

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

鮑中奎，張海峰

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

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

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

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

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

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

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

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

1 二維Kleinberg模型

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

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

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

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

2 疾病傳播模型

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

圖1 在傳播模型示意圖

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

3 仿真及分析

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

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

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

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

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

為了分析出現(xiàn)最優(yōu)半徑的原因，本文分別研究了最終傳播比例R（∞）（如圖3a所示）、治愈比例V（∞）（如圖3b所示）及總代價X（如圖3c所示）與z的關系。從圖3可以發(fā)現(xiàn)，隨著z的增加，最終傳播比例R（∞）快速下降，導致治愈比例V（∞）也相應降低，因此總的代價X達到一個最小值。從圖3a～圖3b可以發(fā)現(xiàn)，隨著進一步增加控制半徑z，傳播比例 R（∞）→ 0，再增加z只會導致更多的人被治愈，即V（∞）增加，最終導致系統(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的關系

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

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

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

進一步研究m=2的情況，即每個節(jié)點有兩條長程邊指向遠處節(jié)點。通過圖5和圖6可以觀察到m=2的定性性質和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的關系

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

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

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

4 結 束 語

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

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

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

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

［1］ 李翔. 復雜動態(tài)網(wǎng)絡傳播動力學［J］. 力學進展， 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］ 汪小帆， 李翔， 陳關榮. 網(wǎng)絡科學導論［M］. 北京： 高等教育出版社， 2012. WANG Xiao-fan， LI Xiang， CHEN Guan-rong. Network science： an introduction［M］. Beijing： Higher Education Press， 2012.

［6］ 榮智海， 唐明， 汪小帆， 等. 復雜網(wǎng)絡2012年盤點［J］. 電子科技大學學報， 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］ 王偉， 楊慧， 龔凱， 等. 復雜網(wǎng)絡上的局域免疫研究［J］.電子科技大學學報， 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

國家自然科學基金（61473001）

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