-
通信网络中的病毒传播以及社会网络中的疾病传播都可以抽象为复杂网络上的传播动力学问题,因此对复杂网络上传播动力学行为的研究是复杂网络领域的一个重要命题[1-7]。研究疾病传播的根本目的是为了有效地预防、控制疾病的大范围扩散,减小疾病爆发带来的危害,因此学者们提出了多种免疫策略,如目标免疫[8]、熟人免疫[9]、基于随机游走的免疫策略[10]以及删边免疫策略等[11, 12]。
已有的免疫策略虽然在某些条件下可以有效地控制疾病在网络上的传播,但是这些免疫策略存在以下共同问题:1) 这些免疫策略是在疾病还没有发生之前就实施,在现实情况中,很多突如其来的疾病往往缺乏及时、充分有效的疫苗,因此免疫或者治愈措施往往是发生在疾病爆发之后;2) 已有的免疫策略多关注能否最终控制疾病传播范围而忽视免疫或控制措施自身带来的成本代价问题;3) 已有的免疫策略都要求人们掌握网络的结构信息,而对于一个充分大的网络,要想获取网络的结构信息较为困难。因此需要更为合理的控制策略。
文献[13]提出了一种局部控制策略(类似于环状免疫策略)。在该模型中,假设感染者分为隐形感染者和显性感染者,隐性感染者以一定概率变为显性感染者。显性感染者以一定的概率恢复为恢复者,同时显性感染者也可以以一定的概率被治愈,并且将其周围一定半径内的所有个体也一并治愈(包含易感染者和感染者)。然后定义系统总的代价为恢复者和治愈人数之和,通过研究发现,对于一维和二维的Newman-Watts小世界网络(简称NW网络[14]),均存在一个最优的控制半径。
NW网络虽然可以部分地刻画现实网络中的小世界性——平均距离小、聚类系数大的特征[15],但是对于网络上的长程边是随机加上去的,导致网络的可搜索性不够好;且NW网络是无向网络。基于以上原因,Kleinberg对二维的NW网络进行改进,提出了经典的Kleinberg网络模型。通过研究发现对于二维的Kleinberg网络,当网络规模趋向无穷大时,存在一个最优的参数α,使网络中任意两点之间的平均传递步数最小[16-17]。
基于以上原因,本文通过研究发现,当m和疾病的传播率在一定范围内时,二维Kleinberg网络上同样存在一个最优的控制半径,使系统总的代价最小;且该最优半径随着传播率的增加而增加,当传播率很大时,这种最优现象会消失。尤为重要的是,该最优现象随着α的增加变得更加明显。
-
二维Kleinberg模型是对二维NW进行改进,具体如下[5, 15-16]:
1) 从规则网络开始,首先构造一个具有周期边界条件的二维方格,每个节点和最近邻的4个邻居互为邻居,即假设每个节点和周边4个邻居的连边是双向边。
2) 偏好性加长程边,为了保证网络的小世界特性和可搜索性,定义每个节点都有m条“有向”的长程边指向网络中其他的m个节点(保证不重连)。不同于NW网络中的随机加边,要求每个节点i指向其他节点j的概率与这两个节点的Manhattan距离有关,具体定义如下[5]:
$${\Pi _{i \to j}} = \frac{{{{({d_{ij}})}^{ - \alpha }}}}{{\sum\limits_j {{{({d_{ij}})}^{ - \alpha }}} }}$$ 式中, ${d_{ij}} = \left| {{x_i} - {x_j}} \right| + \left| {{y_i} - {y_j}} \right|$ 表示i节点与j节点的Manhattan距离,节点i和j的坐标分别为Xi和yi;(Xi,yi);α=0是刻画偏好性程度参数,表示随机加长程边,α>0表示节点更倾向连接距离自己近的节点作为邻居。
文献[15]指出当N→∞时,α=2是唯一的最优值,此时分散式算法所需的平均传递步数至多是logN的多项式函数,即对于规模很大的网络,平均而言每个个体可以经过很短的步数,找到网络中需要搜索的目标节点。
Optimal Local Control Strategy for the Spreading of Epidemic in Two-Dimensional Kleinberg Networks
-
摘要: 研究二维Kleinberg网络上的疾病传播及最优控制问题。基于Manhattan距离提出了一种局部的控制策略抑制疾病在Kleinberg网络上的传播,并进一步研究该策略对系统总的代价(定义为最终感染比例和治愈人数比例之和)的影响。通过研究发现,当Kleinberg网络中长程边数量和疾病传播率在一定范围内时,会存在一个最优控制半径,使系统代价最小。当控制半径小于最优控制半径,局部控制策略不能有效地抑制疾病的传播,导致很多节点被感染;当控制半径大于最优控制半径,虽然疾病的传播范围被有效地控制,但是会花费更多的代价用于控制疾病传播。并且最优控制半径会随着疾病的传播率以及刻画网络的参数改变而发生变化。
-
关键词:
- 代价函数 /
- 疾病传播 /
- Kleinberg网络 /
- 局部控制
Abstract: 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.-
Key words:
- cost function /
- epidemic spreading /
- Kleinberg networks /
- local control strategy
-
[1] 李翔. 复杂动态网络传播动力学[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] 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京:高等教育出版社, 2012. WANG Xiao-fan, LI Xiang, CHEN Guan-rong. Network science:an introduction[M]. Beijing:Higher Education Press, 2012. [6] 荣智海, 唐明, 汪小帆, 等. 复杂网络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] 王伟, 杨慧, 龚凯, 等. 复杂网络上的局域免疫研究[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.