（控制理论与控制工程专业论文）复杂网络及其上的病毒传播和演化博弈的研究.pdf

摘要 传染病在人群中的流行和博弈演化中策略的选择，都可以看作是服从某种规 律的网络上的动力学行为，如何去描述这种行为，寻找对该行为进行有效控制的 方法，一直是科学家们共同关注的焦点。 本文在阐述复杂网络基本理论的基础上，主要研究了三个方面的内容：首先 对于网络上的疾病传播，在验证了网络的平均度的增加不利于病毒传播的控制之 后，从不同的个体具有不同的抵抗力出发，提出了基于节点度大小和基于个体抵 抗力的两种不同的免疫策略，结果表明采取前一种策略能更有效的抑制病毒的传 播；其次研究了网络上的演化博弈，通过经典博弈模型在改进的无标度网络中的 合作演化，验证了网络的异质性对合作的促进作用，然后提出了一种新的公众博 弈模型，其采取的多样化的分配资产方式有利于促进合作；最后以面向对象编程 的思想设计并实现了“网络拓扑模型构造器”，通过设定网络参数，生成基本网络 拓扑结构，并分析网络的度分布特性。 关键词：复杂网络病毒传播演化博弈拓扑模型 a b s t r a c t t h ee p i d e m i cs p r e a d i n ga m o n gt h ep e o p l ea n dt h es t r a t e g yi nt h ee v o l u t i o n a r yg a m e s a l lc a l lb es e e na st h ed y n a m i cb e h a v i o r sw h i c hc o n f o r mt oc e r t a i nr u l e s t h es c i e n t i s t s f o c u so nh o wt od e s c r i b et h e s eb e h a v i o r sa n da d o p t i n ge f f e c t i v em e a s u r e st oc o n t r o l t h e s eb e h a v i o r s o nt h ef o u n d a t i o no fi n t r o d u c i n gt h eb a s i ct h e o r ya b o u tt h ec o m p l e xn e t w o r k s ，w e m a i n l yi n v e s t i g a t et h r e ea s p e c t sa sf o l l o w s ： f i r s t ，a b o u tt h ee p i d e m i cs p r e a d i n gp r o c e s s ，a f t e rp r o v i n gt h a tt h eg r o w t ho fa v e r a g e d e g r e eh a v ean e g a t i v ee f f e c to ne p i d e m i cc o n t r o l ，w ea s s u m et h a ti n d i v i d u a lh a si t s o w nr e s i s t a n c e ，a n dt w od i f f e r e n tk i n do fi m m u n i z a t i o ns t r a t e g yw a sp r o p o s e d ：o n ew a s b a s e do nt h ed e g r e eo fn o d e s ，t h eo t h e ra c c o r d e dt oi n d i v i d u a l s r e s i s t a n c e t h er e s u l t s s h o wt h a tt h ef o r m e ro n ew a sm o r ee f f c c t i v e ；s e c o n d ，w er e s e a r c ht h ee v o l u t i o n a r y g a m eo nn e t w o r k s ，i no r d e rt oi n v e s t i g a t et h ei n f l u e n c eo fh e t e r o g e n e o u s i n t e r a c t i o no n t h ee v o l u t i o no fc o o p e r a t i o n , w es t u d yt h ec l a s s i c a lg a m em o d e l sw i t hp l a y e r sl o c a t e d o ni m p r o v e ds c a l e f r e en e t w o r k s w ep r o p o s ean e wp u b l i cg o o d sg a m em o d e l ，i n w h i c ht h ed i v e r s ea s s i g n m e n to ft h ei n v e s t m e n t sw a sa d o p t e d i ti sf o u n dt h a tt h i s s t r a t e g yc a l lp r o m o t ec o o p e r a t i o n t h el a s t ，w ed e s i g n e das t r u c t u r ec o n s t r u c t o ro f n e t w o r kt o p o l o g y , i tc a i lc r e a t et h en e t w o r kt o p o l o g i c a ls t r u c t u r ew i t ht h eu s e r si n p u t p a r a m e t e r s ，a n da n a l y z et h ec h a r a c t e r i s t i c so fd e g r e ed i s t r i b u t i o n k e y w o r d ：c o m p l e xn e t w o r k se p i d e m i cs p r e a d i n ge v o l u t i o n a r yg a m e s t o p o l o g i c a lm o d e l 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：弧逾 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 茸 期 期 日 日 第一章绪论 第一章绪论 1 1 复杂网络的提出 在现实世界中，许多复杂系统都需要用网络的形式加以描述，而且这些网络 与人类生活、工作息息相关。例如，把人看作是网络中的一个点，人与人之间的 交往看成是连接节点的一条边，就构建成为社会关系网，那么地球上任意两个人 之间要通过多少个朋友才能互相认识? 把一台计算机看成是网络中的一个节点， 计算机之间的互联看成连接节点的一条边，形成了计算机互联网，那么层出不穷 的计算机病毒是如何在互联网上传播的? 此外，各种传染病( 艾滋病、非典型性肺 炎和禽流感等) 是如何在人类和动物中流行的? 为什么流言蜚语会散布的很快? 全球或地区性金融危机是如何发生的? 局部故障是如何触发大规模停电事故的? 为什么大脑能够具有思维的功能? 这些问题尽管看上去各不相同，但是每一个问 题中都涉及很复杂的网络，更为重要的是，越来越多的研究表明，这些看上去各 不相同的网络之间有着许多惊人的相似之处。正因为如此，研究网络的结构，发 现其内在的共同特征是众多学科领域的科学工作者一直所关注的问题。从最初的 规则网络，到后来的随机网络，以及近年来研究的复杂网络，越来越多的成果被 人们发掘出来，从而为人们更加深刻的认识现实世界，了解网络系统的功能和演 化规律以便对之进行控制或者应用提供了可能。 1 2 复杂网络的研究历程 从哥尼斯堡七桥问趔l j 到随机图理论：复杂网络的研究可追溯到1 8 世纪最伟 大的数学家欧拉对哥尼斯堡( k o n i g s b e r g ) 七桥问题的探讨，k o n i g s b e r g 是现俄罗斯 的一个城镇，城中有一条贯穿城区的河流，河中有两个岛，两岸和两岛之间共架 有七座桥，如图1 1 所示。相传有这样一个有趣的问题：一个人能否在一次散步中 走完所有的桥，而且每座桥只经过一次，最后返回原地? 这个问题看起来似乎相 当简单，但长期以来小镇上没有一个人能走出这样一条路径。1 7 3 6 年，欧拉仔细 地研究了这个问题。他利用数学抽象法，将被河流分隔开的四块陆地抽象为四个 点，分别用a 、b 、c 和d 表示，而将连接这四块陆地之间的七座桥抽象为连接四 个点的七条线，分别用a 、b 、c 、d 、e 、f 、g 表示。这样就得到了由四个点和七条 线构成的一个图，如图1 1 所示。于是七桥问题就转换为如下的数学问题：从图 1 1 中的任一点出发，经过每条边一次而后返回原点的回路是否存在? 欧拉给出了 存在这样一个回路的充要条件，并由此推得上述七桥问题是没有解的。 复杂网络及其上的病毒传擂和演化博弈的研究 图1i 七桥问题图示 欧拉对七桥问题的抽象和论证思想，开创了数学中的一个分支图论的研 究。而图1 i 也被公认为欧拉图。事实上，今天的人们关于复杂网络的研究与欧拉 当年关于七桥问题的研究在某种程度上是一脉相承的，即网结结构与网络性质密 切相关。 在欧拉解决七挢问题之后的相当一段时间里图论并未获得足够的发展。2 0 世纪6 0 年代，由两位匈牙利数学家e r d 6 s 和r 6 r 研建立的随机图理论( r a n d o mg r a p h t l l e o f y ) 被公认为是在数学上开创了复杂网络理论的系统性研究吲。在e r d o s 和r & l y i 研究的随机图模型f 称为e r 随机图冲，任意两个节点之间有一条边相连接的概率 为p 。因此一个含有n 个节点的e r 随机图中边的总数是一个期望值为 p n ( ni ) 2 1 的髓机变量。由此可以推得，产生一个有n 个节点和m 条边的e r 随机图的概率为p u ( 卜p ) ”“2。e r d 6 s 和r 6 n y i 系统性地研究了当_ _ 时e r 随机图的性质( 如连通性等) 与概率p 之间的关系。e r d 6 s 和r 6 n y i 的最重要的发现 是：e r 随机图的许多重要的性质都是突然涌现的。也就是说，对于任一给定的概 率p ，要么几乎每一个图都具有某一个性质，要么几乎每一个图都不具有该性质。 e r d o s 和r d n y i 建立的随机图理论被公认为对复杂网络理论的系统性研究具有开创 性的意义。 从小世界实验到复杂网络研究的新纪元：在2 0 世纪的后4 0 年中随机图理 论一直是研究复杂网络的基本理论。在此期间，人们也做了试图揭示社会网络特 征的一些实验。比如著名的小世界实验( s m a l lw o r l de x p e r i m e n t ) 。一个社会网络就 是一群人或团体按某种关系连接在一起而构成的一个系统。这里的关系可以是个 人之间的朋友关系、同事之间的合作关系、家庭之间的联姻关系和公司之间的商 业关系等等。以朋友关系为例，很多人都有这样的经历：偶尔碰到一个陌生人， 同他聊了一会儿以后发现你认识的某个人居然他也认识，然后一起发出“这个世 界真小”的感叹。那么对于地球上任意两个人来说，借助第三者、第四者这样的 间接关系来建立起他们两人的联系，平均需要通过多少人呢? 2 0 世纪6 0 年代美国 第一章绪论 3 哈佛大学的社会心理学家s t a n l e ym i l g r a m 通过一些社会调查后给出的推断是：地 球上任意两个人之间的平均距离是6 。也就是说，平均中间只要通过5 个人，你就 能与地球上任何一个角落的任何一个人发生联系。这就是著名的六度分离( s i x d e g r e e so f s e p 删i o n ) 推断【3 l 。从此以后，关于小世界现象的实验不断被报道。例如， 科学家协作网络的e r d f s 游戏，i n t e m e t 的小世界实验等。这些实验的涌现使得人 们对复杂网络的科学探索发生了重要的转变，复杂网络理论也不再局限于数学领 域。人们可以考虑节点数量众多、连接结构复杂的实际网络的整体特性，在从物 理学到生物学的众多学科中掀起了研究复杂网络的热潮，甚至被称为“网络的新 科学1 9 】”。 上个世纪之末，有两篇开创性的文章可以看作是复杂网络研究新纪元开始的 标志：一篇是美国康奈尔( c o m e l l ) 大学理论和应用力学系的博士生w a r s 及其导师、 非线性动力学专家s t r o g a t z 教授予1 9 9 8 年6 月在n a t u r e 杂志上发表的题为“小 世界 网络的集体动力学( c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s ) 的文 章【4 】；另一篇是美国n o t r ed a m e 大学物理系的b a r a b d s i 教授及其博士生a l b e r t 于 1 9 9 9 年l o 月在s c i e n c e 杂志上发表的题为随机网络中标度的涌现) ) ( e m e r g e n c eo f s c a l i n gi nr a n d o mn e t w o r k s ) 的文章【5 j 。这两篇文章分别揭示了复杂网络的小世界特 征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。 1 3 复杂网络研究内容 自从1 9 9 8 年w a t t s 和s t r o g a t z 提出小世界网络模型以来，复杂网络的研究在 过去几年得到了迅速发展。原因有以下几个方面： ( 1 ) 数据库容量的持续增加和计算机技术的迅猛发展，使我们有可能获得各种 大规模网络的统计性质； ( 2 ) 实证分析表明，从万维网到新陈代谢网，许多领域的各种复杂网络展现了 某些共同的统计性质，如幂律分布，表明其中可能存在一些普适性的概念 和规律； ( 3 ) 理论研究也有了突破。w a r s 和s t r o g a t z 给出了小世界网络的构造方式， b a r a b o s i 和a l b e r t 则指出，增长和偏好连接是形成无标度网络的根本原因， 统计物理学的研究方法在复杂网络研究中得到了广泛应用。 理论研究和实证分析1 7 - 1 0 的相互促进在复杂网络的研究中得到了充分体现。 目前，复杂网络的研究工作主要集中在以下几个方面： ( 1 ) 对实际复杂网络特性进行深入和广泛的分析：这一个方面可视为复杂网络 研究中最基础的一步。事实上，只有通过获得现实世界中的网络数据并分 析它们的共性，科学家f f j z l 能提出这些经典的网络模型，比如小世界网络 4 复杂网络及其上的病毒传播和演化博弈的研究 和无标度网络。对更多实际复杂网络的数据进行更广泛的实证研究和更深 入的理论刻画，如给定度分布基础之上的匹配模式、各种相关关系、加权 网络的统计性质 2 0 - 2 4 】和描述方式以及网络的聚类等，才能构建新的更符合 实际的网络模型； ( 2 ) 复杂网络的建模问题研究 i f - 1 4 ：科学家在研究的过程中，发现了一些网络 的共性，比如网络的度分布符合特定的规律等等。于是为了研究的方便， 人们就把网络模型化，并且模型化以后的网络具备了实际网络的某种或某 几种特性。另外，在一些经典模型的基础上，科学家们又做了大量的工作， 在这些模型的基础上做了多次修改，提出了一系列的改进模型，这些我们 将在以后的章节详细介绍； ( 3 ) 复杂网络上的动力学研究1 1 5 - 1 9 l ：包括网络容错性和攻击鲁棒性，以及网络 上的传播、同步与共振等各种动力学过程。人们对网络动力学的研究主要 集中在网络上的传播和同步化两个方面。而在本文中主要讨论病毒传播动 力学过程和不同复杂网络模型上进化博弈的动力学演化； ( 4 ) 复杂网络的应用问题：虽然复杂网络的研究尚出于起步阶段，但是迄今为 止已发现了许多有趣的应用。例如对复杂网络的同步问题的研究可以应用 在通信领域，对网络搜索和导航【2 5 j 问题的研究在计算机路由问题中有着很 大的潜力，以及对病毒传播的研究对于有效控制疾病传播的促进作用。随 着科学家们在复杂网络方面研究的深入和透彻，这些成果的应用也会越来 越广泛。 总之，人们在复杂网络的研究过程中，首先通过揭示刻画网络系统结构的统 计性质，以及度量这些性质的合适方法来建立合适的网络模型以帮助人们理解这 些统计性质的意义与产生机理；然后再分析单个节点的特性和整个网络的结构性 质来分析与预测网络的行为，这些研究思路也促使人们开始从整体上研究网络的 结构与性能之间的关系；最后提出改善已有网络性能和设计新的网络的有效方法， 特别是稳定性、同步性和数据流通等方面。 1 4 复杂网络的研究意义 复杂网络是一门富有生命力而且应用极为广泛的学科。它渗透到非线性科学、 电路与系统、计算机科学、控制理论、理论物理、数学、生物学、经济学、生态 学等各个学科领域。复杂网络的研究无论在理论上还是应用上都有非常重要的意 义：一方面，对复杂网络的深入研究可以使我们更好的了解和解释现实世界的复 杂系统，从而了解自然、了解我们所生活的现实世界，这也是科学研究最主要的 目的之一；另一方面，随着对复杂网络研究的深入，我们可以应用理论研究成果 第一章绪论 5 到具体问题中去，如可以设计出具有更好特征的实际网络或使网络处于对我们更 有利的状态，使得网络理论可以更好地为我们所用。如今，复杂网络理论不仅在 电力网、通讯网、运输网、计算机网等技术性网络和基因网络、蛋白质网络等生 物网络的分析和设计中得以应用，而且也渗透到电路布图、模式识别、统筹管理、 场所选址等网络优化问题中。更为值得注意的是，复杂网络理论不仅可以被应用 到自然科学，而且也被应用到社会科学中。例如：通过构建社会网络中人与人直 接的关系网络模型去研究传染病在人群中的流行、谣言在社会中的扩散以及演化 博弈中的策略的选择。从而我们可以深入的描述这些动力学行为，揭示它的特性， 寻找去对该行为进行有效控制的方法等。综上所述，复杂网络的研究有着非常重 要的意义。 1 5 本文研究内容 现实中的复杂系统是动态演化的，是开放自组织的，是规则与随机伴行的。 复杂网络理论的建立，为深入了解现实复杂系统的内在机制提供了可能。本课题 的研究内容为探索复杂网络的拓扑结构，针对疾病传播的动力学行为和博弈演化 过程，通过对原有复杂网络模型的进一步扩展，研究了网络结构和拓扑性质对网 络上的病毒传播与合作行为有怎样的影响。除此之外，目前研究者在研究复杂网 络时，大都把重点放在了对复杂网络理论的研究上，而在如何利用计算机编程技 术对网络生成进行仿真这一领域却缺乏深入的研究。本文在理论的基础上，充分 考虑到仿真实验或者工程实践中将复杂网络拓扑结构的理论模型转换为实际的拓 扑图形的需求，以面向对象编程的思想设计并实现了动态生成网络这一过程。 本文共分为六章，各章内容安排如下： 第一章为绪论，主要介绍了研究问题的提出，复杂网络研究的发展和意义， 特别指出了本文所做的主要工作。 第二章介绍了复杂网络理论基础理论知识，复杂网络的两大特性：小世界与 无标度，最后在已有的一些经典复杂网络的模型的基础上，介绍了一些改进的网 络模型，并进行了简单分析。 第三章我们将介绍网络上疾病传播的经典模型，在不同的网络上疾病的传播 过程以及采取不同的措施进行免疫后对疾病传播的影响。 第四章首先介绍了经典博弈模型，然后具体介绍这些模型在复杂网络上的合 作演化以及在扩展的网络模型上分析网络结构对合作演化的影响。 第五章在v i s u a lc + + 编译环境下以面向对象思想设计并实现了“网络拓扑模型 构造器，它既可以根据用户的输入参数生成包括随机网络、小世界网络和b a 无 标度网络等典型网络的拓扑结构图，也可以分析给定网络的度分布特性。 6 复杂网络及其上的病毒传播和演化博弈的研究 第六章为结论，将介绍我们在复杂网络方面的研究成果，并在文章的结尾提 出总结和展望。 概括起来，本文的创新点包括以下几点： 1 利用计算机模拟仿真的方法，验证了不同的网络结构上s i s 模型的传 播过程，分析了对于平均度不同的小世界和b a 网络，结果表明平均度 的增加不利于疾病传播的控制；其次，我们研究了个体具有不同抵抗 力时疾病传播的过程。我们使每个个体随机的具有一定的抵抗力，并 且在传播过程中，个体的抵抗力不改变。在病毒的传播过程中，当个 体的邻居处于感染状态时，个体被感染上的概率与个体本身的抵抗力 成反比。由此我们研究了两种不同的免疫策略：一种是基于节点度大 小的免疫，我们从度最大的节点依次开始免疫，考察免疫个体占总个 体数不同比例时病毒的传播情况；另一种是基于个体抵抗力的免疫策 略，我们对抵抗力弱的个体优先免疫。我们发现对于最终整个网络中 被感染个体的比率来说，基于节点度大小的策略要优于基于个体抵抗 力的策略。 2 本文研究了经典的博弈模型在改进的无标度网络中的合作演化，验证 了网络的异质性对合作的促进作用；然后我们提出了一种新的公众博 弈模型，博弈个体根据不同团队的合作水平进行决策，从而决定如何 分配资产，我们发现，与个体平均分配资产进行投资的方式相比较， 这种多样化的分配资产方式能够更有利于促进合作。 3 利用面向对象的程序设计思想，设计并实现了“网络拓扑模型构造器， 该软件可以根据v c + + 生成界面上的菜单项选择我们熟知的网络类型， 并且设定网络参数，从而动态的生成网络拓扑结构。在网络演化完成 后，用彩色标注网络节点，这样用户可以直观清晰的观察到网络的节 点分布情况，尤其在节点数比较多，节点度比较大的情况下。最后分 析了节点的度分布，显示节点度在不同网络中的概率分布。 第二章复杂网络的基本概念及其性质7 第二章复杂网络的基本概念及其性质 2 1 概述 复杂网络是从拓扑学的角度对自然界的大量复杂系统的一种很好的描述方式 6 - 8 1 。将真实系统中的个体抽象为节点，而用边来表示个体间的相互联系，网络则 是由这些节点和连接这些节点的边所组成。例如，城市交通网络可以看成是大量 错综复杂的道路相互交织而成的网络1 2 刨；计算机网络可以看作是自主工作的计算 机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络1 2 7 。类似的还 有蛋白质相互作用网络【2 引、社会关系网络i 捌、食物链网络等等。在这里，我们 把网络不依赖于点的具体位置和边的具体形态就能表现出来的性质称为网络的拓 扑性质，相应的结构称为网络的拓扑结构。 在图论里，复杂网络被表示为由一个点集y ( g ) 和一个边集e ( g ) 组成的一个 图。e ( g ) 中的每条边e 有矿( g ) 中的一对点( ，v ) 与之对应。这样，网络可以用几何 图形表示，许多大网络、大系统问题，经过用图模拟，使研究变得概念清晰、形 象直观、目标明确和计算简化。 2 2 网络的表示及其存储方法 2 2 1 网络的矩阵表示法 如概述中所示，网络是由节点集合及其节点间的边集合构成的。边数较少的 网络称为稀疏网络，边数较多的网络称为密集网络，包括所有可能边的网络称为 完全网络。如果网络中的边没有规定方向，则称为无向网络，如果网络中的边规 定为从一个节点指向另一个节点，则称为有向网络。 网络的拓扑结构可以用矩阵来表示。通常用来表示网络的矩阵有关联矩阵和 邻接矩阵。关联矩阵描述了一个网络中节点与边的关系，而邻接矩阵则描述了一 个网络中节点与节点之间的关系。一个简单无向网络的关联矩阵或邻接矩阵以及 一个简单有向网络的关联矩阵或邻接矩阵，完全反映了该网络的所有信息。因此 可以用矩阵来刻画一个网络。在计算机中贮存一个网络时，最常用的是邻接矩阵 表示法 3 1 1 。 设网络u 是一个无重边的无向网络，u 的邻接矩阵x ( u ) = ( x i j ) 定义如下： ：p 黑俞嗽脯一条边( 2 - 1 ) l ，一1o ，否则 8复杂网络及其上的病毒传播和演化博弈的研究 由定义，如果【，是一个刀个节点的无向网络，则x ( u ) 是一个以阶的对称方阵，它 的元素只有0 或1 两个值。显然，任何一个满足该性质的矩阵都对应了一个网络。 若将无向网络邻接矩阵第行亍或者第f 列的元素值加起来就得到节点f 的度。 设网络d 是一个无重边的有向网络，d 的邻接矩阵x ( d ) = ( 黾) 定义如下： 再，： 1 ，坦墨亨条边从节点曲发指协( 2 - 2 ) 一10 ，否则 由定义，如果d 是一个含有疗个节点的有向网络，则x ( d ) 是一个甩阶矩阵，它的 每个元素1 表示网络中的一条出边，它不是一个对称矩阵。将第f 行的元素值累加 起来就得到节点f 的出度，将第，列的元素值累加起来就得到节点，的入度。显然， 任何一个满足该性质的矩阵都对应了一个有向网络。图2 1 所示的无向网络u 的 邻接矩阵如式( 2 3 ) 所示： 2 3 4 6 5 x ( u ) = 图2 1 无向网络示意图 2 2 2 网络在计算机中的存储表示法 o1 1o o1 ol 01 0 o o o 11 o o o o o o l0 o o lo o1 0 o ol 10 ( 2 - 3 ) 网络在计算机中的存储表示方法有多种，常用的有邻接矩阵表示法、边列表 示法和邻接表表示法等。 邻接矩阵表示法中矩阵元素的个数取决于网络节点的个数。对于有n 个节点 的网络，设每个元素需要占有一定的存储空间，整个网络需要占有的存储空间为，1 2 乘上每个元素所需的存储空间。当网络规模很大时，需要占有很大的存储空间， 用邻接矩阵法就不合适了。 边列表示法适合于实际网络中边数较少的情况，边列就是一个以边为元素的 数组，数组中记录了边的出节点和入节点，对于无向网络记录的就是一条无向边。 第二章复杂网络的基本概念及其性质 9 这个数组包含有吃个元素即边数，第i 个元素就表示网络的第i 条边，整个网络需 要占有的存储空间为2 吃乘上每个元素所需的存储空间。利用m a t l a b 软件处理网 络时这种方法很方便【3 2 1 。邻接表法适合于实际网络中的边数少于节点个数的情况。 对于无向网络，第i 个元素存储的是与节点i 相关联的边链表的指针，这时的边链 表就是由节点i 的邻接节点构成的链表，显然，无向网络中的同一条边在邻接表中 要出现两次，即分别出现在与该边关联的两个节点的边链表中。由于本文不研究 有向网络，所以对于有向网络的邻接表存储不作介绍。 2 3 复杂网络的基本概念 为了更加方便的研究复杂网络，人们提出了许多概念和方法来刻画复杂网络 结构的统计特性。在这一节，主要介绍网络的几个基本概念，它们是理解复杂网 络的基础。本节内容主要取材于文献【8 ，9 1 。 2 3 1 节点的度和度分布 1 节点的度：某个节点与网络中其他节点的连接数，即 砖= ( 2 4 ) j e n 其中，口。为网络邻接矩阵元。 2 度分布：所有节点的度危的平均值称为网络的平均度，定义为用 表示。 网络中所有节点的度的分布情况用函数p ( k ) 表示，其含义等于在网络中随机选择 一个节点，它的度恰好为七的概率，也等于网络中度数为七的节点的个数占网络节 点总个数的比例。 3 度关联：如果一个度为七的节点与一个度为后的节点相连的几率与七无关， 则说这个网络是不相关联的。在一个无向网络中，度关联用条件概率p ( k 。i 后) 来表 示度为七的节点与度为七。的节点相连的几率，满足归一化条件p ( k 。i k ) = l 。 2 3 2 平均路径长度 网络中的节点f 和节点j 之间的距离吒定义为连接这两个节点的最短路径上 的边数。最短路径在运输网络中显得尤为重要，通常代表从一个地点到另一个地 点的最短传输路径。 在一个网络中，网络中任意两个节点之间的距离的最大值称为网络的直径 l o 复杂网络及其上的病毒传播和演化博弈的研究 ( d i a m e t e 0 ，记为d ，即 d = m a x d o ( 2 - 5 ) 网络的平均路径长度定义为网络中任意两个节点之间的距离的平均值，即 k 丽2 丽善办( 2 - 6 )( + 1 ) 筹9 式( 2 6 ) 中为网络中的节点个数。网络的平均路径长度三也称为网络的特征路径 长度( c h a r a c t e r i s t i cp a t hl e n g t h ) ，它决定网络的尺度效应。 2 3 3 聚类系数 在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种性质就称 为网络的聚类特性。假设网络中节点i 有t 条边将它和其它节点相连，这屯个节点 就称为节点f 的邻居节点。显然，节点珀勺毛个邻居节点之间最多能有七i ( t 一1 ) 2 条 边。节点f 的聚类系数c ，定义为节点f 的七，个邻居节点之间实际存在的边数e 和最 多能有的边数j | ，( t 一1 ) 2 之比，即 c i = 蒜 p 7 ， 整个网络的聚类系数c 就是所有节点的聚类系数的平均值。 c = 二y e( 2 8 ) 7 很明显，0 c l 。c = 0 表示网络中所有的节点均为孤立节点，即和其它节 点都没有连接；c = 1 表示网络是全耦合网络，即每个节点与其它所有节点都有连 接。对于一个由个节点构成的完全随机的网络，当很大时，c = o ( n _ ) ，这 与大部分真实网络的聚类系数相比是很小的。研究者已经发现大部分的真实网络 都有明显的聚类效应，尽管它们的聚类系数远小于1 ( 并非全耦合的) ，但却比 o ( n - 1 ) 要大得多。事实上，在很多网络中，你朋友的朋友也是你的朋友的概率会 随着网络规模的增大而趋于某个大于零的常数，即当哼0 0 时，c = d ( 1 ) 。这说 明大部分的真实网络既不是完全随机网络，也不是完全耦合网络，而是在某种程 度上具有人们常说的“物以类聚，人以群分 的特性。 2 4 复杂网络的基本特性 2 4 1 小世界特性 在第一章我们介绍了“六度分离”这个现象，1 9 9 8 年科学家w a t t s 和s t r o g a t z 第二章复杂网络的基本概念及其性质 通过建立相应的网络模型来研究“六度分离 现象，这就是小世界网络。将社会 中的个人抽象为网络的节点，将人与人之间的关系抽象为网络的边，就将整个社 会与一个网络对应了起来。社会中人与人之间的平均距离就体现为网络的平均路 径长度，在网络理论中将其定义为节点之间最短距离的平均值。通过对社会网络 的研究发现，尽管网络很大，但每对节点之间还是有相对较短的路径，这个性质 被称为小世界性质。 2 4 2 无标度特性 传统的随机网络，尽管连接是随机设置的，但大部分节点的连接数会大致相 同，即节点的分布方式遵循钟形的泊松分布，有一个特征性的平均数，连接数比 平均数高很多或低很多的节点都极少，如图2 2 ( a ) 所示。 1 9 9 9 年科学家b a r a b d s i 和a l b e r t 开展一项描绘万维网的研究【5 】。他们原本以为会 发现一个随机网络的钟形图，但结果意外发现：万维网基本上是由少数高连通性 的页面串连起来的，8 0 以上页面连接数不到4 个，而占有节点总数不到万分之一 的极少数节点却和1 0 0 0 个以上的节点连接。随机网络所具有的“平均数不见了， 于是他们把这种网络称为“无标度网络 ，这种系统的特性是，若将节点连接的分 布取对数画在双对数坐标上，结果成一条直线，遵循幂律分布，如图2 2 ( b ) 所示。 图2 。2p o i s s o n 分布与幂律分布 2 5 复杂网络发展历程 ( b ) 幂律分布 近年来，对复杂网络的研究方兴未艾，人们对存在于不同领域的大量实际网 络的拓扑特性进行了广泛的实证性研究，在此基础上，人们从不同的角度出发提 1 2复杂网络及其上的病毒传播和演化博弈的研究 出了各种各样的网络拓扑结构模型，本节将简单回顾一下复杂网络的发展历程， 并对复杂网络的这些经典模型做出详细的介绍。 2 5 1 规则网络 在很长一段时间里，人们认为真实系统各因素之间的关系可以用一些规则网 络表示等。但是，对于现实世界错综复杂的关系网络，仅仅用规则网络来描述有 很大的局限性。最近邻耦合网络和全局耦合网络是两种最常被研究的规则网络模 型。 1 最近邻耦合网络 如图2 3 所示的是一个最近邻耦合网络模型，它是一个被广泛研究的、稀疏 的规则网络，通常也被称为格子( l a t t i c e ) 。它的每个节点只与周围的少数邻居节点 相连。一个包含n 个节点的最近邻网络，这n 个节点围成一个环，其中每个节点 都与它左右各k 2 个邻居节点相连( k 为偶数) 。我们很容易得到，当n 很大时，最 近邻网络的平均路径也很大。当一时，平均路径也趋于无穷大。 2 全局耦合网络 全局耦合网络模型如图2 4 所示。在该网络中，任意两个点之间都有边直接 相连。因此在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径 长度和最大的聚类系数。虽然全局耦合网络模型反映了许多实际网络具有的聚类 和小世界性质，但该模型作为实际网络的局限性在于：在一个具有n 个节点的网 络中共有n ( n - 1 ) 2 条边，在实际网络中，边都是比较稀疏的，一般网络具有的边 数是n 的数量级而不是2 的数量级。 ” 气，一一功愈、p 2袋螺支 滋筏辽 飞茹匕芦 图2 3 最近邻耦合网络图2 4 全局耦合网络 2 5 2 随机图 1 9 6 0 年，数学家e r d o s 和r 6 n y i 应用概率方法研究图论问题，建立了随机图 的数学理论，提出了著名了e r 模型f 2 ，3 3 1 ，给定n 个节点，每一对节点之间以概率p 相互连接。由上述e r 模型生成的图被称为随机图。e r 随机图有以下三个统计特 征量： 第二章复杂网络的基本概念及其性质 1 度分布 根据随机图演化过程，每个点与其它点的连接数都是等概率的。 的度分布p ( 1 ( ) 服从二项分别b ( n l ，p ) ，即 p ( k ) = c 嘉p ( 1 一p ) 肛七 当充分大时，式( 2 9 ) 可改写为 尸( 忌) ：p p n ( p n ) k ：口一d 型 因此随机图 ( 2 - 9 ) ( 2 - 1 0 ) 其中，平均度( k ) = p ( n 1 ) = u p 。因此，e r 随机图也称为“p o i s s o n 随机图 。 2 平均路径长度 随机图的平均路径长度有如下估计式： 三删士鍪( 2 - 1 1 ) i n 所以，相对于图的规模n ，随机图的平均路径长度是很小的，呈对数增长。 3 聚类系数 考察随机图中的一个节点和它的邻点，任意两个邻居节点之间存在连接的概 率总是连接概率p 。因此，随机图的聚类系数为 c _ p = 字1 ( 2 - 1 2 ) 显然，c 随着n 无限增大而趋于零，表明随机图并不能反映现实网络的聚类特性。 2 5 3 小世界网络 规则的最近邻耦合网络具有高聚类特性，但是平均路径很大，不具有小世界 特性，而e r 随机图虽然具有小的平均路径长度但是却没有高聚类特性，因此对于 现实中的网络，这些模型都不能很好的再现。现实世界里，人们不仅有“近在眼 前 的朋友，也可能会有“远在天边”的亲人，而万维网上面的网页并不是像e r 随机图那样