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

2020-12-15王建辉

广西民族大学学报(自然科学版) 2020年3期

王建辉,蒋勇

(1.长沙南方职业学院民航学院,湖南长沙410208;2.湖南大学信息科学与工程学院,湖南长沙410208;3.湖南化工职业技术学院自动化与信息工程学院,湖南株洲412000)

1 前言

1.1 疾病传播免疫的研究

从历史上的西班牙大流感,到2003年的SARS病毒,H5N1禽流感,2009年的甲型H1N1流感,2013年的H7N9的禽流感病毒,2014年的西非埃博拉病毒等疫情均让世界闻之色变,各国政府高度重视、积极措施布置防控.早期的疾病传播研究最为广泛的是以传染病模型为主,该模型把人群分为三种状态:易感态S,感染态I和免疫态R.

1.2 复杂网络研究的兴起

疾病传播给人类带来了巨大灾难,为了抑制疾病的传播,人们提出了不同类型的免疫策略,并逐渐思考如何站在系统的角度来控制疾病的传播.随着复杂系统、复杂网络研究的兴起,人们聚焦于在复杂网络平台上,开展疾病模型的实验分析与探索.

复杂网络可以通过抽象成图的方式来描述其网络结构,最早的图表示方法是由欧拉对著名七桥问题的研究开始.在20世纪60年代,Erdos和Renyi建立的随机图理论系统研究了复杂网络.Watts和Strogatz在Nature[1]揭示了复杂网络的小世界特性,Barabasi和Albert在Science[2]揭示了复杂网络的无标度特征.这些复杂网络的基础研究对实现疾病传播的模拟分析,以及面向拓扑免疫策略研究,在免疫效果的深化研究上,提供了良好的数学理论与统计分析的基础.例如刘影等[3]考虑结构拓扑,张乐延等[4]提出节点活跃度计算,陈端兵等[5]基于SIR的模拟测试,柳彤[6]提出面向交互频次策略,聂力[7]提出局部中心性策略,方宝平[8]挖掘的临近节点等.

1.3 面向社交网络的研究

疾病传播的主体是社会关系的行动者,通过接触、交互来传播.社交网络主要关注的是行动者之间的交互与联系,这种交互与联系级联地影响到其他行动者的社会行为.围绕社交网络如何构建传播模型、如何设计免疫策略、如何搭建评价标准等问题,专家展开了相关研究.Parish等人使用“社交网络”概念分析挪威渔村的社会结构,姚双龙[9]提出通过控制叠加子网络中的重复节点来抑制疫情的传播蔓延,宋会敏[10]提出在社区间通过免疫桥节点来控制信息传播,王龙鲸[11]提出了一种基于节点强度的网络模型,通过SIS模型仿真验证了高连接节点的免疫策略.

2 面向疾病传播免疫策略的相关研究

目前对疾病传播免疫的研究聚焦于两个方面,一个是传播模型的探讨,即深化探索疾病的传播机理研究;另一个是免疫策略的选择,如何以最小的成本对某些节点进行定向免疫,大大降低疾病传播的途径,进而控制疫情的爆发.

2.1 传播模型的研究

当前的疾病传播模型主要围绕传染病模型和信息传播模型展开研究.

(1)传染病模型的相关研究.复杂网络的疾病传播研究是从传播动力学展开研究的,早期疾病传播研究最为广泛的是以传染病模型为主,其中SI、SIR与SIS三种经典病毒传播模型的研究最广.基于以上基本的疾病传播模型,存在一些改进的模型,本文不再深入探讨.

(2)信息传播模型的相关研究.在拓扑结构的分析中,研究者发现网络中的一些关键节点在传播过程中发挥更大的作用.一些研究者从信息传播模型的角度出发,针对这些关键节点进行目标性的免疫,能够有效抑制流行病的传播和爆发.Domingos等[12-13]提出社交网络中的个人网络价值概念,Kempe等、[14]Chen等[15]讨论研究了两类影响力传播模型,即独立级联模型[16]和线性阈值模型,它们是目前研究最为广泛的两个模型.同时也存在一些其他的传播模型,例如Even-Dar等人[17]提出的概率投票模型,以及Rodriguez等人[18]提出时变因素的传播模型等.

(3)传播模型小结.从传染病模型到信息传播模型,更加注重了社会行动者的交互行为分析,深化了传播机理的探索;随着社交网络的兴起,个体之间的拓扑关系在传播过程中发挥了重要作用.

2.2 免疫机制研究

围绕传染病模型或信息传播模型,人们在疾病传播的免疫策略上展开了一系列的理论分析与实证探索,并形成了很多重要的研究成果,常见的包括:随机免疫、目标免疫、熟人免疫等,以及多种改进型的免疫策略例如接触免疫、环状免疫等.

总体而言,以上免疫策略总体可分为两类,[3]一类是面向全局属性进行免疫,该方法需要预先掌握网络上的所有信息,涉及节点、链接以及主题等相关信息;另一类是面向局部属性进行免疫,该方法需要了解某些局部区域的节点相关信息.因此,如何利用网络的局部信息进行免疫,降低时间复杂性、提高免疫效果,设计出高效的免疫策略成为研究的重点.

(1)面向全局属性的免疫.全局属性需要统筹网络拓扑的全局属性,虽然可以准确地识别关键节点,免疫效果最优.但是全局属性信息的计算难度很大,难以快速实现.当前全局属性的计算主要有以下方法:介数中心性,接近中心性,[19]特征向量中心性,k-壳中心性.[20]

(2)面向局部属性的免疫.局部属性免疫是利用已知的局部属性信息,进而选择目标展开快速免疫抑制疾病传播,更具有实际的可操作性.主要包括:度中心性,随机免疫,目标免疫,熟人免疫等,以及一些研究者从社区研究的角度出发提出的区域免疫,通过社区桥节点开展免疫研究,[21-24]取得了一定进展.

(3)免疫机制小结.免疫策略是通过对目标节点进行定向免疫,以便阻断进一步的传播路径、抑制疾病的传播扩散.当前研究的重点在如何选取最少的免疫节点,进而实现最大化的抑制疾病传播.当前从全局属性到局部属性的免疫策略,不断地降低了时间复杂性,但是当前的局部信息仍需要进一步的集成计算节点属性或者拓扑属性,对于时效性敏感的免疫策略而言,还存在较大的提升空间.

3 基于局部属性计算的免疫机制研究

3.1 问题定义

基于目前的研究,我们考虑疾病传播中的目标免疫机制,实验方法以蒙特卡洛模拟为基准进行测试.问题定义为:面对初始化节点集为d的疾病传播,如何快速选择或者部署规模为k的免疫节点集,使得最大化的抑制疾病传播(或最终疾病传播的范围最少)?

3.2 主要思想

本文提出基于社区定位的局部属性免疫策略,期望提升免疫效果,降低时间复杂性.首先,采用标签传播的方式进行社区划分,对初始疾病节点的传播网络进行社区级的粗粒度定位;其次,立足每个疾病节点所在的社区内,按照比例轮循选择社区内具有高链接、高中心性的节点,实现局部区域内免疫的候选集快速发现;最后,基于信息传播模型在社交网络上展开蒙特卡洛模拟,对疾病传播下的免疫策略效果进行量化计算与对比评估.

3.3 变量定义

本文所使用的变量定义如表1所示.

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

3.4 计算过程

3.4.1 初始疾病传播节点设置

在疾病传播节点的初始设置上,选择两种方式,一种是基于随机节点集的疾病传播,另一种是基于最大度节点集的疾病传播,对比两种疾病传播模式情况,不同免疫策略对其产生的抑制效果.(为了便于实验的统一计算,在疾病传播节点的定位上,按照社区分别选取,避免疾病扩散可能出现的交叉重叠,以便测试在尽量促使初始疾病节点扩散的基础上,开展不同类型免疫策略的对比分析.)

3.4.2 免疫传播节点集的选择

本文提出基于社区的局部属性免疫算法(Local Attribute based on Community,简称LAC算法),主要有两个步骤,具体如算法1所示.

(1)基于标签的社区划分.

从社区的角度来选择节点,需要在社交网络上划分有意义的社区结构.但是传统的面向图划分、聚类等方法不适于直接社区划分,因为它需要预先知道社区的全局属性.本文采用基于标签传播的方法进行快速的社区划分.[25]

(2)区域性中心节点选择.

在社区中选取高链接、高中心性的节点,我们认为在社区内,节点自身属性以及邻居节点属性都兼顾的节点具有较好的免疫效果.因此通过对疾病传播节点的社区定位,对位于局部社区内的进行二重属性的高链接节点快速计算;然后,按照社区容量的比例轮循添加,形成候选节点集;最后计算排序选择免疫节点集.

3.4.3 免疫效果模拟评估

(1)信息模型构建.

算法需要在信息传播模型的一种(本文选取独立级联模型)进行验证,在每条边(u,v)上随机选择概率,分别调节着影响级别的强弱.

(2)蒙特卡洛模拟.

影响力范围:为了更好估算这些免疫策略下的抑制效果,我们分别在独立级联模型上通过蒙特卡洛模拟来进行量化计算(Monte Carlo Simulation,简称MCS),具体如算法2所示.

(3)算法执行步骤.

算法1 LAC算法执行过程如下所示:

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

虽然多数学者原则上支持会聚研究和组织结构创新，但在涉及本人或部门利益时往往退缩。因此，探索有效的机构组织形式，在兼顾现有组织文化的同时创建以科学或社会挑战为核心的新型研究组织方式，制定合理的会聚项目评审标准、任务分配制度和绩效考核指标，以促进不同学科背景的科研人员间高效的合作伙伴关系，是科研机构亟待解决的问题。

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算法具体执行过程如下所示:

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:主要进行面向区域定位的免疫节点发现.第2步是进行面向标签传播的社区划分,时间复杂性为O(E);第3～6步是对疾病传播节点进行社区定位,时间复杂性为O(d);第7～14步是在每个社区中轮循选择区域中心节点,时间复杂性为O(dh);第15～17步是在候选集中按照排序选择k个免疫节点,时间复杂性为O(k).此时,总体复杂性=O(E)+O(d)+O(dh)+O(k)=O(E).

算法2:主要为免疫策略提供蒙特卡洛模拟评估.第2步是筛选节点集开展循环,第4～6步是开展R次蒙特卡洛模拟计算,第7步是求取平均值.此时,总体复杂性=O(d ER).

4 实验分析

4.1 实验设置

(1)实验环境.

处理器:Intel的双核CPU,2.60 GHz主频;内存:16 G;操作系统:Windows 7 64位.

(2)实验数据.

实验数据来自Arxiv的学术论文的合作数据集,为了进行基准对比,对网络规模进行了统一,将3个数据集的节点规模限制为2000.其中,Gr Qc:广义相对论领域,边数目是3963;Dblp:计算机领域,边数目是4035;Phy:物理学领域,边数目是6660.

(3)初始设置.

初始传染节点种子集个数:5.

初始传染节点生成方式:随机生成方法和最大度生成方法.

免疫种子集个数:100.

蒙特卡洛模拟次数:2000.

(4)对比方法.

随机点免疫:本文使用Random来代替,试验中简写为RanIM.

最大度免疫:本文使用MaxDegree来代替,试验中简写为MdIM.

度折扣方法免疫:本文使用DDiscount Heuristic来代替,试验中简写为DdIM.

介数中心性免疫:本文使用Betweeness来代替,试验中简写为BetIM.

社区中心性免疫:本文使用LAC来代替(本文算法1),试验中简写为LacIM.

熟人免疫:基于初始感染节点和免疫节点的不同数量,考虑到初始感染节点的分布性,无法在同一标准下选择该策略下的免疫节点,因此本文忽略此对比方法.

贪心算法免疫:贪心算法在传染病抑制上可以获得全局的最优解,但是每次迭代需要在全网计算比较一次最优解,其时间复杂性较高(k·N·E·R),因此本文忽略此对比方法.

图1 疾病随机传播下的免疫策略对比(Gr Qc)Fig.1 Comparison of immunization strategies under random disease spread(Gr Qc)

图2 疾病随机传播下的免疫策略对比(dblp)Fig.2 Comparison of immunization strategies under random disease spread(dblp)

图3 疾病随机传播下的免疫策略对比(phy)Fig.3 Comparison of immunization strategies under random disease spread(phy)

图4 疾病最大度传播下的免疫策略对比(Gr Qc)Fig.4 Comparison of immunization strategies under the maximum spread of disease(Gr Qc)

图5 疾病最大度传播下的免疫策略对比(dblp)Fig.5 Comparison of immunization strategies under the maximum spread of disease(dblp)

图6 疾病最大度传播下的免疫策略对比(phy)Fig.6 Comparison of immunization strategies under the maximum spread of disease(phy)

4.2 结果分析

4.2.1 时间复杂性评价

随机节点免疫的时间复杂性是常数项,可忽略;最大度免疫(MdIM)的时间复杂性为O(N),度折扣方法免疫(DdIM)时间复杂性为O(k·log(N)+E),介数中心性免疫(BetIM)最大时间复杂性为O(N3),最小时间复杂性为O(N*E),本文所提出的社区中心性免疫(LacIM)的时间复杂性为O(E).

4.2.2 抑制传播范围评价

分别从随机和最大度的方法生成初始感染节点,分别对免疫策略进行对比分析.

(1)基于随机方法生成初始感染节点.

从整体上而言,本文提出的LAC免疫策略在降低疾病传播上效果最优.如图1、图2和图3所示.基于Gr Qc、dblp、phy数据集上,LAC免疫策略在免疫节点集达到98、80、60个的时候,开始与其他的策略拉开距离,并随后逐渐体现出了较好的免疫效果.对于介数中心性免疫策略,在Gr Qc数据集上的效果较好(如图1所示),在dblp数据上效果居中,在phy数据集上效果最差,说明该策略受网络拓扑结构的影响不稳定.而最大度免疫、度折扣免疫等策略,在不同数据集上效果不一;3个数据集属于无标度网络,在均匀网络上性能较优的随机免疫策略,在该数据集上的效果最差.

(2)基于最大度策略生成初始感染节点.

从整体上而言,与随机感染方式类似,本文提出的LAC免疫策略在降低疾病传播上效果最优.如图4、图5和图6所示,基于Gr Qc、dblp、phy数据集上,LAC免疫策略在免疫节点集达到98、78、80个的时候,开始与其他的策略拉开距离,并随后逐渐体现出了较好的免疫效果.与随机感染方式类似,对于介数中心性免疫策略,在Gr Qc数据集上的效果较好(如图4所示),其余2个数据集效果不佳,说明该策略受网络拓扑结构的影响较大.而最大度策略、度折扣策略等免疫效果,在3个数据上效果居中;基于相同的原因,随机免疫策略的效果最差.

小结:从两种初始感染节点的传播范围来看,随机节点集的初始疾病传播范围要大于最大度节点集的初始疾病传播范围,主要是社交网络具有的无尺度特性,一些高度数节点往往基于“优先链接”特性,存在很大的高节点邻居特性,造成了相互之间的初始疾病传播存在很大的重叠空间,消减了一部分的扩散范围.从多种免疫策略的对比来看,面向不同数据集本文提出的LAC免疫策略效果显示最优,且在两种初始感染节点方式上的性能稳定,时间复杂度可规约为线性级.