logo资料库

复杂网络免疫策略分析.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.79M 资料格式：pdf 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    第51卷第3期 2013年5月 吉林大学学报(理学版) Journal of Jilin University(Science Edition) VoI．51 No．3 May 2013 复杂网络免疫策略分析 李向华 ，王欣 ，高 超 (1．西南大学计算机与信息科学学院，重庆400715；2．吉林大学计算机科学与技术学院，长春130012) 摘要：基于网络免疫策略，先从免疫效率、代价和鲁棒性三方面分析各免疫策略在同构网络 中的免疫特性，再构建异构耦合网络模型，并分析了各类免疫策略在异构耦合网络中对病毒 传播的抑制力．实验结果表明，已有免疫策略可有效抑制病毒在同构网络中的传播，但对异 构耦合 络的保护能力有待提高． 关键词：复杂网络；网络免疫；病毒传播；同构网络；耦合网络 中图分类号：TP399 文献标志码：A 文章编号：1671—5489(2013)03—0444—09 Network Immunization Strategies in Complex Networks ‘LI Xiang—hua ，WANG Xin。，GAO Chao (1．College of Computer and Information Science，Southwest University，Chongqing 400715，China； 2．College of Computer Science and Technology，Jilin University，Changchun 130012，China) Abstract：On the basis of comparing the characteristics of different strategies in homogenous networks in terms of et ficiency，cost and robustness，the authors constructed a hybrid interdependent network and analyzed the efficiency of different immunization strategies in such network．The results show that although current immunization strategies can effective restrain virus propagation in homogeneous networks，the efficiency of strategies should be improved in interdependent networks． Key words：complex network；network immunization；virus spreading；homogeneous networks； interdeDendent networks 网络免疫技术通过保护网络中部分节点以切断病毒传播路径的方式保护网络，是复杂网络传播动 力学的主要研究内容，也是抑制病毒传播的有效方法之一l1 ]．高效的免疫策略不仅对计算机网络适 用，对人类社会接触关系网络中的传染病传播和控制也有重要意义_6。]．然而，目前对复杂网络免疫策 略的分析都是基于单一网络结构，即假设网络中的节点服从单一度分布 ]，而异构耦合网络在现实世 界中广泛存在，如电网、交通和通信等系统通常耦合在一起、互相关联，一个系统的波动即会影响另 一个系统的稳定 ]．如疟疾_1。]和H5N1[1 ”]为代表的病毒可同时在动物网络(蚊子、鸟类)和人类接触 网络中传播；同一所学校内不同班级同学之间也拥有显著不同的接触模式口 ．因此，研究这类耦合网 络的抗毁性具有重要意义l9 。 ． 判断一种网络免疫策略是否可在网络中有效执行，通常从两方面评价：1)策略对网络的保护能 收稿日期：2()l2 1l一15． 作者简介：李向华(1979)，女，汉族，博士，副教授，从事复杂网络、数据挖掘和人工免疫系统的研究，E—mail：li_xianghua@ 163．corn．通信作者：高超(198o一)，男，汉族，博士，副教授，从事复杂网络和复杂系统的研究，E—mail：cgao@SWU．edu．cn． 基金项目：匡l家科技支撑计划(批准号：2012BAD35B08)、高等学校博士学科点专项科研基金(批准号：20120182120016)、重庆市 自然科学基金(批准号：cstc2012jiB40012)、吉林省科技发展计划项目(批准号：201105016)和中央高校基本科研业务费专项基金 (批准号：X DlK2012B0l6；XDJK2O12CO18)．
    446 吉林大学学报(理学版) 第51卷 1．2基于网络局部信息的免疫策略 局部免疫策略克服了全局策略需要预先掌握网络拓扑的瓶颈，其中随机免疫策略 忽略网络节 点属性差异，以等概率方式选取一定比，例的节点进行保护．虽然该策略对均匀网络的保护能力较优， 但在无标度网络中，该策略几乎需要免疫所有节点才可能阻止病毒传播Ⅲ，这在现实世界很难实现． 为提高局部免疫效率，利用现实网络中广泛存在的无标度结构特征，研究者们提出了邻居免 疫 和图覆盖免疫 。 策略．邻居免疫策略先从网络中随机选取“种子”节点，再从这些节点周围 随机选择一个或多个直接邻居进行免疫．因为在无标度网络中，度大的节点拥有更多邻居，其被选中 的概率远高于度小的节点，进而能以较低的计算成本取得远好于随机免疫的效果，同时回避了目标免 疫需要掌握全局信息的瓶颈．但这种对所有邻宿不加甄别、随机选取的方式及仅选取直接邻居的方 法，使其效率受到严重制约 ∞]． 基于图覆盖的免疫策略将免疫过程视为一个图覆盖问题，即以“种子”节点为中心，免疫其周围 d步范围内的最大度节点．该方法利用一定局部拓扑知识，取得明显优于邻居免疫的效果．但由于该 策略选择节点行为固定，受网络拓扑，特别是社团结构的影响较大，常陷入局部最优解[26]．虽然该方 法适合于分布式网络，但其计算复杂性随覆盖距离的增加而指数级增大，且在实际应用中，用户很难 获得间接邻居信息．同时，该策略并未考虑任何与应用领域相关的启发信息，也未回答针对不同网络， d值如何选取，因此具有一定的局限性． 为了能仅利用局部信息获得与目标免疫策略近似、甚至更优的免疫效果，文献[27]从计算角度将 网络免疫问题转化成分布式约束优化问题 ，将自组织和正反馈机制融入到分布式约束搜索算法中， 提出一种基于AOC的分布式免疫策略．该策略通过在网络中布置一群具有自治行为的计算体(entity) 实现对一组最大度节点的搜索．与已有方法相比，该方法从群体智能中的激发工作机制人手，通过自 组织计算提高搜索效率，但该策略与全局免疫策略的免疫效率有一定差距． 以图1为例，如果只选择一个免疫节点，随机免疫策略可能选择V 作为免疫节点．如果 被选 为种子节点，则随机邻居免疫策略会从直接邻居 和V 中随机选取一个作为免疫节点．而当覆盖范 围 一3时，图覆盖免疫策略会将到 距离小于等于3的{V ，V ，V。，V ，V ，V ，V。}集合中选取一个 最大度节点作为免疫节点，即 或V。；而基于AOC免疫策略中的entity根据它们之间的自组织交互 及局部正反馈机制最优移动规则，最终选取 为免疫节点． 2 同构网络中免疫策略对比及分析 本文以两个真实邮件网络(美国安然公司和西班牙ROVIRA I VIRGILI大学邮件网络)及GLP算 法[2叼构建的人工网络作为实验用的同构网络，从免疫效率、代价和鲁棒性三方面定量分析不同类型免 疫策略对病毒的抑制能力，所用网络列于表l_对比免疫相同数目节点时，用网络中最终被感染节点 的数目判断哪种策略免疫效率最好；免疫代价不仅比较了各策略的时间复杂度，还分析了免疫临界 值，即选择哪种策略可在免疫最少节点的情况下，将病毒传播率控制在最小范围内；鲁棒性则分析对 比各策略对网络拓扑变化的适应能力． 表1 实验所用同构网络 Table 1 Homogeneous networks used in experiments 网络名称 节点数 边数 幂指数 网络名称 节点数 边数 幂指数 G 1 1 000 4 224 1．70 8．456 G…4 000 16 734 1．77 8．340 G 2 1 000 4 226 2．70 8．452 G 。 1 238 2 1O6 1．30 3．400 G…3 1 000 4 232 。3．70 8．464 Gu…i i 1 133 5 451 1．46 9．620 2．1免疫效率 在交互式邮件传播模型 中，对比分析目前最具代表的网络免疫策略对病毒传播的抑制能力．病 毒传播模型参数设置与文献E3o3相同，传播过程模拟运行600个时间步，初始病毒攻击采用随机攻击 方式感染网络中两个节点．所有数值结果均为运行100次的平均值．从网络中分别选取5 ，1O％和
    第3期 李向华，等：复杂网络免疫策略分析 447 30 的节点进行免疫，观察不同策略对病毒传播的抑制能力，即网络的最终被感染节点数目情况． 表2列出了各类策略在合成网络中的免疫效率，括号内的数字表示不采用策略时网络中被感染的 节点总数．由表2可见，在选取相同数目免疫节点的前提下，掌握了全局拓扑信息的节点介数免疫策 略对病毒传播的抑制能力最强．而在全局信息未知情况下，基于AOC策略的免疫效果最佳．实验结果 也表明控制病毒的传播并非只保护网络中度数大的节点，那些传输能力强的中继节点对病毒的传播也 起至关重要的作用．而基于AOC的免疫策略利用自组织和正反馈机制在局域环境中搜索最大度节点 的同时，间接免疫了那些具有大度数的中继节点，因而取得了比其他基于节点度数免疫策略更好的免 疫效率．人工社团网络(该网络具有4个社区，由100条边将独立的社区连接在一起)的免疫结果与人 工合成网络相似． 表2 人工合成网络中不同免疫策略的免疫效率对比结果 Table 2 Immunization efficiencies of different strategies in synthetic networks 人工合成 、 免疫节点比例／ 人工合成 免疫节点比例／ 网络 5 10 30 网络 界 5 10 30 G l(941) 目标免疫‘ 679 413 7 G 3(956) 目标免疫 827 734 58 节点介数免疫 653 368 3 节点介数免疫833 729 10 边介数免疫 682 398 39 边介数免疫845 741 198 随机免疫879 803 563 随机免疫892 827 604 随机邻居免疫805 673 232 随机邻居免疫875 781 433 图覆盖免疫d一2 663 456 9 图覆盖免疫 一2 855 743 83 图覆盖免疫 ：3 658 43l 7． 图覆盖免疫 =3 846 736 60 基于AOC策略 659 365 4 基于AOC策略826 728 30 G 2(954) 目标免疫813 675 22 G…(3 764) 目标免疫 3 028 2 272 12 节点介数免疫 795 677 5 节点介数免疫 2 986 2 038 4 边介数免疫803 674 177 边介数免疫， 3 056 2 300 386 随机免疫888 812 584 随机免疫 3 532 3 266 2 355 随机邻居免疫840 765 393 随机邻居免疫 3 392 3 017 1 253 图覆盖免疫 一2 820 704 30 图覆盖免疫d一2 3 104 2 345 60 图覆盖免疫 ：3 813 678 19 图覆盖免疫 一3 3 042 2 222 26 基于A0C策略 796 669 9 ‘ 基于AOC策略 2"969 1 976 8 图2对表现较优的4种免疫策略做了进一步分 析．其中，节点介数免疫策略明显优于目标免疫策 t 一2 略，这是因为介数免疫可有效破坏网络拓扑，增加 网络平均路径长度，切断病毒传播路径．由于基于 嚣 Aoc免疫策略选择的节点不仅节点度数大，而且 介数值高，所以其免疫效率又优于只保护了节点介 数大的介数免疫策略． 表3进一步分析了各策略在真实邮件网络中的 免疫效率．图3显示了在安然网络中被感染节点数 目随时间的变化过程(A)及被感染节点数目与免疫 节点间的变化关系(B)．结果表明，在安然网络中，Fig．2 基于AOc策略在免疫网络中10 的节点后，达到 时间步 图2人工社团网络最终感染的节点 数目随时间变化曲线 Final number of infected nodes with time varying in the synthetic community"based network 免疫临界点，即病毒很难在网络中大规模扩散．上述实验结果与人工网络结论相同，即基于节点介数 的免疫策略和基于AOC的免疫策略在免疫效率方面取得了比其他策略更好的效果．由于基于AOC 免疫策略只依靠局部信息即可在网络中部署，故更适合在大规模分布式网络中应用． 文献[17]验证了节点介数免疫策略的免疫效率优于目标免疫策略，这是因为介数免疫策略可有效 破坏原有网络拓扑结构，通过增加网络平均路径长度的方式阻断病毒传播路径．而本文实验表明，基
    448 吉林大学学报(理学版) 第51卷 于AOC的分布式免疫策略的免疫效率在某些情况下甚至优于节点介数免疫策略．这是因为基于AOC 免疫策略选择的免疫节点不仅具有较大的节点度数，同时搜索自治体在网络中按照网络链路的链接关 系进行游走时，会先保护网络中中转能力强的节点，即介数大的节点．所以基于AOC免疫策略选出的免 疫节点不仅具有较大的节点介数值，同时具有较大的节点度数值，因此可更有效地切断病毒传播路径． 表3真实网络中不同免疫策略的免疫效率对比结果 Table 3 Comparison of immunization efficiencies from different immunization strategies in benchmark networks 、 免疫节点比例／ 、 免疫节点比例／ 5 10 3O 。 5 10 30 G (i 037)目标免疫 19 17 14 Gu …(1 078)目标免疫 995 886 250 节点介数免疫 14 lO 7 节点介数免疫 991 862 59 边介数免疫 68 23 8 边介数免疫 1 001 911 492 随机免疫822 784 541 随机免疫 1 029 973 748 随机邻居免疫 187 77 22 随机邻居免疫 1 O12 940 636 图覆盖免疫d一2 64 19 11 图覆盖免疫 一2 998 903 301 图覆盖免疫 一3 2O 14 1O 图覆盖免疫 一3 995 895 267 基于A0C策略 10 4 4 基于A0C策略 972 872 79 时间步 (A)被感染节点随时间变化曲线 免疫节点比例／％ fB)被感染节点与免疫节点关系曲线 图3安然邮件网络的病毒传播示意图 Fig．3 Illustration for viruses propagation in Enron email network 2．2 免疫代价 表4列出了各类策略的计算复杂性分析结果，其中：N表示网络中节点总数； 表示免疫节点数 目；表示网络平均度；志表示策略想要选择的熟人数目；d表示图覆盖免疫策略中想要选择的步 长； 表示基于AOC免疫策略收敛到稳定状态时所需时间步． 表4计算复杂性对比结果 Table 4 Comparison of computational complex of immunization strategies 策略名称 计算复杂性 目标免疫策略 介数免疫策 随机免疫策略 随机邻居免疫策略 图覆盖免疫策略 基 里壅茎 !翌 ：：± ! ____________-___-___●_--__。●_。- -__-____●__________________________________________________________-___-。 。 。’’ ’—’ ’’’—’’—————————一 由表4可见，基于AOC免疫策略的计算复杂性最小，而全局的介数免疫策略和目标免疫策略因 为需要掌握全局拓扑结构才可以实施，因此计算复杂性最大．在现实应用中，免疫某个节点需要一定 成本，为了既能抑制病毒传播，又能降低成本，高效的免疫策略应通过免疫尽量少的节点控制病毒的 感染率．因此衡量免疫代价的另一个指标就是为了达到免疫临界值所需免疫节点比例．为便于阐述， 定义以下变量：pc表示不应用免疫策略时网络的最终感染密度(1Do—N，／N，其中NI表示被感染节点 总数)； 表示应用免疫策略后网络节点最终感染密度；lO表示病毒传播感染率，ID—ps／po．根据 + K × 一 d K )) ( 0 O o O O
    第3期 李向华，等：复杂网络免疫策略分析 449 文献[25]，定义厂 作为免疫临界值，表示为使病毒的传播率p—O时，需要免疫的网络节点比例值厂． 图4对比了采用随机攻击时，两种人工合成网络中．0随免疫节点比例厂的变化过程．实验表明， 节点介数免疫策略能花费最小的厂值有效保护网络；而在分布式策略中，基于AOC的免疫策略免疫 代价最小．以图4(A)为例，当|0—0．1时，节点介数免疫策略需要的免疫临界值厂 小于基于AOC’的 免疫临界值厂 ，而厂。小于目标免疫临界值，。，即f <厂 < ．同时，当网络幂指数变大时，同一种 策略需要的免疫代价也随之增加．以节点介数免疫为例，分别对比图4(A)和图4(B)，为了能使病毒 的传染率控制在0．1以内，在不同幂率网络下需要的免疫临界值分别约为13 和24 ． 图4不同幂率结构人工网络中的免疫代价对比 Fig．4 Comparison of immunization costs in synthetic networks with different powe~law exponents 2．3免疫鲁棒性 ‘ 面对网络结构差异，同一策略在不同网络中会 得到不同的效果，但最佳策略应不受网络拓扑影 响，即策略应具有鲁棒性_2 ．图5为免疫临界值厂 与网络幂指数之间的变化关系．由图5可见，厂 的 变化幅度越小，当网络结构变化时，为抑制病毒传 播所需免疫的节点比例变化越小，策略鲁棒性越 强．实验结果表明，节点介数策略的鲁棒性最好， 但该策略受网络拓扑结构限制，无法应用于大规模 分布式网络中．而在分布式策略中，基于AOC策 略的鲁棒性最好．同时，该策略的搜索性能所展现 的鲁棒性更适用于大规模、分布式的动态网络L2 ． 3异构耦合网络中免疫策略分析 网络幂律指数 图5免疫临界值随网络结构的变化关系 Fig．5 Change of immunization critical value (fc)with the network structure 上述病毒传播模型是以同构网络为研究目标，即假设网络节点度分布服从幂律分布．而现实网络 并非拥有单一网络结构，在一个网络中同时包含多个子网络，每个子网络拥有不同的度分布特征，呈 现出异构特点 ]．本文构造一个异构耦合网络(heterogeneous interdependent net：work)，并在此网 络上分析免疫策略对病毒传播的抑制能力． 异构耦合网络构建过程如下： 1)构建4个具有独立度的分布网络，分别用G ，G。，G。，G 表示，其中：G 和G。由GLP网络产 生器[2朝产生无标度网络，幂指数分别为1．7和2．7；G。是利用WS模型构建的小世界网络；G 是利用 ER模型构建的随机网络．表5列出了4个独立网络的结构属性，图6(A)的度分布清晰展现了4个独 立网络的异质特性． ． 2)在独立网络间随机添加100条边，构建异构耦合网络，如图6(B)所示．如果网络M和N之间 边数用E删表示，则E12—17，E13—14，E14—14，E23—21，E24—19，E34：15．
    450 吉林大学学报(理学版) 第51卷 ． ——-_r (A)4个独立网络和度分布 ．； 空 ] 。 · 一 ’’· l ：、 一 (B)异构网络和度分布 图6异构网络示意图 Fig．6 Illustration for heterogeneous interdependent network 下面仍以交互式邮件传播模型_3。。为基础，分 析异构耦合网络的抗毁性及各类免疫策略对异构耦 合网络的保护能力．本文先从整个网络中随机选取 2个初始感染节点，并根据不同策略要求从网络中 选取不同比例的免疫节点．图7为异构耦合网络中 不同免疫策略的免疫效率对比结果．由图7可见， 在异构网络中，虽然基于AOC免疫策略的效率优 于其他策略，但低于在同构网络中的效率，表明设 计异构耦合网络中的免疫策略是关键． 为进一步分析异构耦合网络的鲁棒性，设定病 毒从不同子网络展开攻击，即分别从不同子网络中 选取2个节点作为初始感染节点．图8为应用目标 免疫节点比例l厂 图7异构耦合网络中不同免疫策略 的免疫效率对比结果 Fig．7 Comparison of immunization efficiencies in the heterogeneous interdependent network 《 她 填 图8从不同子网络展开攻击时的病毒传播曲线 Fig．8 Virus propagation in each subnetwork of a heterogeneous interdependent network 一、
    第3期 李向华，等：复杂网络免疫策略分析 451 免疫后，病毒在不同子网络中的传播趋势．由图8可见，无论从何处展开攻击，G。和G 子网络感染 速度都最快、范围最广．因此，对异构耦合网络中WS和ER子网络的免疫是难点． 综上所述，网络免疫技术是抑制病毒传播的主要方法之一，也是复杂网络传播动力学的主要研究 内容．本文先对网络免疫的基本原理和关键技术进行定性分析，然后在同构网络中定量分析了各策略 的免疫效率、免疫代价和免疫鲁棒性．实验结果表明，免疫策略对同构网络的保护能力与其计算量近 似成反比．如随机免疫策略与其他5种免疫策略相比，计算量最小，但对网络的保护能力最弱；而基 于介数的免疫策略计算量最大，但该策略利用中心控制选择节点(边)介数最大的节点进行免疫，可实 现最好的免疫效率，高效阻断病毒传播路径．本文构建了一种新型异构耦合网络，并分析了免疫策略 对异构耦合网络的保护能力，实验结果表明，已有各类免疫策略对异构耦合网络的保护能力有限，设 计一种适合异构耦合网络的分布式网络免疫策略是一个亟待解决的问题． [1] [2] [3] [4] [5] [6] [7] [8] [9] [1O] [11] [12] [13] [14] [15] [16] [17] [18] 参 考 文 献 Pastor—Satorras R，Vespignani A．Immunization of Complex Networks[J]．Physical Review E，2002，65(3)： 0361O4． cHEN Yi—ping，Paul G，Havlin S，et a1．Finding a Better Immunization StrMegy I-J]．Physical Review Letters， 2008，i01(5)：058701． Hu：Ke，TANG Yi．Immunization for Scale—Free Networks by．Random Walker[J]．Chinese Physics，2006， 15(12)：2782—2787． Cohen R，Havlin"S，Ben-Averaham：D．。Efficient Immunization Strategies for Computer Networks and Populations [刀．Physical Review Letters，2003，91(24)：247901． Echenique P，Gomez-Gardenes J， Moreno Y，et a1．Distanced Covering Problem in Scale—Free Networks with Degree Correlation[J-I．Physical Review E，2005，71(3)：035102． Cornforth D M，Reluga T C，Shim‘E，el a1．Erratic Flu Vaccination Emerges from Short-Sighted Behavior i n Contact Networks[J]．PLoS Computational Biology，2011，7(1)：e1001062． Ames G M，George D B，Hampson C P，et a1．Using Network Properues to Predict Disease Dynamics on。H uman Contact Networks[J]．Proceedings of the Royal Society B，2011，278：3544—3550． GAO Jin—xi，Buldyrev S V，Havlin S，et a1．Robustness of a Network of Networks[J]．Physical Review Letters， 2011，107(19)：195701． Vespignani A．Complex Networks：The Fragility of Interdependency[J]．Nature，2010，464：984—985． Menach A I ，Tatem A J，Cohen J M，el a1．Trave1 Risk，Malaria Importation and Malaria Transmission i‘n Zanzibar l-j]．Science Report，2Oll，1：article number 93． Rivas A L，Fasina F O，Hoogesteyn A L，et a1．Connecting Network：Properties of Rapidly：Disseminating Epizoonotics』-J]．PLoS One，2012，7(6)：e39778． Bont6 B，Mathias J D，Duboz R．Moment Approximation of Infection Dynamics in a Population of Moving Hosts [J]．PLoS One，2012，7(12)：e51760． Stehl~J，Voirin N，Barrat A，et a1．。High—Resolution Measurements of Face—to—Face Contact Patterns in a Primary School[J]．PLoS One，2011，6(8)：e23176． LI Wei，Bashan A，Buldyrev S V，et a1．Cascading Failures in Interdependent Lattice Networks：The Critical Role of the Length of Dependency Links[J]．physical Review Letters，2012，108(22)：228702． Hasegawa T，Konno K，Nemoto：K．Robustness of Correlated Networks against Propagating Attacks I-J]．The European Physical Journal B，2012，85：262． Narasimhamurthy A，Greene D，Hurley N，eT a1．Partitioning Large Networks without Breaking Communities [J]．Knowledge and Information Systems，2010，25(2)：345—369． Holme P，Kim B J，Yoon C N，et a1．Attack Vulnerability of Complex Networks l-J]．Physical Review E，2002， 65(5)：O56109． Carmi S，Havlin S，Kirkpatrick S，et a1．A Model of Internet Topology Using k-Shell Decomposition[J]． Proceedings of the National Academy of Sciences of the United States of America，2007，104(27)：1l15O一11154．
    分享到：
    赞 收藏

    相关推荐

    资料库

    网络技术

    共收录2367份资料，累计7个分类，关注成员有19位，主要包括：综合布线,网管软件,网络监控,网络设备,其它,系统集成,网络基础

    热门标签

    综合布线 网管软件 网络监控 网络设备 其它 系统集成 网络基础

    最新资料