基于有限临时删边的病毒传播控制策略

doi:10.13232/j.cnki.jnju.2019.04.015

基于有限临时删边的病毒传播控制策略

李黎^,, 张瑞芳, 杜娜娜, 柳寰宇

陕西师范大学计算机科学学院，西安，710062

Virus propagation control strategy based on limited temporary links removed

Li Li^,, Zhang Ruifang, Du Nana, Liu Huanyu

School of Computer Science and Technology, Shaanxi Normal University, Xi’an, 710062, China

通讯作者: E⁃mail：lili@snnu.edu.cn

收稿日期: 2019-02-27 网络出版日期: 2019-07-17

基金资助:

陕西师范大学中央高校基本科研业务费. GK201903093

Received: 2019-02-27 Online: 2019-07-17

摘要

复杂网络理论的蓬勃发展为人们研究病毒传播行为和网络结构对病毒传播影响提供了新的思路，网络结构动态演化对病毒传播控制有着重要作用.考虑到有限资源约束，为及时有效地控制病毒传播，提出了一种与初始感染源无关的病毒传播控制策略：有限临时删边（Limited⁃Temporary⁃Links⁃Removed，LTLR）策略.该策略在保证网络系统基本功能不受影响的前提下，通过临时删除或管制网络中病毒传播最短路径上重要的边资源，使得病毒绕道或被阻断，从而有效地延缓病毒的传播速度和控制病毒的传播范围.仿真实验表明，在具有小世界特性的网络中，LTLR策略能显著增加网络平均路径长度、提高病毒传播控制效率，并且该策略消耗少、易于部署，可作为一类通用的优化控制策略推广到舆情网络传播控制、交通网络拥塞治理等领域.

关键词： 网络结构 ; 传播控制 ; 有限资源 ; 临时删边

Abstract

The booming development of complex network theory provides new ideas for people to study the behavior of virus spread and explore the influence of the network structure on the propagation of the virus. The dynamic evolution of network structure plays a critical role in the control of virus propagation. Considering the constraint of limited resources，the paper proposes a virus propagation control strategy，named Limited⁃Temporary⁃Links⁃Removed(LTLR)，to control virus propagation timely and effectively，which is independent of the initial source of infection. By temporarily removing or controlling the important link resources on the shortest path of virus propagation in the network，the LTLR strategy makes the virus go by a roundabout route or be blocked，thereby effectively delay the propagation speed of the virus and control the propagation scale of the virus under the situation that the basic functions of network system is maintained. Simulation experiments show that the LTLR strategy can significantly increase the average path length of the network and improve the control efficiency of virus propagation in a network with small-world characteristics. The strategy is less costly and easy to deploy，besides it can be used as a generic optimization control strategy and be extended to the propagation control in public opinion networks，congestion control in traffic networks，etc.

Keywords： network structure ; propagation control ; limited resources ; temporary links removed

PDF (1465KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

李黎, 张瑞芳, 杜娜娜, 柳寰宇. 基于有限临时删边的病毒传播控制策略. 南京大学学报(自然科学版)[J], 2019, 55(4): 651-659 doi:10.13232/j.cnki.jnju.2019.04.015

Li Li, Zhang Ruifang, Du Nana, Liu Huanyu. Virus propagation control strategy based on limited temporary links removed. Journal of nanjing University(Natural Science)[J], 2019, 55(4): 651-659 doi:10.13232/j.cnki.jnju.2019.04.015

病毒在人群中流行以及在网络上传播都会给社会生活带来巨大的影响，比如H7N9禽流感、非典型肺炎（SARS）、埃博拉等病毒在人群中爆发；比如计算机病毒、网络谣言、舆情等在网络上传播^[1,2,3].而为了对抗病毒的传播和蔓延往往需要花费大量的人力和物力，因此研究病毒的传播机理，进而采取有效措施控制病毒传播具有重要的现实意义，特别是基于有限资源的网络病毒传播控制策略研究具有更大的实用价值.

在实际生活中，每个个体都有趋利避害的行为.当易染人群得知病毒传播的消息后，他们会自适应地采取相应措施避免自身被感染，比如接种疫苗、避免与感染个体接触等，这些行为会使得个体所在网络的结构发生变化^[4].类似的，对于网络中节点而言，它们会通过自适应改变自身的连接情况来避免与感染节点接触.例如，Gross and Blasius^[5]在研究自适应网络的易染⁃感染⁃易染模型和Shaw and Schwartz^[6]在研究自适应网络的易染⁃感染⁃免疫⁃易染模型中，都认为当网络中有感染节点存在时，易染节点都会选择与感染节点断开连接，重新选择一个非邻居的健康节点或免疫节点进行连接，使自身避免被感染从而实现自我保护.

影响病毒传播的因素包括网络结构因素和传播机制因素，本文关注网络结构演化对病毒传播的影响.这里网络结构演化主要是指网络中边的链接关系发生变化，其中，重连策略就是通过断开和重连网络中的边，使网络结构动态调整进而控制病毒传播的典型策略.

Risau⁃Gusman and Zanette^[7]研究了当节点对邻居节点并不具备完全知识的情况下自适应网络中多种重连策略下病毒的传播行为.Shaw and Schwartz^[8]研究得出随机免疫策略在自适应网络中对病毒传播控制的效果比在静态网络中更加有效.上述研究主要是基于平均场理论，然而利用微分方程很难体现网络中节点状态及网络拓扑在每个时刻的演化情况.宋玉蓉等^[9,10]为克服基于平均场理论建立病毒传播模型的不足，提出基于元胞自动机(Cellular Automata，CA)的病毒传播模型，并进一步证实重连策略对病毒传播具有抑制作用.曹玉林等^[11]对宋玉蓉等^[9,10]提出的策略进行了分析，提出基于最短路径和节点度的重连策略.刘振杰等^[12]提出基于度与聚集系数的病毒免疫策略在人工合成网络和真实大学网络中的研究.上述研究表明自适应网络中的重连策略可以有效减缓病毒传播速度，降低病毒感染规模.

然而，现有大多数重连策略没有考虑有限资源的约束，花费代价比较大.如果重连策略假设断边和重连过程中不改变网络中的总边数，那么在有限资源约束下不仅要考虑断边优化，也要考虑重连边的优化问题.为了有效求解此类问题，本文提出一种与初始感染源无关的有限临时删边（Limited⁃Temporary⁃Links⁃Removed，LTLR）策略.

本文工作的主要贡献有：

(1)考虑了有限资源的约束，基于边介数提出了有限临时删边的LTLR策略.该策略不仅在有限删边情况下能保证网络系统基本功能不受影响，而且与一般策略相比，具有实现方便、花费代价小的优势.

(2)LTLR策略是一种与初始感染源无关的病毒传播控制策略，即无论初始感染源是单个还是多个，是集中出现还是分散出现等都对LTLR策略的控制效果不产生影响.

(3)仿真实验结果表明，在具有小世界特性的网络中，本文提出的LTLR策略能显著延缓病毒的传播速度和控制病毒的传播范围.

1 基于元胞自动机的病毒传播模型

元胞自动机(Cellular Automata，CA)是一种能够模拟具有内部相互作用的动力系统^[9].通常一个CA主要由元胞空间C、有限状态集Q、元胞邻域V和元胞状态转换规则函数 $δ$ 这四大元素组成，可以表示为 $C A = (C, Q, V, δ)$ .

本文基于元胞自动机建立易染⁃感染⁃易染(Susceptible⁃Infected⁃Susceptible)的SIS病毒传播模型.该模型中节点的状态有易染(susceptible)即健康状态和感染(infected)状态^[13]两种状态，这两种状态的节点之间相互转换过程如图1所示.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 SIS 状态转换

Fig.1 SIS state transition

一般网络系统可表示为G=(N,E)，其中，N为网络中节点的集合， $n = |N|$ 表示网络中节点个数，E为网络中边的集合， $m = |E|$ 表示网络中边的个数.E中的每条边都有N中的一对节点与之对应，并且这种对应关系包含于网络的邻接矩阵 $A$ 中.网络中的每个节点都看作一个元胞，则n个节点的网络就可看作包含n个元胞的元胞自动机.根据元胞自动机的四要素可建立如下模型^[11,14]：

元胞空间C：初始时刻建立包含有n个元胞的一维元胞空间.

有限状态集Q：在本文所提及的SIS模型中，节点对应元胞的状态分为易染状态和感染状态，并分别用0和1表示，因此可得状态集 $Q = \{0,1\}$ .若令 $S_{i} (t) (S_{i} (t) \in Q)$ 来表示元胞i在t时刻的状态变量，则有：

S_{i} (t) = \{\begin{array}{l} 0, 元 胞 i 在 t 时 刻 为 易 染 状 态 (S) \\ 1, 元 胞 i 在 t 时 刻 为 感 染 状 态 (I) \end{array}

(1)

元胞邻域V：网络邻接矩阵A能反映网络的拓扑结构，这里采用A表示元胞空间中各个元胞邻居之间的关系.因此，t时刻元胞i的邻居就可以表示为 $A (t)$ 中第i行所有取值为1的元素集合，这里用 $a_{i j} = 1 (a_{i j} \in A (t))$ 表示元胞i和元胞j之间存在连接的边，并且 $a_{i i} = a_{j j} = 0$ .

元胞状态转换规则函数 $δ$ ：在每一时刻t，感染节点会以 $β$ 的概率去感染其周围的邻居节点，同时被感染的节点也会以 $α$ 的概率恢复为健康节点.感染节点和健康节点之间的状态转换函数可以表示为：

S_{i} (t + 1) = \{\begin{array}{l} \bar{S_{i} (t)}, g > 0 \\ S_{i} (t), g \leq 0 \end{array}

(2)

其中，上横线表示取反操作，g表示感染节点和易染节点之间的状态转换判断函数，表示如下：

g = \bar{S_{i} (t)} (1 - {(1 - β)}^{m_{i} (t)} - γ) + S_{i} (t) (α - γ)

(3)

其中， $α$ 表示恢复率， $β$ 表示感染率， $γ$ 取(0,1)之间的随机数， $m_{i} (t)$ 表示t时刻节点i的感染邻居的个数：

m_{i} (t) = \overset{N}{\sum_{j = 1}} a_{i j} S_{j} (t)

(4)

设I(t)表示t时刻感染节点所占比例，S(t)表示t时刻健康节点所占比例.显然，在任何时刻以下等式始终满足：

I (t) = \frac{1}{N} \overset{N}{\sum_{i = 1}} S_{i} (t)

(5)

I (t) + S (t) = 1

(6)

因此，根据上述元胞自动机的组成要素，可以基于元胞自动机建立病毒传播的SIS模型.

2 有限临时删边的控制策略

真实世界中，当传染病在人群中扩散时，人们为了避免自身被感染，会选择与已感染的人群暂时不再联系，也就意味着有选择性的暂时的自我隔离.同理，当病毒在网络中蔓延时，网络中的节点也会临时改变自身的连接情况进而避免被感染.

2.1　典型删边策略

在现有病毒传播控制策略研究中，随机(Random)删边策略和基于节点度(Degree)删边策略使用得比较多.下面分析这两种典型删边策略的特点.

(1)随机删边策略：给定网络初始矩阵

A(t)，在网络中完全随机选择一部分边进行删除.

(2)基于节点度删边策略：给定网络初始矩阵A(t)，给每条边赋权 $W_{i j}$ ， $W_{i j}$ 为一条边两端节点i和j度之积，将边权按由大到小排序；然后删除 $W_{i j}$ 最大的那条边（需要注意的是：若 $W_{i j}$ 值最大的边有多条,则随机选择一条边删除）；最后重复上述过程直至删边数目满足条件即可.

随机删边策略虽然实现简单但是对病毒传播控制的效果有限.节点度信息是衡量节点重要性的常用指标，以度为基础的删边策略已有较多研究^{[12,15,16,17]}.然而，度指标只利用了节点自身信息，并没有考虑节点在网络中的位置，也无法刻画节点邻居之间的连接状况.从图论角度看，节点介数/边介数表示网络中所有节点对之间通过该节点/边的最短路径的数目，在最短路径算法中，介数能量化节点/边要处理的信息量，进而介数能更好刻画网络中的负载特征^[15].因此，为了有效地控制病毒传播，本文提出基于边介数删边的有限临时删边LTLR策略.

2.2　LTLR策略

LTLR策略利用边介数特性优化网络结构进而有效控制病毒传播.当选择边介数较大的边进行删除或管制时，意味着暂时切断病毒传播过程中所经过的最短路径，增加了网络的平均路径长度，使病毒在传播过程中绕行其他路径，从而能够更有效地延缓病毒传播，控制病毒传播的范围.具体来看，LTLR策略具有以下特点：

(1)LTLR策略中临时删边是逻辑上的，不等同于物理意义上的删边.在实际网络系统中可能意味着在某个时间段内关闭网络链路或通过软件暂时关闭链路，也可能意味着绕道；在病毒传播的过程中或许意味着临时隔离或其他管制措施^[15].

(2)考虑了有限资源的约束，尽可能删除最少数目的临时边，并且保证网络基本功能不受影响，是LTLR策略遵循的基本原则.在本文中，LTLR策略中临时删边的数目是通过网络中最大连通子图中节点所占比例来确定的.

(3)LTLR策略是一种与初始感染源无关的策略，即无论初始感染源是单个还是多个，是集中出现还是分散出现等都对LTLR策略的控制效果不产生影响.

总的来说，有限临时删边的LTLR策略通过移除最少数目的边资源不仅保证了网络基本功能不受影响，而且对病毒的传播控制起到显著作用，方案容易部署实施，成本开销比较低.

下面对LTLR算法进行具体描述.给定一个含有n个节点m条边的网络G(N,E)，用 $A (t)$ 表示t时刻网络的邻接矩阵.随机选取x%的节点作为初始的感染源.需要说明的是，本文提出LTLR策略与初始感染源无关，是随机选取初始感染节点数目和位置的，具有普适性.

由于网络结构决定网络功能，而网络的基本功能是与网络连通性密切相关的.在临时删边的过程中，为保证网络基本功能不受影响，本文中用网络连通性来反映网络基本功能.在具体实现过程中，利用广度优先搜索（Breadth⁃First⁃Search，BFS）算法统计随着删边数目的增加，网络中最大连通子图规模的变化情况，在满足给定网络连通需求的情况下，进而确定有限临时删边数目k的比例.

对于每个节点 $i \in N$ ，具体步骤如下：

(1)首先利用Girvan and Newman^［18］提出的经典社团结构划分(Girvan⁃Newman，GN)算法得到基于边介数的删边顺序；

(2)然后利用BFS算法确定有限删边数目为k%;

(3)再按照GN算法中所得到的删边顺序，临时删除一条满足条件的边；

(4)重复步骤3直至临时删边比例为k%.

LTLR算法的流程如图2所示.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 LTLR算法流程图

Fig.2 The flowchart of the LTLR algorithm

根据上述处理步骤可看出，LTLR策略实现的复杂度主要取决于GN算法，在大规模网络系统中计算复杂度比较高，但该策略利用中心控制选择边介数最大的边进行删除，有效地延缓了病毒传播速度，缩小了病毒传播规模^[19].

3 仿真结果与分析

为验证LTLR策略的有效性，在给定网络拓扑图和有限删除边约束的情况下，分析比较LTLR策略和典型删边策略对病毒传播控制的性能.本文关注具有小世界特性的网络系统，选取了具有代表性的Zachary空手道俱乐部实际网络和由Watts和Strogatz提出的具有代表性的小世界网络模型为例进行仿真分析.基于SIS传播模型，设置仿真实验中传播参数，恢复率 $α = 0.8$ ，感染率 $β = 0.4$ ，初始感染节点为随机选取总节点数的4%，临时删边数目少于k%（临时删边数目是在保证网络基本功能不受影响的前提下确定的，本文实验中取k=15）.在仿真实验中，每条曲线值都表示运行50个轮次以上的平均值.

3.1　对病毒传播演化的影响分析

Zachary空手道俱乐部网络是一个包含34个节点78条边的“基准”社会网络.图3描述了在删边数目相同的情况下，Zachary网络在不同删边策略作用下网络中感染节点所占比例I(t)的变化趋势.图4描述了在删除相同数目边的情况下，具有200个节点的WS小世界网络在不同删边策略作用下网络中感染节点所占比例I(t)的变化趋势.从图3和图4中数据分析可知：(1)从感染率I(t)的变化趋势可看出，与无删边策略相比，基于随机删边、节点度删边和LTLR策略删边都能控制病毒的传播速度和感染规模，但是其中，LTLR策略的控制效果最为显著；(2)不论是面向Zachary网络（如图3），还是面向WS网络（如图4）都可以看出，LTLR策略能显著地控制病毒的传播速度和感染规模，验证了该策略的可行性和有效性.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 Zachary网络的I(t)变化曲线(全局随机选取

Fig.3 I(t) curves of Zachary network (Globally and randomly select the source of infection)

感染源)

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 WS网络的I(t)变化曲线(全局随机选取感染源)

Fig. 4 I(t) curves of WS network (Globally and randomly select the source of infection)

图3和图4在选取初始感染源时是从全局范围内随机选取的.上述的过程都是在给定网络拓扑的前提下实现的，而当网络拓扑未知时，只能通过从局部范围内随机选取部分节点作为初始感染源，通过这些初始感染源来反映病毒传播的趋势.因此，为了进一步验证LTLR策略与初始感染源位置的无关性，需要再从局部范围内随机选取相同比例的节点作为初始感染源.

图5初始感染源是在局部范围内随机选取，描述了在删边数目相同的情况下，网络在不同删边策略作用下感染节点所占比例I(t)的变化趋势.从图5的数据分析可得到与图3相同的结论，LTLR策略对控制病毒的传播速度和感染规模效果最为显著.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 Zachary网络的I(t)变化曲线(局部随机选取感染源)

Fig.5 I(t) curves of Zachary network (Locally and randomly selected source of infection)

图6初始感染源也是在局部范围内随机选取的，描述了在删边数目相同的情况下，网络在不同删边策略作用下感染节点所占比例I(t)的变化趋势.从图6的数据分析可得到与图4相同的结论，LTLR策略在病毒传播控制过程中有明显的优势.因此，LTLR策略是一种与初始感染源无关的病毒传播控制策略.无论初始感染源是在全局范围内随机选取还是在局部范围内随机选取都对LTLR策略的控制效果不产生影响，验证了LTLR策略与初始感染源位置的无关性.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 WS网络的I(t)变化曲线(局部随机选取感染源)

Fig. 6 I(t) curves of WS network (Locally and randomly selected source of infection)

3.2　对网络结构的影响分析

下面考察删边策略在控制病毒传播过程中对网络结构的影响.本文选择常用的网络结构性质评价指标平均路径长度L，来比较分析网络结构在不同删边控制策略下的性能变化.网络平均路径长度L定义为任意两个节点之间的距离的平均值，即 $L = 1 / (N (N - 1) / 2) ∙ \sum_{i \geq j} d_{i j}$ ，其中N表示网络中节点数目， $d_{i j}$ 表示网络中节点i和节点j之间的最短路径距离.注意到两点之间的最短路径可能不存在，导致整个网络的平均路径长度也为无穷大.为避免在计算中出现这种发散问题，本文中把网络平均路径长度进一步定义为存在连通路径的节点对之间的距离的平均值.

图7描述了随着删边数目的增加，随机删边、基于节点度删边和LTLR三种控制策略对Zachary网络平均路径长度的影响.从图7可以看出，与随机删边和基于节点度删边策略对增加网络平均路径长度所起的作用相比，LTLR策略对增加网络平均路径长度影响最为明显.

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 Zachary网络的L指标分析

Fig.7 L⁃index analysis of Zachary network

图8也描述了随着删边数目的增加，随机删边、节点度删边和LTLR三种控制策略对WS网络平均路径长度的影响.从图8中可以得到与图7相同的结论，LTLR策略随着删除边数目的增加对网络平均路径长度增加有显著影响.网络平均路径长度增加意味着网络传输效率降低，这揭示了LTLR策略能够有效控制病毒传播速度和传播规模的实质.

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 WS网络的L指标分析

Fig.8 L⁃index analysis of WS network

3.3　临时删边资源的优化

通过删边改造网络结构进而控制病毒传播的过程中，如果不考虑删边资源/成本约束，这与现实不符；然而仅通过删除很少数目边使获得较高的病毒控制效果，这也可能事与愿违.如何优选有限删边资源集从而尽可能获得病毒传播控制高性能是本文临时删边资源优化的目标.

从网络图中删除/管制一些边，这通常会影响网络传输和节点间的连接程度，甚至破坏网络的连通性.网络连通性是对网络结构影响的重要因素，所以保持网络的连通性非常重要.经验和实验研究表明，许多实际大规模网络都是不连通的，但是往往会存在一个特别大的连通片，它包含了整个网络中相当比例的节点.本文选择网络结构性质重要指标：最大连通子图规模P，即最大连通片中包含节点数目，作为考察依据来优选临时删边集合.

图9和图10分别描述了Zachary网络和WS网络图中最大连通子图规模随着删除边数目增加的变化情况.图9和图10中数据分析可以看出，当删边数目少于15%时，本文提出的LTLR策略能保证网络的连通性至少达到95%，这样不仅能够很好地抑制病毒的传播速度、降低病毒的传播规模，也能够保证网络的基本功能不受影响.因此，通过网络的连通性来控制临时删边的数目，不仅网络的基本功能不受影响，而且还考虑到了有限资源的约束.

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9 Zachary网络最大连通子图中节点所占比例

Fig.9 The proportion of nodes in the largest connected subgraph of Zachary network

图10

新窗口打开| 下载原图ZIP| 生成PPT

图10 WS网络最大连通子图中节点所占比例

Fig.10 The proportion of nodes in the largest connected subgraph of WS network

4 结论

本文关注网络结构动态演化对病毒传播控制的影响，与现有大多断边重连控制策略鲜有考虑有限资源约束不同，本文提出的LTLR控制策略不仅考虑有限数目边的删除或管制，而且部署实施更方便，成本代价更小.本文基于元胞自动机建立了病毒传播的SIS模型，结合网络结构变化对病毒传播行为的作用，提出了一种与初始感染源无关的病毒传播控制策略：有限临时删边（Limited⁃Temporary⁃Links⁃Removed,LTLR）策略.该策略通过临时删除或管制网络系统中病毒传播最短路径上重要的边，使得病毒绕道或被阻断，不仅能保证网络系统的基本功能不受影响，而且能有效地降低病毒传播速度和感染规模.仿真实验表明在具有小世界特性的网络系统中，与随机删边和基于节点度删边策略相比，本文的LTLR策略能显著延缓病毒的传播速度和控制病毒的传播范围，并且该策略简单有效、成本开销少，可作为一类通用优化控制策略应用于舆情网络、交通网络等领域.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

王亚奇，蒋国平.

复杂网络中考虑不完全免疫的病毒传播研究

物理学报，2010，59(10)：6734-6743.