《复杂网络上疫情与舆情的传播及其基于免疫的控制策略-刘影.pdf》由会员分享，可在线阅读，更多相关《复杂网络上疫情与舆情的传播及其基于免疫的控制策略-刘影.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第13卷第1期 复杂系统与复杂性科学 V0113 No120 1 6年 3 月 COMPLEX SYSTEMS AND COMPLEXITY SCIENCE Mar 20 1 6文章编号：16723813(20l_s)01一007410；DOI：1013306j_16723813201601007复杂网络上疫情与舆情的传播及其基于免疫的控制策略刘 影1，王 伟1，尚明生1，唐 明1(1_电子科技大学互联科学中心，成都611731；2西南石油大学计算机科学学院，成都610500)翰摘要：较为全面的综述复杂网络的免疫问题，包括：真实疫情和舆情传播场景的抽象与建模、疾病传播模型、全局免疫策略和局域免
2、疫策略等。在若干真实网络和模型网络上模拟免疫控制的结果表明，基于中心性、图划分、熟人免疫等策略的免疫效果比随机免疫好，这说明免疫策略的选择对传播控制具有实际指导意义。在选择免疫策略时，应考虑网络的拓扑结构特性和信息的完整程度，才能达到较佳控制效果。关键词：复杂网络；传播动力学；疫情与舆情；网络免疫中图分类号：C93；N93 文献标识码：AControlling Epidemic Outbreaks and Public SentimentSpreading by Vaccination in Complex NetworkLIU Yin91一，WANG Weil，SHANG Mingshen9
3、1，TANG Min91(1Web Sciences Center，University of Electronic Science and Technology of China，Chengdu 611731，China；2Sch001 of Computer Science，Southwest Petroleum UniVersity，Chengdu 610500，China)Abstract：In this paper， an overview of vaccination methods addressing in suppresslng the epldemic spreading
4、is given，focusing on modeling the epidemic and pubhc sentiment spreadingromreal world scenarios，describing models of dynamic spreading，and presentlng Vacclnatlon strategies and theiT efficiency Simulation results on empirical networks and model networks using different vaccination strategies show th
5、at vaccination strategies such as centrantybased Vacclnatlon，graph partitionbased vaccination and acquaintance Vaccination are more eectlVe than randomvaccination This implies that vaccination strategy is lmportant and meanlngtul ln suppresslng epidemic spreading In order to reach a better control r
6、esult，the topological structure and the comDleteness of network information should be taken into account when choosIng a Vacclnatlon strategyKey words：complex network；spreading dynamics；epidemic and public sentiment spreading；network vaccinationO 引言当前，有效应对和处理公共突发事件已经成为维护国家安全和社会稳定的一个重要研究课题和任务。所谓公共突发事
7、件是指突然发生，可能造成重大人员伤亡、财产损失、生态环境破坏和严重的社会危害，危及公共安全的紧急突发事件。疫情是一种典型的突发公共卫生事件，指疾病的发生和快速蔓延，包括人类传染病、动物传染收稿日期：2015一05一07基金项目：国家自然科学基金(1oj025，91324002)；西南石油大学科研启航计划(2014QHz024)作者简介：刘影(1980一)，女，山东烟台人，博士研究生主要研究方向为复杂网络传播动力学。通讯作者：唐明(198l一)四川资阳人博士副教授，主要研究方向为复杂网络传播动力学。万方数据第13卷第1期 刘 影，等：集群运动：复杂网络上疫情与舆情的传播及其基于免疫的控制策略 7
8、5病和植物传染病。例如SARS、禽流感、H1N1流感、埃博拉病毒、熊猫烧香、震荡波等生物和计算机病毒，以社会网络和科技网络作为传播载体，在短时间内造成大范围的感染，具有传播速度快、破坏能力大的特点。随着互联网的广泛应用，计算机病毒传播更是令人关注的一种疫情形式。舆情是“舆论情况”的简称，是指在一定的社会空间内，围绕社会事件的发生、发展和变化，作为主体的民众对作为客体的社会管理者及其政治取向产生和持有的社会政治态度。同时，它也是群众对社会中各种现象、问题所表达的信念、态度、意见和情绪等表现的总和。借助互联网、手机短信、微博等新兴信息交互平台，意见表达和信息传播渠道变得非常广泛。当网络信息不对称，
9、特别是人们对相关信息真伪的辨别能力有限时，信息可能演变成谣言在人群中快速传播u3。如2008年汶川大地震后互联网上流传上游水库遭到污染的谣言使成都发生了疯狂的抢水事件。2011年日本核泄漏事故将导致食盐含有放射物质的谣言引发了抢盐风潮。网络舆情具有自发性、内容海量性、论点多样性、用户分散性等特点。及早发现和报告疫情和舆情，掌握它们在网络中的传播规律并对其进行有效的引导与管控，将大大减少这类突发事件给社会带来的不良影响和损失。网络科学可以描述真实社会中的复杂系统，如人类接触网络、通讯网络、科学家合作网络、朋友关系网络等。网络中的节点代表个体或组织，边代表它们之间的交互关系，不同类型的网络都呈现出
10、复杂的拓扑结构特性3。特别是1998年Watts和Strogatz发现网络具有小世界特性以及1999年Barab丘si和Albert发现网络具有无标度特性，对复杂网络的研究渗透到计算机、生物、管理等多个领域。疫情和舆情以各种网络为载体，以接触(物理接触和信息交流)的形式进行传播和扩散。疫情在人类及动物接触网络中的蔓延、计算机病毒在互联网上的传播、谣言在人群关系中的扩散都是符合某种规律的传播行为一引。在社会交往和信息传递、交流中，网络个体之间通过长期的互动关系已经形成了相对稳定的社会网络，当疫情和舆情在接触网络、信息网络上传播时，受制于网络结构和传播规律从而具有一定的可预测性和可控制性。这为采用
11、复杂网络的传播动力学方法分析传播规律，制定控制策略奠定了基础。复杂网络的传播动力学对传播的动态过程进行描述，建立能反映传播规律的动力学模型。通过对模型的定性分析和定量解析，揭示传播过程中的规律，如疾病爆发阈值、爆发时间、传播持续时间、传播最终的范围等5一。由于疫情和舆情在传播内容、载体、接触模式上存在一定差异，传播机制也存在差异性。但是，网络内在的拓扑结构往往是决定传播范围的关键因素，在采用网络动力学机制研究疫情与舆情的传播控制时，现有方法都是采用传播模型模拟传播过程，在实施免疫策略后评估控制效果。免疫的核心思想是通过免疫目标对象切断其传播的途径，控制传播的扩散。采取免疫措施会产生大量的经济和
12、安全方面的成本，人们总是希望在保持免疫数目较低的同时对传播有明显的抑制或控制效果。最佳的免疫策略应该是用最少的免疫量来最大限度地控制疫情和舆情的传播范围，这对于节约成本、挽救生命、维持社会稳定都具有非常重要的现实意义。l 真实社会中基于网络的传播场景真实社会中存在大量以网络为载体的传播场景，如流行病在人类接触网络中的传播、计算机病毒在电子邮件网络中的传播、谣言在网络论坛上的传播等。有许多工作对真实社会传播场景进行建模和抽象。本节举例介绍了在线社交网络、社会接触网络、科技网络等几类网络上的传播场景。对真实场景的抽象建模是采用免疫理论实施舆情和疫情控制的基础。11 电子邮件网络上的病毒传播人们的电
13、子邮件往来构成了一个体现社会关系的网络。Newman等山-构建了有向的邮件网络。在邮件网络中，每个节点代表一个用户账户。如果用户i出现在歹的邮件列表中，则在节点i和J之间存在一条有向边。用户i出现在歹的列表中，并不意味着用户j出现在用户i的列表中。电子邮件网络呈现出小世界特性，并且具有无标度的度分布。计算机病毒随着邮件的发送传播，其传播过程如下：用户定期的查看电子邮件，当遇到可能带病毒的邮件时，用户若打开病毒邮件，该节点就被感染并向邮件列表中的所有朋友发送病毒邮件。如果用户没有打开病毒邮件，则认为用户识别出病毒邮件并将其删除。7。如果事先告知用户病毒特征，该节点就视作免疫，它不会转发病毒副本。
14、12 网络论坛上的舆情传播网络论坛是民众公开发表个人言论的公共区域，具有言论自由、开放、快速、互动等特点。Cao等8一利用信息提取软件G00Seeker挖掘论坛中某一主题发表评论及回复的原始信息，对数据进行结构化处理，构建舆情传播模型。网民被赋予唯一的ID号，网民之间的回复关系形成有向边，有向边的数目为节点的出度和人度。根据回复次数还可以进一步将网络抽象成权重网络。通过网络拓扑结构寻找关键节点可以帮助定位网络论坛中的意见万方数据复杂系统与复杂性科学 2016年3月领袖，而监控及引导网络舆情中意见领袖的言论，对于舆情的演变和控制有着重要作用。13接触网络上的疫情传播禽流感是一种禽类间通过接触方式
15、传染的动物疾病。Yang等陵根据小世界网络的构建规则，建立了禽流感传播的网络模型。方法是：将发现病毒个体的方圆几十公里设为疫区，每个疫区看作网络中一个节点。考虑到禽流感病毒以接触传染为主，传播倾向于在局部相邻区域中展开，代表疫区的节点与左右相邻的节点相连形成环状的规则网络。病毒的远程传播只有在候鸟迁徙或者长途运输中会产生，这对应于将规则网络中的节点按照一定的概率建立远程连接。类似地分析疫情传播的工作还有模拟甲型H1N1流感的传播、非典的爆发、埃博拉病毒的传播等。14互联网上的级联失效传播因特网是世界上最大的计算机网络?对因特网结构的抽象主要基于路由器级别和自治域级别。前者把每个路由器看作节点，
16、路由器之间的连接看作边。后者将自治系统(Autonomous System，AS)抽象为节点，AS之间的连接看作连边。当互联网上一个或多个节点由于恶意攻击或故障失效时，数据传输改变路径，故障节点的邻居节点由于负载突然变化可能引起级联失效效应，故障像病毒一样传播开。DIMES项目采集了互联网数据，分析发现因特网具有水母状的结构特性1 0I。此外，技术的革新、新产品的推广、新思想的采纳、行为的传播、科学论文的引用等社会现象，都可以抽象为复杂网络上的传播。虽然我们在此关注的是疫情与舆情的传播，但其相关策略可以推广到其它传播场景。2传播模型对免疫策略的研究，常常依赖于传播模型。通过模拟免疫策略实施前后
17、传播影响范围的变化，设计和评估免疫策略。传播模型借助微分方程精确地刻画传播过程中节点状态的变化，能够精确预计传播时间、传播范围、传播阈值等。目前研究最深入、应用最广泛的传播模型是SIS(SusceptibleInfectedSusceptible)和SIR(SusceptibleInfectedRecovered)模型+儿_1 2。在这类传播模型中，个体可处于以下几种状态：易感态(Susceptible，个体当前处于健康状态，但能够被感染)、感染态(Infected，个体已经被感染，具有传染性)、恢复态(Recovered，个体曾经被感染但已获得免疫力，不会传播疾病，也不会再次被感染)。在研究
18、舆情传播时，S态对应未听说过舆情信息的个体；I态对应舆情的传播者，他们已经接触到舆情并积极将舆情传播给邻居；R态对应已知舆情信息但并不传播舆情的人。这两个模型虽然简单，但也存在缺陷，即不能充分刻画传播过程中所有可能存在的状态。许多人类疾病如B型肝炎、艾滋病、登革热，病人都会经过一段潜伏期才会发病。在舆情传播中，某人听到舆情相关信息后，并不立即传播，而是通过一段时间的评估来决定是否接受并传播此信息。考虑到传播的延迟性和病毒的潜伏性，定义了节点的另一种状态暴露态(Exposed，也称作潜伏态)。处于潜伏态的节点以一定概率转化为感染态或健康态。1) SIS模型。初始时，一小部分节点处于感染态I，其余
19、节点处于易感态S。每一个时间步，I态节点接触它的一个随机选择的邻居(单点接触模式)或者全部邻居(全接触模式)，并将S态邻居以概率口变为I态；感染完毕后I态节点以概率p恢复为S态，或者以概率1一p保持I态。网络的有效传播率为A一口卢。传播过程在I态节点数目不变时达到稳定，此时I态节点密度为，。sls模型可模拟流感、肺结核等疾病的传播，患病病人在治愈以后并不能获得免疫力而是再次成为易感人群。受病毒入侵的计算机在清除病毒以后，也可能再次被感染。2) SIR模型。每一个时间步，I态节点接触它的邻居，并将S态邻居以概率口变为I态。I态节点在感染了S态节点之后，以概率9变为R态，或者以概率1一p保持I态。
20、传播过程直到网络中没有I态节点为止，此时R态节点的比例为R。R。越大，说明传播影响力越大。像麻疹、水痘等疾病，病人在治愈后具有了免疫力，不会再次被感染也不会传播疾病，可以用SIR模型来模拟。3) SEIR模型：在SIR模型基础上，节点增加了一个暴露态E。易感节点S在接触I态节点后不是立即转换为I态，而是先经过一段时间的潜伏态E，再以一定概率变为I态或S态。在疫情传播中，感染节点如果自身具有较强的免疫能力，在患病后自行恢复，转变为健康个体。若感染节点自身抵抗力较弱，疾病不但不能被自身消除还会感染他人，这对应于E态节点转变为I态。含有潜伏期的传播模型还有SEIS、SEIRS模型等。在经典传播模型的
21、基础上，国内外学者研究了不同免疫策略下，传播模型的变化。Fu等一31详细介绍了在部分免疫、目标策略、熟人免疫、活跃免疫等多种免疫策略下，SIS模型及其传播阈值的改变。Shi等。1 4提出了不完全免疫的SIS模型，研究在无标度网络上传播阈值和免疫失效率的关系，发现在免疫控制下传播结果不仅与网络万方数据第13卷第1期 刘 影，等：集群运动：复杂网络上疫情与舆情的传播及其基于免疫的控制策略 77结构有关，还与免疫药物的有效期有关。Chen等1在SEIR模型中引入直接免疫率，处于潜伏态的节点以一定概率直接变为免疫个体。此外，引入外部舆论场影响率来研究传播模型的变化。Wang等16j研究了有免疫失败和免
22、疫失效时，病毒在sIR模型上传播行为的变化。Chen等m：考虑舆情传播中话题具有衍生性、复杂性等特点，提出基于话题衍生性的SEIRS舆情传播演化模型，发现了网络舆情演化对传播规律的影响。3复杂网络上的免疫基于病毒传播的机理，人们采用免疫的方法来控制传播。节点一旦被免疫，意味着从网络中删除了与这些节点相连的边，使得病毒传播的途径大大减少。免疫会产生经济方面的问题，比如注射疫苗有经济成本，也有对人体产生副作用的安全成本。当成本和资源有限时，选择最优的免疫策略，用最少的免疫量来最大限度地控制疫情和舆情的爆发，具有立刻可见的实用性和经济性。基于复杂网络的免疫过程可以分为3个阶段：建立网络模型、实施免疫
23、控制、评估免疫效果，如图1所示。根据真实社会场景收集节点和连边信息，建立复杂网络模型，表示成图G一，其中V是节点集合，E是边的集合。根实施免疫控制生物接l 电子自B 即时通 论坛网 在线社钽网络 抖网络 if【网络 络 交网络全局免疫策略_-一蜀域免眨策略基于网络结f!j极大连询佝度量疗法 子圈大小壬于传j蔷睦量方图l基于复杂网络的免疫过程Fig1 Immunization b嬲ed on complex network据免疫策略从V中选出重要节点实施免疫，这些节点不会被感染，并切断了传播的路径。最后采用合适的指标对免疫效果进行评估。在下面的内容中，我们先介绍免疫效果的度量方法，这为后面介绍和
24、理解免疫策略奠定基础。然后全面而详细地介绍当前主要的免疫策略，并对它们的适用场景、优缺点进行分析。31免疫效果的度量方法在大多数免疫相关的研究中，对免疫效果的度量主要采用以下两种方法及其变形，即基于网络结构的度量方法和基于传播范围的度量方法。基于网络结构的度量方法。基于网络结构的免疫效果度量，考察网络极大连通子图的大小如何随着免疫节点从网络中被移除而改变。免疫节点可以看作将节点和它的连边从网络中删除。节点一旦孤立，病毒就无法传播。只有处在极大连通子图中的感染节点，才能继续扩大感染范围。考虑一个无向无权网络，规模为N。被删除节点比例为p(0户1)，剩余节点比例为1一夕。网络在删除免疫节点之后，极
25、大连通子图所包含的节点比例记为S。在一定的户下，S值越小，说明移除节点后剩余网络的极大连通子图规模越小，网络破碎程度越大，免疫策略效果越好。基于传播范围的度量方法。该方法通过在传播模型上模拟病毒传播过程，考察传播进人稳定状态时网络中感染节点的比例。初始时，对目标节点进行免疫，且网络中仅有小比例的节点被感染。被免疫的节点在传播过程中既不会被感染，也不会传播疾病。疾病基于传播模型如sIS，SIR，SEIR进行传播。当传播达到稳态时，考察感染密度J或R随免疫密度户变化的函数。当施加相同的免疫剂量时，I+或R的减小越多，免疫策略越有效。有时人们也会关注免疫临界g，它代表使病毒无法传播时，即传播范围趋于
26、0时需要免疫的节点比例。免疫I临界值越小，免疫策略效果越好。32基于全局信息的免疫策略免疫算法根据其依赖的网络信息完整程度可以分为两类：基于全局信息的免疫和基于局域信息的免疫。基于全局信息的免疫需要知道网络结构的完整信息，即每一个节点全部邻居的数量和对象。基于局域信息的免疫不需要网络完整的结构信息，只需要知道特定节点的局域信息，并以此决定免疫目标。利用网络完整的结构信息识别重要节点，比如求解特征向量中心性需要知道整个网络的邻接矩阵。一旦网络结构确定，依据不同策略选择的目标节点就固定下来，因此也称为确定性免疫策略。万方数据 78 复杂系统与复杂性科学 2016年3月321基于中心性的免疫基于中心
27、性的免疫策略的基本思想是，对节点的重要性进行排序，按照排序从高到低的顺序选择免疫目标。节点的重要性也称为“中心性”，中心性高的节点往往具有更大的传播影响力，如Twitter中少数重要节点的微博能很快传播网络；全球经济网络中核心国家的经济动荡会引发全球经济危机。Kang1胡利用中心性理论识别舆情传播中的关键节点，发现中心关键节点的资源控制能力与信息输入输出效率具有显著的正相关性。Cao等嘲发现在突发事件的舆情传播中，网络论坛中中心性高的节点能影响舆情演变，并发现“网络名人型”和“事件关注型”两类关键节点的演化规律。复杂网络理论中常用的中心性指标有度中心性、介数中心性、接近中心性、特征向量中心性和
28、是一壳中心性。Lu等一19指出，相比于随机免疫，基于中心性识别重要节点并免疫，能有效地影响网络传播的可控性。1)度中心性。节点i的度是指与i直接相连的节点数目。度中心性认为一个节点的邻居数目越多，该节点的影响力越大。度中心性的计算复杂度为0(N)，是最常用、最简单的中心性指标。经典的目标免疫算法就是利用度中心性选择免疫目标。在wS和BA模型网络上的免疫研究发现，无标度网络中免疫阈值的消失是由于度分布的异质性，基于节点度的目标免疫能大大降低网络对传播攻击的脆弱性心0I。2) 介数中心性。Freeman于1977年提出介数中心性，它认为网络中连接所有节点对的最短路径中，经过某个节点的最短路径数目越
29、多，这个节点就越重要。介数中心性刻画了节点对网络中沿最短路径传输的网络流的控制能力。节点i的介数定义为c再)_涵巍等 q)!sttst b 9其中，或为从节点s到f的最短路径中经过i的最短路径数目，踟为节点s到的全部最短路径数目。Holme等卫u研究了基于度和介数中心性的免疫对网络结构的破坏，发现基于介数中心性的策略能更有效地破碎网络。同时，基于动态中心性的免疫比基于静态中心性的免疫效果更好。动态中心性是指节点的中心性在免疫过程中随网络结构的变化而不断更新，静态中心性是指节点的中心性在免疫过程中一直不变，以初始网络结构计算得到的中心性为其中心性。Schneider等221在介数中心性排序的基础
30、上，随机交换节点对的免疫顺序以减小网络极大连通分量大小，在航空网、朋友关系网和因特网上的模拟表明，改进的方法能减少55的免疫数量。介数中心性的计算复杂度较高，为0(N3)。3) 接近中心性。接近中心性认为一个节点到网络中其它节点的平均距离越小，该节点位于网络越中心的位置一2 3|。对于有N个节点的连通网络，节点i的接近中心性被定义为i到其余节点的平均距离的倒数：G一基 接近中心性对类似于星形网络的结构可以准确地发现中心节点，但对于随机规则网络却不适用。当信息或疾病从某节点向网络其余部分传播时，接近中心性高的传播源具有较短的平均传播距离，因而能更快速地传播信息与疾病。该算法的时间复杂度为O(N3
31、)。4)特征向量中心性。特征向量中心性的基本思想是：节点的重要性既取决于它邻居的数目，也取决于它邻居的重要性。如果一个节点的邻居很重要，这个节点的重要性很可能较高；如果邻居的重要性低，既使该节点有很多邻居，它也未必重要。节点i的特征向量中心性定义为一吉，量旷吉孔e， 其中，p为常数，L为节点i的邻居集合，A，为网络邻接矩阵。节点的特征向量中心性就是网络邻接矩阵最大特征值对应的特征向量。从传播的角度看，特征向量中心性适合于描述节点的长期影响力，如在疾病传播、谣言扩散中，特征向量中心性大的节点传播影响范围越大，是需要防范的关键卫。特征向量中心性思想也被推广到有向网络用于识别重要节点，典型的算法有P
32、ageRank，H1Ts等。该算法的时间复杂度为0(N2)。5)是一壳中心性。是一壳中心性通过走一壳分解算法将网络分层，为节点赋予核心性指标志，以区分节点在网络中的位置重要性。是，值越大，表明节点位于网络越核心的位置，与网络其余部分的连接越紧密，传播影响力越大一5【。志一壳算法过程如下：首先从网络中删去度为1的节点及其连边。当全部度为1的节点被删除后，网络中可能会出现新的只有一条边的节点，继续删去这些节点，直到不存在度为1的节点为止。这些被删掉的节点被赋予核心性是，一1。按照类似的方法，剥掉网络中度为2的节点，它们具有核心性是，一2。继续删除更高的壳层，直万方数据第13卷第l期 刘影，等：集群
33、运动：复杂网络上疫情与舆情的传播及其基于免疫的控制策略 79一到网络中每个节点被赋予一个是，值。在医院患者关系网络和演员合作网络上的研究表明，核心性高的节点是最有影响力的传播源zr。在Twitter网络上，核心性高的节点发表的观点更容易被人追捧和扩散比“。是一壳分解算法被推广到带权网络上j，识别全球经济网络中最可能引发经济危机的国家。是一壳中心性具计算复杂度低的优点，为0(N)。是一壳中心性虽然可以用于识别位于网络核心位置的节点，但是在实施免疫时，免疫的对象往往是网络中一定比例的节点而不是单个节点。当按照是，值从高到低的顺序来选取免疫目标时，同时免疫走，值高的节点反而降低了免疫效率。这是因为忌
34、，值高的节点常常相互连接，同时免疫它们使得许多边被重复隔离。Iiu等嵋胡最近的研究发现，是一壳分解方法并非在所有真实网络中都能准确定位网络的动力学核心。在有的真实网络中，由于类核团的存在，是一壳分解方法找到的网络核心节点不是网络最有影响力的传播源。如何利用核心性进行有效免疫值得进一步研究。Iyer等293在真实网络和模型网络上比较了基于不同中心性的免疫效果。在BA模型网络和ER模型网络中，度中心性对网络的破碎程度最大，然后依次是介数中心性、接近中心性和特征向量中心性。度中心性与介数中心性的表现非常接近，这是因为在这两种模型网络中两者的相似性很高。在没有特殊的结构特征时，考虑节点的度是最好的检测
35、重要节点的方法。但是，当网络中有许多小度节点作为桥节点连接不同社区时，介数中心性就是更好的方法。在真实网络中，与在模型网络中结果类似，基于度和介数中心性的目标免疫是分割网络最有效的方法。同时，基于动态中心性的目标免疫方法比对应的基于静态中心性的方法破碎网络效果更好。基于不同中心性的目标免疫的效果明显比随机免疫好，这说明对真实数据的采集、建模和分析对传播控制具有实际意义3。除了E述常用中心性以外，Dufresne等3考虑以节点所属社区数目作为中心性指标来定位免疫目标，发现在特定的有效传播率时，该方法好于或者接近于介数中心性的免疫效果。图2展示了演员合作网上采用基于传播范围的度量方法时，中心性免疫
36、的效果对比。Ln24和Liu323等比较了各种中心性的优缺点及适用环境，指出节点重要性排序不仅与网络结构有关，还受网络传播机制及节点自身属性的影响。在选用中心性方法定位免疫目标时，还需要考虑节点本身的特征及传播机制。322其它免疫策略在目标免疫时，免疫节点由于断开了与其邻居节点的连边，将网络分割成若干个集团。但是这些集团的大小分布很广，有大量规模非常小的集团。免疫策略实际上浪费了许多剂量在分割那些极小规模的集团上。Chen等33提出了一种“相等图划分”(Equal Graph Par一0 00l O 0lFrac“on ofnodcs remove d社区密度口=o50，有效感染率A=5oo。
37、基于社区成员数目的免疫(菱形)效果好于或接近于基于介数中心性(三角)、度(圆圈)、一壳中心性(五角)和随机节点(方形)的免疫。图2 PGP网络上传播范围J。随免疫比例d的变化31Fig-2 ifected popuIati帆JVers璐theimmunization fract伽d in PGP network3l】tition，EGP)的免疫策略。EGP的主要思想是，将网络划分成相互连接的、几乎相同大小的子图(社团)。与目标免疫相比，该算法能够减少约550的免疫剂量。在随机网络、无标度网络、随机规则网络和真实网络上的模拟结果表明，EGP免疫策略通过分割网络来限制疾病传播，比目标免疫策略所需要
38、的免疫剂量更少。图3展示了在4个真实网络中，几个免疫策略的对比。在所有的网络中，EGP算法都表现更好。Huang等口们对复杂网络的节点进行着色，提出了基于着色的免疫策略。根据着色原理，任意两个相邻的顶点被着以不同的颜色。着色完成后，相同颜色的节点形成独立集，独立集内任意两个节点不直接相连。通过从含有节点数目最多的独立集中随机选择节点进行免疫与从整个网络随机选择节点进行免疫相比较，发现基于独立集的随机免疫效果明显好于经典的随机免疫。这是因为独立集节点互不相连，免疫这些节点对网络连通性的破坏更大。基于独立集的免疫策略提供了研究免疫的新思路，即免疫距离较远的节点集合能取得更好的免疫效果。进一步地，Z
39、hao等353研究如何寻找网络上最有效的多点传播源，发现相比于在整个网络中选取中心性排序在前的节点，在独立集中选择中心性高的节点作为多点传播源能最大化传播的广度和加速传播的过程。这一结论启示我们可以通过在独立集中选择中心性高的节点进行免疫。万方数据复杂系统与复杂性科学毒 傺 k i兰Kqc高能粒子学引用网再o2 1相等图划分策略(EGP)；一基于度中心性的目标免疫(HD)；一基于动态度中心性的目标免疫(HDA)图3可被感染的最大连通簇的比例F与免疫比例口的关系333Fig3 The fractim F of the si抚0f the Iarg皓t cluster thal can be in
40、fected versus the fraction of immunized nod姻g当疫情和舆情爆发时，个体会根据自身状况对疾病和信息的传播作出反应。如处在流行病爆发区的人群会倾向于接种疫苗，政府会采取预警和应对措施。Zhang等363基于博弈思想，研究了自我接种机制对疾病传播的影响。由于是否采取免疫行为都有一定的成本，个体会平衡接种和不接种的代价。当接种代价小于被感染的代价时，个体就采取接种行为。研究发现，自愿接种机制下，在无标度网络上能够比在随机网络上更有效地控制疾病的传播。这是由于度大节点被感染的风险更大，因此它们更倾向于采取免疫行为，从而有效控制了疾病的传播。进一步地，Zhang
41、等口7。381研究了政府对免疫行为采取补贴政策时，免疫率的提升。在基于博弈演化理论的自愿接种模型中，个体将最大化其免疫收益。但仅仅是自愿接种并不足以有效控制疾病传播，政府提供的补贴政策会对免疫覆盖产生重要作用。研究发现，对个体免疫成本的部分补贴策略能鼓励更多的人采取免疫行为，而对一部分个体进行完全补贴时，对大度节点补贴比对随机节点补贴能更明显地提升免疫效果。此外，在部分补贴策略下，免疫的覆盖范围单调依赖于个体对免疫代价的敏感度，而在完全免疫策略下，该依赖性并不单调。Ruan等393研究了个体危机意识对免疫策略的影响，提出了信息驱动免疫。通过引入信息产生率和信息敏感率来量化信息驱动的免疫。信息敏
42、感率越高，采取免疫行为的概率越大。模拟结果发现当信息产生率和信息敏感率较大时，疾病的传播明显减小，需要的免疫计量也大大减少。免疫节点的方法虽然有效，但却破坏了网络的连通性，比如在Internet中关闭度大的路由器会影响网络的可达性。Zhang等m3提出基于删边的免疫策略，通过删去连接大度节点的边可以有效控制疾病的传播。Wang等411研究了网络度分布和权重分布对传播阈值和传播范围的影响，发现增加权重分布的异质性能降低疾病传播的范围。在感染概率较低时，增加度分布的异质性能增加传播范围；在感染概率较大时，增加度分布的异质性却能降低传播范围。进而提出一种基于边权的删边策略，通过优先删除边权较大的边，
43、能有效地控制传播，尤其是在权重分布具有较强的异质性和度分布具有同质性的网络上。33基于局域信息的免疫策略全局策略能够较为准确地识别关键节点，免疫效果明显。然而对于大规模网络，我们很难及时获知网络的全部信息，对网络结构的运算复杂度也往往较高，无法确保及时识别出关键节点。局域免疫策略是在对网络全局信息未知的情况下，利用节点周围的局部信息，选取目标控制节点。局域免疫策略只需要少量的局域信息就能快速有效地识别免疫目标，从而控制疾病在整个网络中的传播，因而更具有实际的可操作性。局域免疫策略也称为不确定性免疫策略。331 随机免疫随机免疫附3是完全随机地选取网络中的一部分节点进行免疫，是最简单的免疫方法。
44、随机免疫需要免疫大量人群来阻止接触过程中的疾病传播，许多疾病需要免疫80100的节点，如风疹需要免疫95的人群。对因特网来说，阻止计算机病毒需要几乎100的免疫。随机免疫通常用作检验其它免疫方法效果的基准。332熟人免疫由于随机免疫需要免疫大比例的节点，实施免疫时代价较高，Cohen等43提出了熟人免疫算法。它的算法流程是：随机选择一个节点，然后随机选择它的以个熟人，也就是矾的竹个随机选择的邻居，将选出的熟人进行免疫。下一步继续随机选择被免疫的节点的邻居，直到达到设定的免疫比例。熟人免疫策略可以识别高度连接的个体，特别是在无标度网络中。这是因为大度节点有大量的连接，一个随机节点的邻居是大度节点
45、的概率很大，因此大度节点更容易被选中。万方数据第13卷第1期 刘影，等：集群运动：复杂网络上疫情与舆情的传播及其基于免疫的控制策略 81熟人免疫的一种改进策略是：若随机节点的熟人的度比 x、 。RI)口Rl(该节点的度大，则免疫该节点。如果不存在这样的邻居，就重 “ 一。一 、 -Rncj新选择一个随机节点。该方法的一个变形是，找到随机节点 ，、 。、 ”D1 h的熟人，其连接数目应大于指定的值矗，比如志一5。该策略仅 。1(“) _。 ”_，基于局域信息，却能使免疫效果接近于目标免疫4“。另一个 。 、类似的改进策略由Holme：别提出：选择随机节点度最大的邻 。居进行免疫。为了避免过分免疫
46、同一个邻居集，考虑免疫具 “虬7一。1有最大连出边数的邻居(指连出该随机节点的邻居集)。在多 。，享3ii嗣蔫呷竺等等学守号静个真实网络和模型网络上的模拟结果表明，Holme的改进策 r略在大多数情况下比熟人免疫效果更好。图4展示了arXiV 图4感染节点数目s随免疫比例，的变化m合作网络上，基于SIR传播的几种免疫策略效果的对比。随 Fi24 Number of infected nodes s机免疫(RND)，熟人免疫(RNB)，免疫随机节点度最大的邻 vers吣immunization fraction，居(DEG)，免疫随机节点具有最大连出边数的邻居(OUT)。带C的曲线指的是连锁免疫
47、，即免疫在前一时间步被免疫节点的邻居，而不带C的曲线在每一步都随机选择节点，然后选择该随机节点的邻居实施免疫。可以看出，改进的熟人免疫效果好于经典的熟人免疫，随机免疫效果最差。333具有社区结构的网络上的局域免疫在具有社区结构的网络中，连接不同社区的桥节点及弱连边在病毒的扩散过程中起着非常关键的作用，免疫桥节点能更加有效地控制传染病爆发。SaIath等46一研究了社区结构对传播动力学的影响，提出了一种仅基于网络局域信息的社区桥节点发现策略(CommunityBridgeFinder，CBF)，对发现的桥节点进行免疫。CBF算法采用随机游走识别桥节点，无需知道网络的全局结构，因此也不知道网络的社
48、区结构。它的实现依赖于这一假设：当前随机游走下，第一个与之前访问的节点不相连的节点，很有可能属于另外一个社区。基于CBF的免疫在具有较强社区效应的网络上免疫表现非常好。Gong等n 73对实际网络的社区结构进行深入分析，发现桥节点的弱连接数存在一定的异质性，即桥节点中存在少数更加重要的桥中心节点，它们比其它桥节点具有更多的弱连边。基于自避免随机游走和对比已有朋友圈与当前节点邻域的重叠度，提出桥中心点发现算法(BridgeHub Detector，BHD)。在模型社区网络和真实社区网络上的模拟结果表明针对桥节点及桥中心节点的免疫比熟人免疫和CBF算法的免疫效果都好。Yang等8研究了自适应网络上
49、的传播过程，发现在疾病传播早期，由于断边重连机制的存在，易感节点S与感染节点I发生断边行为，形成较强的社区结构。利用节点局域信息，如节点及其邻居当前的状态和数目，识别S社区与I社区之间的桥节点并实施免疫，能有效延缓传播速度，减小传播范围。此外疾病的控制并非越早越好，而应当在社区效应较强时进行控制。Wang等n91研究了通讯一接触耦合网络上，疾病和消息传播的相互影响对最终传播范围的影响。用SIR模型模拟消息传播，SIRV模型模拟疾病传播，建立通讯一接触耦合网络上的传播模型。基于平均场方法的解析与数值模拟结果表明通讯网络的异质性越强，免疫概率越大，疾病越不容易爆发。4小结与思考如何有效地控制疫情和舆情是网络