（控制理论与控制工程专业论文）多局域世界网络中的病毒传播及其控制策略.pdf

| ； j 南京邮电大学 硕士学位论文摘要 学科、专业：工学控制理论与控制工程 研究方向：复盘丕统曼匦终撞剑 作 者：盟级研究生叶东海 指导教师：蒋国平 题目：多局域世界网络中的病毒传播及其控制策略 英文题目：v i r u ss p r e a d i n ga n dc o n t r o ls t r a t e g yi nm u l t i l o c a l - w o r l d n e t w o r k s 主题词：多局域世界元胞自动机病毒传播控制策略复杂网络 k e y w o r d s ：m u l t il o c a l - w o r l d ，c e l l u l a ra u t o m a t a ，v i r u ss p r e a d i n g ，c o n t r o l s t r a t e g y ，c o m p l e xn e t w o r k s 南京邮电大学硕士研究生学位论文 摘要 摘要 生物病毒在人群和牲畜群的流行，计算机病毒在i n t e r a c t 上的肆虐，都给人类社会造 成了巨大的损失。认识病毒在网络中传播现象，研究它的传播特性及其控制策略，对于社 会的发展和人类的进步有着重要的现实意义。 论文简要介绍了现有的针对复杂网络的不同拓扑特性的研究成果，系统地综述了局域 世界网络中的病毒传播及其控制策略。在把握现有研究成果的基础上，本文引入了多局域 世界演化模型，并结合元胞自动机理论，从传播临界值、攻击模式以及病毒传播模型三个 方面考察了多局域世界网络中的病毒传播特性，最后对多局域世界网络中的控制策略进行 了研究。 论文的主要贡献以及研究成果如下： 1 论文引进多局域世界演化模型，并针对它的不足，提出两点改进，使得网络模型的 演化能够更加准确地反映现实复杂网络的拓扑结构特性。且多局域世界演化模型是一个动 态的网络模型，改变了以往的研究都是基于静态的网络模型的状况。 2 论文以元胞自动机为分析工具，很好地反映了病毒传播过程中的概率事件和个体间 的交互行为，弥补了平均场理论的不足。 3 论文针对多局域世界网络的具体特性，提出一种新的基于局域世界间连接矩阵的控 制策略。数值仿真表明，这种新的控制策略能够在较小的免疫代价下，取得良好的免疫效 果。 关键词：多局域世界；元胞自动机；病毒传播；控制策略；复杂网络 南京邮电大学硕士研究生学位论文 a b s t r a c t t h ep r e v a l e n c eo fb i o l o g i c a lv i r u s e sa n dc o m p u t e rv i r u s e sc a u s e sh l l g el o s s e st oh u m a n s o c i e t y u n d e r s t a n d i n gt h ep h e n o m e n o no fv i r u ss p r e a d i n gi nt h en e t w o r ka n ds t u d y i n gt h e p r o p a g a t i o nc h a r a c t e r i s t i c sa n di t sc o n t r o ls t r a t e g i e s ，h a v ei m p o r t a n tp r a c t i c a ls i g n i f i c a n c ef o r s o c i a ld e v e l o p m e n ta n dh u m a np r o g r e s s t h i sd i s s e r t a t i o ns u r v e y sc u r r e n tr e s e a r c hr e s u l t s0 1 1d i f f e r e n tt o p o l o g i c a lc h a r a c t e r i s t i c so f c o m p l e xn e t w o r k s ，i n c l u d i n gv i r u ss p r e a d i n ga n di t sc o n t r o ls t r a t e g i e si nl o c a l - w o r l dn e t w o r k s b yu n d e r s t a n d i n gt h ec u r r e n tr e l a t e dr e s e a r c hw o r k s ，m u l t il o c a l - w o r l de v o l v i n gm o d e li s i n t r o d u c e dt ot h er e s e a r c h c o m b i n e dc e l l u l a ra u t o m a t at h e o r y , t h ec h a r a c t e r i s t i c so fv i r u s s p r e a d i n gi nm u l t il o c a l w o r l di ss t u d i e di nt h r e ea s p e c t s ：t h r e s h o l do fs p r e a d i n g ，a t t a c kp a t t e r n a n dt h em o d e lo fv i r u ss p r e a d i n g t h ec o n t r o ls t r a t e g i e so fm u l t il o c a l w o r l dn e t w o r k sa r ea l s o s t u d i e d t h em a i nc o n t r i b u t i o no ft h i sd i s s e r t a t i o ni ss u m m a r i z e da sf o l l o w s ： 1 m u l t il o c a l w o r l de v o l v i n gm o d e li s i m p r o v e dt ob ea b l et o r e f l e c tt h et o p o l o g i c a l c h a r a c t e r i s t i c so fr e a l - - l i f ec o m p l e xn e t w o r k sm o r ea c c u r a t e l y a n dm u l t il o c a l - - w o r l de v o l v i n g m o d e li sa d y n a m i c a lm o d e l ，w h i l et h ep r e v i o u ss t u d i e sa r eb a s e do ns t a t i cm o d e l 2 t h ec e l l u l a ra u t o m a t am o d e li si n t r o d u c e d i tc a nw e l lr e f l e c tt h ee v e n t sw i t hp r o b a b i l i t y a n di n t e r a c t i o n sb e t w e e ni n d i v i d u a l si n t h e t r a n s m i s s i o n , w h i c h c a no v e r c o m et h e d i s a d v a n t a g ei nt h em e a n - f i e l dt h e o r y 3 i nv i e wo ft h es p e c i a lc h a r a c t e r i s t i c so fm u l t il o c a l w o r l d ，an e wc o n t r o ls t r a t e g yb a s e d o ni n t e r - l o c a l w o r l dc o n n e c t i v i t y - m a t r i xi sp r o p o s e d n u m e r i c a ls i m u l a t i o ns h o w st h a tt h i s n e wc o n t r o ls t r a t e g yc a ng e tg o o di m m u n ee f f e c tw i t hl o w e ri m m u n i z a t i o nc o s t k e yw o r d s ：m u l t il o c a l - w o r l d ；c e l l u l a ra u t o m a t o n ；v i r u ss p r e a d i n g ；c o n t r o ls t r a t e g y ； ；j点 南京邮电大学硕士研究生学位论文 目录 目录 摘要。i a b s t r a c t 目录 第一章绪论 1 1 引言l 1 2 研究的背景与现状2 1 3 研究内容与章节安排4 第二章局域世界网络中的病毒传播控制5 2 1 局域世界演化模型5 2 2 局域世界网络中的病毒传播6 2 2 1 初始感染节点对病毒传播的影响7 2 2 2 局域世界网络的传播临界值8 2 3 局域世界网络中的控制策略1 0 2 4 本章小结1 2 第三章多局域世界网络中的病毒传播1 3 3 1 多局域世界演化模型1 3 3 1 1 多局域世界演化模型基本算法1 3 3 1 2 多局域世界演化模型的度分布分析1 4 3 1 3 改进的多局域世界演化算法1 6 3 2 多局域世界网络中的病毒传播17 3 2 1 元胞自动机模型1 7 3 2 2 基于多局域世界演化模型的元胞自动机传播模型1 7 3 3 仿真与分析1 9 3 4 本章小结2 5 第四章多局域世界网络中的控制策略 2 6 4 1 基于随机免疫的控制策略一2 6 4 2 基于目标免疫的控制策略2 8 4 3 基于局域世界间连接矩阵的控制策略3 0 4 4 本章小结3 4 第五章总结与展望3 5 5 1 本文工作总结3 5 j 南京邮电大学硕士研究生学位论文 目录 5 2 展望3 6 致谢 图表索引 参考文献。 作者在学期间取得的学术成果 3 7 3 8 3 9 ， j 南京邮电大学硕士研究生学位论文第一章绪论 1 1 引言 第一章绪论 无论是在自然界还是在人类社会中，病毒传播都是一种极其普遍而又十分重要的现 象，且与人们的日常生活息息相关。历史上，骇人听闻的黑死病、天花、霍乱等传染病曾 夺走了无数人的生命，给人类造成了不可估量的损失；现代社会中，艾滋病、s a r s 、禽 流感等传染病仍在危害人类社会，给社会的发展和人类的进步造成了巨大的影响。甚至可 以毫不夸张地说，人类社会的发展历程，就是一部与各种病毒传播进行斗争的历程。2 0 0 9 年3 月在墨西哥爆发的甲型h 1 n 1 流感病毒，在短短的几个月时间内迅速蔓延到全球范围， 引起了巨大的恐慌。虽然经过世界各国人民，特别是广大科技和医务工作者的努力，甲型 h 1 n 1 流感病毒疫情得到了较好的控制，但它所带来的影响仍值得我们进一步思考。 生物病毒的传播只是众多传播现象中最常见的一种。进入2 1 世纪，科学技术的发展给 人们的生活带来了极大的便利，i n t e r n e t 将世界愈来愈紧密地连接在一起，人与人的距离骤 然缩短，偌大的地球已经成为了一个“地球村”。在将世界各地紧密连接在一起的同时， i n t e m e t 也给计算机病毒的传播和爆发提供了孕育的温床，使其能轻松地跨越国界，侵入到 世界的每个角落。现在的计算机病毒，尤其是一些蠕虫病毒，它们借助于e m a i l 系统，几 乎能以不可思议的速度在i n t e m e t 上传播。以情书病毒“il o v ey o u ”为例，2 0 0 0 年5 月4 日 凌晨，情书病毒从地球一端的菲律宾开始发作，到感染了地球另一端的美国的数十万台计 算机，只花了不到半天的时间。这种蠕虫病毒传播迅速之快、波及面之广，或许是连它的 编制者都未曾想到的。2 0 0 7 年疯狂肆虐网络的“熊猫烧香”病毒，在几天时间内就感染了 高达几百万的个人和企业计算机，严重威胁了社会生活的正常运作，造成了巨大的损失。 曾有网络安全专家大胆预测：在不采取任何应对措施的情况下，3 0 秒内蠕虫病毒可以让整 个i n t e m e t 瘫痪。这决不是危言耸听，计算机病毒己经成为i n t e r n e t 网络安全的巨大威胁。 尽管在生物病毒和计算机病毒的传播过程中，传播主体和传播内容是各不相同的。在 生物病毒的传播过程中，传播主体是人或动物，传播内容是疾病；在计算机病毒的传播过 程中，传播主体是计算机，传播内容是恶意代码。但通过对这两种传播现象进行分析可发 现，在本质上它们存在以下两个共同点： 1 传播主体由单个个体所组成，它是病毒传播的物质基础。例如，在甲型h 1 n 1 流感 病毒的传播过程中，传播主体( 人) 由单个个体所组成；在熊猫烧香病毒的传播过程中，传 】 属 南京邮电大学硕士研究生学位论文 第一章绪论 播主体( 计算机) 也由单个个体所组成。如果不存在这些单个个体，则无论是生物病毒还是 计算机病毒，都没有存在的物质载体，传播现象自然也就无法进行。 2 传播主体之间的接触或交流，是传播内容( 如生物病毒、计算机病毒等) 从一个个体 传播到另一个个体上的必要途径。例如，与感染了甲型h 1 n 1 流感病毒的病人有了较近距 离的接触，一个健康的人才会感染甲型h 1 n i 流感病毒；计算机病毒的传播也是依靠计算 机之间的网络连接才能进行。如果传播主体是孤立的，它与外界没有任何接触或者交流， 则传播主体是不会感染病毒的。 传播主体为传播内容提供了物质载体，传播内容借助传播主体之间的接触或交流完成 各种传播活动。传播主体与传播主体之间是典型的多对多关系，而图正是描述这种关系的 有力工具。从图论的角度出发，可以将传播主体抽象成网络中的节点，传播主体之间的接 触或交流抽象成网络中的边。通过这种抽象，就可以将对现实网络中的病毒传播的研究， 转换为对由节点和边所组成的网络上的传播行为的研究。 认识病毒在网络中传播现象，研究它的传播特性，尤其是研究防治有害传播的控制策 略，对于社会的发展和人类的进步有着重要的现实意义。 1 2 研究的背景与现状 科学技术的进步已经驱动人类社会进入了信息时代，作为这个时代最鲜明的标志之 一，网络已经成为了现代人生活和工作当中不可或缺的组成部分。电子邮件、在线办公、 网络会议、网络购物等，传统的生活方式和工作方式在现代社会已经发生了翻天覆地的变 化，网络的概念深入人心。以i n t e m e t 为例，其上的信息量每天都在以爆炸的速度在增长， 涉及的业务也同益多样化，人类与网络的距离正在日益拉近，i n t e m e t 己经成为现代人获 取知识和资讯的重要手段。i n t e m e t 只是人们所熟知的网络中最常见的代表，网络的概念 已经不再局限于传统的由计算机和路由器所组成的网络。有线电视网络、交通运输网络、 移动通信网络等，都是人们日常生活中接触最频繁的网络。同时，还有一些抽象的网络也 与人们的日常生活密切相关，如人与人之间形成的人际关系网络，各个国家进行外贸交易 时形成的贸易关系网络，科学家进行科学研究时形成的科研合作网络等。借助于现代大型 计算机数据处理和计算能力的飞速发展对这些网络的特性进行研究，科学家们发现这些真 实网络既不是完全的规则网络，也不是完全的随机网络，而是具有与前两种网络截然不同 的统计特征的网络，科学家们将这些网络统称为复杂网络。 2 0 世纪末，英国著名物理学家斯蒂芬霍金曾预言：“t h en e x tc e n t u r yw i l lb et h e 2 南京邮电大学硕士研究生学位论文第一荦绪论 c e n t u r yo f c o m p l e x i t y ( 下一个世纪将是复杂性的世纪) ，作为这个预言的佐证，复杂网络的 研究已经成为了本世纪初最热门的研究课题之一，复杂网络研究正渗透到从数理学科到生 命学科和工程学科等众多不同的领域，对复杂网络定量与定性特征的科学理解已成为网络 时代科学研究中的一个极其重要的挑战性课题【。复杂网络理论将现实世界中的复杂系统 抽象为网络，研究其拓扑结构特性及其上的动态传播行为等，为我们进行复杂性研究提供 了一个崭新的视角，复杂网络理论已经成为了分析现实复杂系统的强有力的工具。 自从p a s t o r - s a t o r r a s 等人进行了复杂网络上病毒传播研究的先遣工作后【2 一钉，复杂网络 中的病毒传播受到了越来越广泛的关注。近年来的研究表明，网络的拓扑结构与网络上的 传播行为之间有着密切的关系【5 培】。根据网络的拓扑特性找出其上病毒传播的共同规律， 从而针对不同的网络研究病毒防御和控制的策略，具有重要的现实意义。随着复杂网络研 究的不断深入，越来越多的网络拓扑性质被揭示出来，例如加权网络特性【9 , 1 0 】( w e i g h t e d n e t w o r k ) 、社团结构特性【1 1 1 ( c o m m u n i t ys t r u c t u r e ) 、局域世界特性【1 3 。1 6 】( l o c a l w o r l d ) 等。与此同时，为了解释这些性质，很多学者进行了深入的研究工作，提出了新的网络模 型，从不同角度研究了病毒在现实复杂网络的传播性质。如b a r t h 6 1 e m y 等人研究了加权 无标度网络中的病毒传播【9 】，发现在实际的加权网络中，除了节点的度分布服从幂律分布 外，网络中的边权值也服从幂律分布。b a h a t 等人基于对现实加权网络的实证性研究1 1 0 ， 提出了加权无标度网络模型( b b v 模型) ，揭示了实际网络中的加权特性，再现了现实加 权网络中度分布，权值分布的幂律特性。刘宗华等人研究了病毒在具有社团结构的网络中 的传播特性【1 1 , 1 2 】，发现具有社团结构的网络更易于病毒传播。许丹等人采用s i s 模型研究 了局域世界网络上的病毒传播特性【1 7 】，发现随着参数m m 的增加，网络逐步从均匀网络 转变为非均匀网络，病毒传播的临界值逐步下降。上述的这些研究工作丰富了复杂网络的 体系结构，同时也给病毒传播研究工作提出了新的挑战和发展机遇。 多局域世界特性( m u l t il o c a l w o r l d ) 是由局域世界特性发展而来，更真实、更准确 地反映了现实复杂网络的拓扑结构特性。本文以多局域世界特性为切入点，研究多局域世 界网络中的病毒传播及其控制策略。以往的研究都是基于一个静态的网络模型，本文采用 的多局域世界演化模型最早是为了反映i n t o m e t 的动态演化而提出的一种网络模型，能够 很好地反映复杂网络的多局域世界特性，且网络模型中节点的度分布，幂律指数和聚类系 数与实际得当1 引。以往的研究大多基于平均场理论【1 9 】，这种研究方法只能反映病毒传播 过程的平均趋势，却无法体现病毒传播过程中的概率事件和个体之间的交互行为。本文采 用元胞自动机对病毒的传播过程进行研究。元胞自动机是一个时间和空间离散的动力模 型，每一元胞取有限的状态，依据确定的局部规则做同步更新，大量元胞通过相互作用而 3 南京邮电大学硕士研究生学位论文 第一章绪论 构成动态系统的演化。因此，元胞自动机能够很好地体现病毒传播过程中的概率事件和交 互行为陬1 1 。 1 3 研究内容与章节安排 本课题的主要研究内容是，通过阅读大量相关文献，把握病毒传播理论研究的动向， 理解现有研究成果，主要包括复杂网络中病毒传播临界值理论，复杂网络的免疫策略以及 网络拓扑结构对病毒传播的影响等。在此基础上，引入多局域世界演化模型，结合元胞自 动机理论，分析多局域世界网络中病毒传播的特性，并进行相应的仿真，最后对多局域世 界网络中的控制策略进行讨论。 论文的内容安排大致如下： 第一章阐述论文的研究背景与现状。首先从最常见的病毒传播现象入手，引入了复杂 网络中病毒传播的概念，并简要介绍了现有的针对复杂网络的不同拓扑特性的研究成果， 最后提出本文的研究内容和章节安排。 第二章系统地综述了局域世界网络中的病毒传播及其控制策略。主要包括局域世界演 化模型，局域世界网络中的病毒传播及其控制策略，并从初始感染节点对病毒传播的影响 和传播临界值两个角度考察局域世界网络中病毒传播的特性。 第三章研究多局域世界网络中的病毒传播。首先分析现实网络中普遍存在的多局域世 界特性，接着引入多局域世界演化模型，并通过理论分析，对多局域世界演化模型基本算 法提出两点改进，使其能够更加准确地反映现实网络的动态演化。随后引入元胞自动机模 型，利用元胞自动机理论对多局域世界网络中的病毒传播进行分析，最后对多局域世晃网 络中的病毒传播特性进行数值仿真。 第四章研究多局域世界网络中的控制策略。首先研究基于随机免疫和目标免疫的控制 策略，然后针对复杂网络的多局域世界特性，提出一种新的基于局域世界间连接矩阵的控 制策略，并对这种控制策略的性能优劣进行数值仿真和分析，最后对各种控制策略进行了 总结和探讨。 第五章主要对本课题所做的工作进行总结，并结合作者对病毒传播的理解，对下一步 的研究工作进行展望。 4 南京邮电大学硕士研究生学位论文 第二章局域世界网络中的病毒传播 第二章局域世界网络中的病毒传播控制 2 1 局域世界演化模型 b a r a b f i s i 和a l b e r t 提出的b a 无标度网络模型，刻画了众多现实复杂网络的统计特性，它 将现实复杂网络的演化归结为两种简明扼要的机制：增长和优先连接【2 2 1 。这旱的优先连接 机制，指的是全局的优先连接机制。新加入的节点选择已有节点建立连接时，更倾向于与 全局网络中具有较高连接度的“大 节点相连接。李翔等人在对世界贸易网的研究中发现 2 3 】，b a 无标度网络的全局优先连接机制并不适用于那些只与少数国家有贸易往来关系的 国家。在这个世界贸易网中，每个国家抽象为网络中的一个节点，如果两个国家之间有贸 易往来，则相应的两个节点之间存在一条连接边。研究表明，许多国家都在致力于加强与 各自区域经济合作组织( 如欧盟、东盟、北美自由贸易区等) 内部的国家之间的经济合作 和贸易往来，优先连接机制只存在于这些区域经济合作组织中。也就是说，世界贸易网中 的优先连接机制是作用在某个局域范围内的，而不是全局范围内的。这一现象揭示了现实 复杂网络的一个重要特性局域世界特性。概括而言，局域世界可以是世界贸易网中的 区域经济合作组织，也可以是计算机网络中的自治域、人类社会的社团组织等。所有这些 都说明局域世界现象存在于诸多现实复杂网络中。 b a 无标度网络根据全局优先连接机制确定节点之间的连接关系，由此得到符合幂律形 式的网络度分布。然而在许多现实复杂网络中，由于局域世界特性的存在，网络中的每个 节点都属于某个特定的局域世界，因而也只能占有和使用各自局域世界的连接信息，而不 能使用全局的连接信息。因此，使用局域世界优先连接机制代替全局优先连接机制，能够 使得网络模型的演化更加符合现实复杂网络的特性。李翔等人提出如下的局域世界演化模 型的构造算法【1 3 】： 增长过程：网络初始时有m 。个节点和e 。条边，每次新加入一个节点和附带的m 条 边： 局域世界优先连接过程：随机地从网络中已有的节点中选取膨个节点( m m ) ， 作为新加入节点的局域世界。新加入的节点根据优先连接概率 n t o 。a l ( k , ) _ ，( 呲聊e k 万i 兰羔e k z i l o c a l 0l o c a l ( 2 - 1 ) 厶一 一j j 、一 。j s 堕室塑皇查兰堡主堕塞生堂垡丝塞 一 。茎三童星苎堂墨塑竺! 箜堑童堡堡 来选择与局域世界中的m 个节点相连，其中l w 由新选的m 个节点组成。 对以上构造算法分析可知，在任意t 时刻，m 满足关系式：m m 册。+ t 。因此， 局域世界演化模型存在下面两种特殊情况：m = 坍：m = m o + f 。当m = m 时，随机 选择的局域世界内节点的个数与新加入的节点附带的边数相等，新加入的节点与随机选择 的局域世界内的所有节点相连接，此时相当于保留了b a 无标度网络模型的增长机制，而优 先连接机制则完全失去了作用。理论分析表明，这种情况生成的网络的度分布服从指数分 一主 布，p ( k ) em 。当m = m 。+ t 时，每个新加入的节点的局域世界其实就是整个网络，此 时的局域世界优先连接机制完全等价于全局优先连接机制，局域世界演化模型完全等价于 b a 无标度网络模型，网络的度分布服从幂律分布，p ( k ) 芘2 m 2 k 。3 。当m m 表 ，( ， 示无标度网络的平均均方度。对网络规模j0 0 的无标度网络，传播临界值以专0 。因 此在病毒的传播过程中，只要有效传播率五大于0 ，病毒就能在无标度网络中传播并最终维 持在一个平衡状态。对于有限规模的无标度网络，虽然存在一个正的传播临界值，但相比 于均匀网络的传播临界值，这个值要小得多。因此，无论病毒有效传播率的大小如何，对 于度分布服从幂律分布的无标度网络，面对病毒传播时均具有脆弱性的特点。 8 0o1 工o80 ； 叭 仃4 t = o 伽 4 m 砂 020 南京邮电大学硕士研究生学位论文第二章局域世界网络中的病毒传播 在局域世界网络中，也存在传播临界值。图2 2 对b a 无标度网络和局域世界网络的传 播临界值作了比较，初始随机选取网络中1 的节点做为初始感染节点，使病毒在网络中自 发地进行传播，记录稳态时被感染节点数占总节点数的比例。横坐标表示有效传播率a ， 纵坐标表示稳态时被感染节点数占总数的比例i 。通过比较可发现，b a 模型中存在一个较 小的临界值，在0 0 7 左右；在局域世界模型中，临界值相对大一些。在m m = 4 0 3 时， 丸= o 0 8 ；在m m = 4 3 时，以= o 1 3 。 图2 2b a 无标度网络与局域世界网络的传播临界值对比【1 7 1 对于局域世界网络，选取不同的m m 值，得至i j s i s 模型不同的传播临界值，两者之间 的关系如图2 3 所示。 图2 - 3 病毒传播临界值与局域世界模型参数m m 的关系【1 7 】 由图2 3 可见，随着参数m m 的增大，网络逐步从均匀网络转变为非均匀网络，传播 临界值逐渐减小，这与无标度网络上传播临界值消失这一结论正好吻合。这说明网络越不 均匀，病毒在其上传播的临界值越小。这也体现了由局域世界模型所得到的非均匀网络在 9 南京邮电大学硕士研究生学位论文第二章局域世界网络中的病毒传播 面对病毒攻击时存在的脆弱性。 2 3 局域世界网络中的控制策略 对网络中的节点进行免疫，是控制病毒传播的一种重要方法。采取不同的免疫策略， 可以得到不同的免疫效果。随机免疫和目标免疫是目前最常见，也是探讨得最多的两种免 疫策略。 随机免疫也称均匀免疫【2 5 】，它不考虑网络中节点之间度、权值等特征量的差异，完全 平等地对待网络中的每一个节点，随机地选择网络中的部分节点进行免疫。p a s t o r - s a t o r r a s 等研究发现【2 4 1 ，对于无标度网络采用随机免疫法，几乎需要对网络中的全部节点进行免疫， 才能保证最终消灭病毒的传播。 另一种常见的免疫策略是目标免疫策略。这种免疫策略充分考虑到无标度网络度分布 的非均匀性特点，针对性地选取网络中度大的节点进行免疫。一旦这些节点被免疫，则意 味着它们所连接的边可从网络中去除，从而使得病毒传播的途径大大减少，有效地切断了 病毒的传播路径【2 6 1 。 针对局域世界网络的具体网络特性，许丹等人研究了其上的控制策略1 7 】，并将免疫效 果和b a 无标度网络上的免疫效果相比较，最后对随机免疫和目标免疫这两种策略在局域世 界网络中的有效性进行了探讨。 对于b a 无标度网络，m m = 4 0 3 和m m = 4 3 的局域世界网络，采用随机免疫和 目标免疫的比较分别如图2 4 ( a ) ( c ) 所示。其中横坐标表示被免疫的节点数占总节点数的 比例，纵坐标为加入免疫后最终被感染的节点数与没有免疫情况下最终被感染的节点数的 比值。 仿真结果表明，b a 无标度模型中这两种免疫方式的差异最明显。为了彻底消除感染， 目标免疫和随机免疫分别需要免疫1 5 和8 0 的节点；在m m = 4 0 3 的局域世界模型中， 这种差异有所减小，分别为2 0 和7 0 ；在m m = 4 3 的网络中进一步缩小，分别为3 0 和6 0 。对网络中度最大的那些节点进行免疫与随机选取节点进行免疫的效果之间的差异， 体现了网络中节点地位之间的差异，而这种差异随着参数m m 的增大而增大，即在非均 匀网络中更加明显。因此，从病毒传播的角度可以应证局域世界演化模型所体现出的演化 特性，以及网络拓扑结构对病毒传播的影响，即无标度网络更易于病毒的传播，目标免疫 在非均匀网络上的效果好于均匀网络。 需要指出的是，研究局域世界网络中的免疫机制，可以事先( 即病毒未爆发前) 随机选 南京邮电大学硕士研究生学位论文第二章局域世界网络中的病毒传播 取处于易感状态的节点，或者有目的地选择处于易感状态度最大的节点进行免疫，切断它 与其他节点的连接，观察采取免疫措施后病毒在网络上的传播行为，旨在研究需要免疫掉 多大比例的节点，最终使病毒无法传播扩散，因此这里的免疫针对的仅是易感节点( 状态s ) 。 g ( a ) b a 无标度网络 ( b ) 局域世界网络( m m = 4 0 3 ) ( c ) 局域世界网络( m m = 4 3 ) 1 虱2 - 4 无标度网络与局域世界网络的随机免疫和目标免疫的对比f 明 1 1 南京邮电大学硕士研究生学位论文 第二章局域世界网络中的病毒传播 2 4 本章小结 局域世界特性是许多现实复杂网络的一个重要特性。本章介绍了局域世界网络的病毒 传播研究，从初始感染节点、传播临界值和免疫机制3 个方面考察了局域世界模型中的病 毒传播特性。初始感染节点选择的不同导致的传播行为差异，从一个侧面反映了网络拓扑 结构对病毒传播的影响。在局域世界演化模型中，随着参数m m 的增大，网络节点的度 分布表现出从指数到幂律的变化过程，病毒传播临界值呈下降趋势，而随机免疫和目标免 疫两种策略之间的差异更加明显。从病毒传播的角度看，反过来也验证了局域世界模型所 体现出的在均匀网络与非均匀网络之间的演化特性。 以局域世界特性为基础，对现实复杂网络的进一步研究揭示，多局域世界特性也是现 实复杂网络的一个重要特性。下一章将针对现实复杂网络的这个特性，探讨多局域世界网 络中的病毒传播。 南京邮电大学硕士研究生学位论文 第三章多局域世界网络中的病毒传播 第三章多局域世界网络中的病毒传播 3 1 多局域世界演化模型 从现实复杂网络的局域世界特性出发，则网络中的任一节点都属于某一个特定的局域 世界，不同的节点可能属于不同的局域世界。各个局域世界内部的联系较为紧密，而局域 世界之间的联系较为稀疏，整个网络可以看成是一个由多个局域世界构成的网络。这就揭 示了现实复杂网络的一个重要特性一多局域世界特性。 以i n t e m e t 为例，在a s 层面上，可以示意性地将i n t e m e t 的层次分为国际连接、国家 主干、区域网络和局域网。区域网内的节点紧密连接使得此网络内具有很高的聚类系数， 而这些高度聚合的区域网由国际连接或国家主干稀疏地相互联系在一起。当一个新节点加 入到一个区域网络时，它对其它区域网络中的节点的影响非常小，而它反过来主要受本区 域网中的节点的影响。若将区域网看作一个“局域世界”，那么整个i n t e m e t 可以看作是 一个由很多的局域世界组成的多局域世界网络。多局域世界演化模型最早就是为了动态地 反映i n t e m e t 的拓扑结构演化而提出的一种模型，理论分析表明，多局域世界演化模型能 够很好地反映复杂网络的多局域世界特性，且模型中节点的连接度幂律分布，幂律指数和 聚类系数与实际得当【27 1 。 3 1 。1 多局域世界演化模型基本算法 多局域世界演化模型的基本思想是：改进b a 无标度网络模型中的增长机制，细分为 节点的增长、局域世界的增长、局域世界内边的增长和局域世界之间远程边的增长；利用 局域世界优先连接机制代替b a 无标度网络模型中的全局优先连接机制；增加边的消亡机 制。 与局域世界演化模型相比较，多局域世界演化模型增加了局域世界的增长、局域世界 之间远程边的增长和边的消亡这三种机制，能够使得网络模型的演化更加与现实网络的演 化相符。 多局域世界演化模型的构造算法如下： 起始为m 个孤立的局域世界，在每个局域世界内部均有m 。个节点、e 。条边。每一步 随机地进行如下的一个操作： 1 3 毒传播 ( 1 ) 以概率p 增加一个拥有个节点、条边的局域世界； ( 2 ) 以概率g 将一个新节点加入到一个已存在的局域世界中，它与同一个局域世界 中的节点建立条边。首先随机地选取一个局域世界q ，此局域世界中，新节点将要连 接的节点由如下概率选取： n ( 屯) 。丽k i + g j m 。 ( 3 - 1 ) 重复此过程m 次； ( 3 ) 以概率，增加m ，条边到一个选定的局域世界。首先随机地选取一个局域世界， 边的一端随机选取，另一端根据概率式( 3 一1 ) 选定，重复此过程所：次； ( 4 ) 为刻画边的消亡，以概率s 在一个选定的局域世界内去掉m ，条边。首先随机选 取一端，另一端由如下概率选定： 诹，) = 而1 - 1 - 而i ( k , ) ( 3 - 2 ) 其中心( f ) 为局域世界q 内的节点个数，重复此过程m ，次； ( 5 ) 以概率“在一个选定的局域世界与其它已存在的局域世界间建立朋。条长程边。 首先随机选取一个局域世界，在其内部根据概率式( 3 1 ) 选定一个节点，作为边的一端，边 的另一端位于另一个随机选取的局域世界内，其选定概率仍为式( 3 - 1 ) ，重复此过程次。 上述参数满足0 q 1 ，0 p ，、s 、“ 1 ，p + q + ，+ j + t t = 1 。 3 1 2 多局域世界演化模型的度分布分析 采用平均场理论对多局域世界演化模型进行分析，可以获得模型中局域世界q 内节 点i 的度分布，其推导如下： 以概率p 创建一个新的局域世界。 这种情况下，一个已存在局域世界内的节点i 的度分布并不随时间变化，因为新产生 的局域世界内的节点与其它已存局域世界内的任何节点均无边，故此 n - - ( 3 - 3 ) ( a m k i ) 鲫= 朋m + l q 妒乙k ( i + + 万 ( 3 4 ) a k il = r m 2b 1 + ( 一划赫l p 5 ， ( 乱，s - m - 1 3 - i 制1 - 一剖赤 ，一弗 p 6 ， ( 孰一b 茹葡1 而1 驷k , + aj 仔7 ， e ( k ) = _ _ 忑( m l + b a ) 4 ( k + b a ) 吖 ( 3 - 8 ) 7 a 3 m + t ( i + 2 p ) 】州 、 南京邮电大学硕士研究生学位论文第三章多局域世界网络中的病毒传播 p 关r p 9 ， 可以验证，若令册：2 s i n 3 ，那么条件式( 3 9 ) 就能得到满足。注意到，幂律指数随着网络 中节点的吸引力的增加而增加，这表明网络中节点的吸引力可能会起到很重要的作用。 多局域世界演化模型的几种特殊情况： 当朋= 1 ，q = l ，p = ，= s = u = 0 时，网络中只有一个局域世界，且幂律指数为 y = 3 + a m ，这时退化为b a 无标度模型。 如果网络仅仅包含一个局域世界，且网络的进展仅仅包括节点和边的产生，即 m = l ，p = ，= 占= u = 0 ，那么幂律指数为7 = 3 + a q ( m l - - m 2 ) g + m 2 】。这表明，已存节 点间