（理论物理专业论文）混沌理论在复杂网络研究中的应用.pdf

大连理工大学硕士学位论文 摘要 在自然界和人类社会中，复杂网络的影响无处不在。正是由于复杂网络的这种实际 背景和进行研究所具有的现实意义，这类研究得以广泛展开。本文利用非线性动力学中 的混沌理论和统计物理学等理论，采用计算机数值模拟的方法对复杂网络的破坏进行了 深入的探索。 本文所研究的对复杂网络的破坏是指采用直接攻击的方式，这种攻击方法直接切断 网络中被攻击的节点与其他节点相连的边，使其变成完全孤立的节点，进而研究网络的 破坏程度。但是，之前的研究都是在完全了解网络拓扑结构的基础上进行的。我们应用 混沌理论，减少了以往进行复杂网络破坏所依赖的前提条件。通过在已有的网络模型上 进行模拟计算，与理想情况对比后发现，我们的方法在没有预先了解网络结构的情况下， 仍然能够取得非常好的破坏效果。 本论文主要分为三部分内容。首先，介绍复杂网络的一些基本概念，如网络中度、 平均最短路径的概念以及聚集系数等。引出三种重要的网络模型，如随机网络，小世界 网络和无标度网络。这些网络模型都为接下来的研究作了理论铺垫。 其次，在介绍了基本的复杂网络理论知识之后，本文进一步介绍了复杂网络上动力 学行为研究的一个分支复杂网络的破坏。介绍了进行破坏的主要方式，一是直接攻击； 二是利用级联效应。并且给出了评估复杂网络破坏程度的两个参数：平均最短路径和最 大子网络的相对大小。 最后，我们在无标度网络上，分别选取三种攻击方式进行对比：( 1 ) 随机故障， 即被去除的节点是随机选择的；( 2 ) 蓄意攻击，即在完全了解网络拓扑结构的情况下， 去除最大程度影响网络结构的那些节点；( 3 ) 我们的攻击方法，即在没有预先掌握网 络拓扑结构的情况下，应用我们的方法去除部分节点。进行计算机模拟后发现，我们的 方法对复杂网络攻击后的结果非常接近蓄意攻击的结果，而且进行深入的研究后，我们 的方法对干扰具有很强的鲁棒性。 关键词：复杂网络；攻击；混沌理论 混沌理论在复杂网络研究中的应用 a p p l i c a t i o no fc h a o st h e o r yt ot h er e s e a r c h e so nc o m p l e xn e t w o r k s a b s t r a c t i nt h en a t u r ea n ds o c i e t y ，c o m p l e xn e t w o r k se x i s te v e r y w h e r e ，s u c ha si n t e r n e t ，w w w ， b i o l o g i c a ln e t w o r k ，t r a n s p o r t sn e t w o r ka n d c o m m u n i c a t i o nn e t w o r k f o rt h i sl ( i 1 1 do fr e a l i s t i c c o n d i t i o n ，m u c ha t t e n t i o nh a sb e e na t t r a c t e d i nt h i sa r t i c l e ，w ea p p l y t h et h e o r yo fc h a o sa n d s t a t i s t i c a lm e c h a n i s mt od e e p l ys t u d yd a m a g et oc o m p l e xn e t w o r k sb ym e a n so fm c s i m u l a t i o n 。 i nt h i sa r t i c l e ，t h es t u d yo fd a m a g et oc o m p l e xn e t w o r k sm a i n l yf o c u s e so nt h em e t h o d o fa t t a c kw h i c hm e a n st oc u to f fa l ll i n k sb e t w e e nt h er e m o v a ln o d ea n do t h e rn o d e si n c o m p l e xn e t w o r k s h o w e v e r , t h es t u d i e sa h e a da r em o s t l yb a s e do nac o m p l e t ek n o w l e d g e a b o u tt h en e t w o r kt o p o l o g y h e r e ，w ep r o p o s eam e t h o dw h i c ha p p l i e st h et h e o r yo fc h a o st o t a k ee f f e c t i v ea t t a c kw i t h o u ta n yp r i o ri n f o r m a t i o no ft h en e t w o r kt o p o l o g y b yc o m p a r i s o n w i t l li d e a li n t e n t i o n a la t t a c ki ns c a l e f r e en e t w o r k w ef i n dt h a to u rm e t h o di sv e r ye f f e c t i v e t h e r ea r em a i n l yt h r e ep a r t si nt h ea r t i c l e f i r s t ，w ed i s c u s ss o m ef u n d a m e n t a lc o n c e p t s i nc o m p l e xn e t w o r k s ，s u c ha sd e g r e ea n dd e g r e ed i s t r i b u t i o n ，a v e r a g es h o r t e s t p a t ha n d c l u s t e r i n gc o e f f i c i e n t a f t e rt h a t ，w ep r o p o s ew h a tt h ec r i t e r i o ni si nd i f f e r e n tn e t w o r k s ， r a n d o mn e t w o r k ，s m a l l w o r l dn e t w o r ka n ds c a l e f r e en e t w o r kf o re x a m p l e t h e s en e t w o r k m o d e l sp r o v i d ei m p o r t a n tb a s i ct h e o r yf o rs t u d i e s t h e n , w ed e e p l yd i s c u s so n ea s p e c to fd y n a m i c a lc o m p l e xn e t w o r k sa n dt h a ti sd a m a g e t oc o m p l e xn e t w o r k s t h e r ea r et w ok i n d so fd a m a g e ，o n ei sa t t a c ka n dt h eo t h e ri sc a s c a d e b r e a k d o w n a n dt h et w op a r a m e t e r sw h i c hc a nb eu s e dt oe s t i m a t et h ed a m a g ea r ea v e r a g e s h o r t e s tp a t ha n dt h er e l a t i v es i z eo ft h el a r g e s ts u b - n e t w o r k l a s t ，i ns c a l e - f r e en e t w o r k ，t h ef o l l o w i n gt h r e ea t t a c k sa l ec o n s i d e r e da n dc o m p a r e d ，( 1 ) r a n d o ma t t a c k ，t h en o d e sa r er a n d o m l ys e l e c t e da n d r e m o v e d ；( 2 ) i d e a li n t e n t i o n a la t t a c k ，t h e n o d e s 谢t l lt h el a r g e s td e g r e ea r es e l e c t e da n d r e m o v e d ；( 3 ) o u rm e t h o da t t a c k ，t h en o d e sf o u n d b yo u rm e t h o da r es e l e c t e da n dr e m o v e d a f t e rm cs i m u l a t i o n ，w ef i n dt h a te v e nw i t h o u ta n y p r i o ri n f o r m a t i o no ft h en e t w o r kt o p o l o g y , o u rm e t h o di sv e r ye f f e c t i v ea n dr o b u s ta g a i n s t d i s t u r b s k e yw o r d s ：c o m p t e xn e t w o r k s ；a t t a c k s ；c h a o s i i 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 1绪论 1 1 引言 在自然界和人类社会中，很多可以例比于二维网络的复杂系统有着非常重要的作 用，例如i n t e m e t 、w w w 、生物网络、通讯网络、公路交通网、航空网络、电力网络、 病毒传播网络等。我们生活在一个网络无处不在的世界中，而这些网络在为我们的生活 提供便利的同时，也存在不利的方面，如信息网络的安全、交通网络的拥堵、电力网络 的稳定，因此研究复杂网络具有重大的现实意义。 复杂网络是具有复杂拓扑结构和动力行为的大规模网络，它是由大量的节点通 过边的相互连接而构成的。复杂网络的节点可以是一个个体，也可以是任意具 有特定动力学和信息内涵的系统的基本单位，而边则表示他们之间的关系或联系。 因此，对于一个复杂网络的研究就是把网络中的节点和连接节点的边作为对象，利用统 计力学的知识和计算机的技术，探索其理论模型，研究其动力学行为，进而深入的理解 复杂网络，使其更好的服务于人类社会。例如，在充分理解复杂网络的拓扑特征以及动 力学模型的基础上，我们就可以掌握病毒在网络中的传播规律，从而更好的预防病毒的 传播；我们也可以大大提高网络的容量，从而节省了有限的资源；我们还可以使我们的 网络变得更通畅，有利于信息的流动，提高网络的运行效率。总之，深入研究复杂网络， 对于我们理解身边的一些奇特的现象具有极大的启示作用，合理的利用之后，必将为我 们提供更大的便利。 1 2 复杂网络研究的方法 1 2 1 经典模型的建立 自从复杂网络受到广泛关注以来，研究人员通过对复杂网络的拓扑结构的研究，给 出了描述三个基本网络随机网络、小世界网络和无标度网络的模型，即随机网络模型 ( 3 l 称e r 模型) 【1 】、小世界网络模型( 又称w s 模型) 【2 】和无标度网络模型( 又称b a 模型) 【3 】。 2 0 世纪6 0 年代以来，e r d s s 和r 6 n y i 建立的随机图理论在将近4 0 年的时间里一直 是研究复杂网络结构的基本理论，他们所提出的随机模型开创了复杂网络理论的系统性 研究，但事实上，绝大多数复杂网络的结构并不是完全随机的，例如，i n t e m e t 的任意 两个路由器之间是否有光纤连接，w w w 中两个页面之间是否有超文本链接等都不是靠 抛硬币来决定的。 混沌理论在复杂网络研究中的应用 随着研究的不断深入，有两篇开创性的文章揭示了复杂网络的基本特性：一篇是 w a t t s 博士及其导师s t r o g a t z 教授于1 9 9 8 年6 月在n a t u r e 杂志上发表的题为“小世界 网络的集体动力学的文章；另外一篇是b a r a b d s i 教授及其博士生a l b e r t 于1 9 9 9 年1 0 月在s c i e n c e 杂志上发表的题为随机网络中标度的涌现的文章。这两篇文章分别揭 示了复杂网络的小世界特征和无标度的性质，并建立了相应的模型，即小世界网络模型 和无标度网络模型。 这三种模型的构造及其应用将在第二章中做详细阐述，以上理论模型的建立，为我 们对复杂网络进行系统性研究建立了基础。 1 2 2 混沌理论的应用 著名的物理学家霍金在二十世纪末曾说过“二十一世纪是复杂性的世纪”，复杂性 科学以复杂系统为研究对象，包括非线性动力学和复杂网络两方面，其中非线性动力学 为复杂性研究提供有效的理论工具，而复杂网络为复杂性研究提供了良好的数学模型， 经过几十年的发展，这两方面的研究都取得了很多重要的成果，为我们更深入的研究复 杂系统奠定了坚实的基础。 目前针对复杂网络的研究都是基于一令前提条件，即研究人员完全清楚该网络的拓 扑结构。但是在现实生活中，当我们要对一个陌生的网络进行研究时，这个前提条件是 不存在的。混沌理论的应用为我们提供了一种方法，可以间接的掌握到复杂网络拓扑结 构的一些信息，从而消除了对一个陌生的复杂网络进行深入研究的障碍。 1 3 我们的工作 网络的破坏是复杂网络的动力学行为研究中非常重要的一部分，主要分两种情况， 一种是随机故障【4 】，诸如i n t e r n e t 中的服务器，在其正常运行的过程中难免会出现运行 不畅，甚至不工作的情况，从而影响到整个网络的运行，因为其发生具有一定的随机性， 所以我们称之为随机故障；另一种是蓄意攻击【4 _ 1 ，由于在这种情况下，目的性强，目 标明确，往往能够造成菲常严重的破坏，甚至出现网络瘫痪的状况。当然，在蓄意攻击 时要想达到这样的效果需要一个前提条件，即完全了解目标网络的拓扑结构，但是在现 实生活中，当我们要对一个陌生的复杂网络进行蓄意攻击时，这个前提条件是不存在的， 网络中非常重要的部分很少，而且不易被发现，在随机的选取部分目标攻击后，不会有 很好的结果产生。 大连理工大学硕士学位论文 混沌理论的应用为我们提供了一种有效的方法，可以利用其他工具间接的掌握到复 杂网络拓扑结构的一些基本信息，如节点的度分布，这为我们找到网络中那些重要的节 点提供了有效的途径，在这种情况下进行蓄意攻击就会产生非常理想的效果。 混沌理论在复杂网络研究中的应用 2 复杂网络的基本要素和模型 2 1 复杂网络的基本要素 通过系统的研究，人们主要用以下三个要素来描述复杂网络拓扑结构的统计性 质：度以及度分度( d e g r e ea n dd e g r e ed i s t r i b u t i o n ) 、平均最短路径长度( a v e r a g es h o r t e s t p a t h ) 、聚类系数( c l u s t e r i n gt o e 伍c i e n t ) 。 2 l 1 度以及度分布 度( d e g r e e ) 是单独节点的属性中简单而又重要的概念。节点f 的度矗定义为与该节 点所连接的边的数目。直观上看，一个节点的度越大就意味着这个节点在某种意义上越 “重要 。网络中所有节点的度的平均值称为网络的平均度，记为( k ) ，由于一条边对 度的贡献为2 ，所以网络的平均度 ( k ) = 寺尼，= 等 ( 2 1 ) v f v 其中m 和分别表示网络的边数和节点数。 网络中节点的度的分布情况可用分布函数e ( k ) 来描述。p ( k ) 表示的是一个随机选 定的节点的度恰好为k 的概率。规则的格子有着简单的度序列：因为所有的节点具有相 同的度，所以其度分布为d e l t a 分布，它是单个尖峰。网络中的任何随机化倾向都将使 这个尖峰的形状变宽。完全随机网络的度分布近似为p o i s s o n 分布，其形状在远离峰值 ( k ) 处呈指数下降。这意味着当k ( k ) 时，度为k 的节点实际上是不存在的。因此，这 类网络也称为均匀网络( h o m o g e n e o u sn e t w o r k ) 。 近几年的大量研究表明，许多实际网络的度分布明显的不同于p o i s s o n 分布，特别 的，许多网络的度分布可以用幂律形式p ( j j ) o c 后一，来更好的描述。幂律分布曲线比 p o i s s o n 指数分布曲线下降要缓慢得多。 幂律分布也称为无标度( s c a l e f r e e ) 分布，具有幂律度分布的网络也称为无标度网 络，在一个度分布为具有适当幂指数( 通常为2 ，3 ) 的幂律形式的大规模无标度网 络中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点。因此，这类网 络也称为非均匀网络( i r t h o m o g e n e o u sn e t w o r k ) 。 大连理工大学硕士学位论文 2 1 2 平均最短路径长度 复杂网络中两个节点i 和j 之间的距离d ，定义为连接这两个节点的最短路径上的边 数。网络的平均最短路径长度d 定义为任意两个节点之间的距离的平均值，即 肚n ( n 南蔷磊 2 + l 智”私 其中为网络的节点数。网络的平均最短路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理，在公式( 2 2 ) 中包含了节点到自身 的距离( 当然该距离为零) 。如果不考虑节点到自身的距离，那么要在公式( 2 2 ) 的右 端乘以因子( n + i ) ( n 1 ) 。在实际应用中，这么小的差别是完全可以忽略不计的。 图2 1 一个简单网络的直径和平均最短路径长度 f i 醇。2 d i a m e t e ra n dc h a r a c t e r i s t i cp a t hl e n g t ho fas i m p l en e t w o r k 例如，对于图2 1 所示的一个包含5 个节点和5 条边的网络，我们有d = 玩，= 3 ， l = 1 6 。在朋友关系网中，三是连接网络内两个人之间最短关系链中的朋友的平均个数。 近期研究发现，尽管许多实际的复杂网络的节点数巨大，网络的平均路径长度却小的惊 人。具体地说，一个网络称为是具有小世界效应的，如果对于固定的网络节点平均度( k ) ， 平均路径长度三的增加速度至多与网络规模的对数成正比。 2 1 3 聚类系数( 簇系数) 在你的朋友关系网中，你的两个朋友很可能彼此也是朋友，这种属性称为网络的聚 类系数，又称簇系数。一般的，假设网络中的一个节点，有毛条边将它和其他节点相连， 这毛个节点就称为节点f 的邻居。显然，在这毛个节点之间最多可能有七，( 屯一1 ) 2 条边。 而这毛个节点之间实际存在的边数骂和总的可能的边数毛( 局- 1 ) 2 之比就定义为节点i 的聚类系数e ，即 混沌理论在复杂网络研究中的应用 q = 2 e t ( 向- i ) 从几何特点看，上式的一个等价定义为 ( 2 3 ) 与点湘连的三角形的数量，、 - 2 写丽丽哥疆再蕴聪 “一) 其中，与节点，相连的三元组是指包括节点i 的三个节点，并且至少存在从节点i 到 其他两个节点的两条边( 图2 2 ) 图2 2以节点i 为顶点之一的三元组的两种可能形式 f i 簖3 t w of 0 咖o f t r i a n g u l a r 整个网络的聚类系数c 就是所有节点f 的聚类系数c 的平均值。很明显，0 c 1 。 c = 0 当且仅当所有的节点均为孤立节点，即没有任何连接边；c = 1 当且仅当网络是全 局耦合的，即网络中任意两个节点都直接连接。对于一个含有个节点的完全随机的网 络，当很大时，c = o ( n 。11 。而许多大规模的实际网络都具有很明显的聚类效应， 它们的聚类系数尽管远小于1 但却比o ( n 。1 1 要大的许多。事实上，在很多类型的网络 ( 如社会关系网络) 中，你的朋友的朋友同时也是你的朋友的概率会随着网络规模的增 加而趋向于某个非零常数，即当- - o o 时，c = 0 ( 1 l 。这意味着这些实际的复杂网络并 不是完全随机的而是在某种程度上具有类似于社会关系网中“物以类聚，人以群分 的 特性。 2 2 复杂网络的基本模型及其性质 要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需要对实 际网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。在w a t t s 和 s t r o g a t z 关于小世界网络，以及b a r a b a s i 和a t b e r t 关于无标度网络的开创性工作之后， 人们对存在于不同领域的大量实际网络的拓扑特征进行了广泛的实证性研究。在此基础 上，人们从不同的角度出发提出了各种各样的网络拓扑结构模型。2 0 0 3 年以前提出的 大连理工大学硕士学位论文 各种主要模型已有综述【8 。9 】。本章介绍三种基本的模型，包括随机网络模型，小世界网 络模型和无标度网络模型。 2 2 1 随机网络模型 e r d o s 和r e n y i 于4 0 多年前开始研究的随机网络模型【l 】是复杂网络进行系统化研究 的基础，揭示出利用统计力学的方法探索网络的拓扑结构及其对网络性质的影响是一个 非常重要的研究方向，包括之后对复杂网络的动力学行为进行研究时，都是以相应的网 络模型为基础，并且取得了很多重要的科研成果。下面将介绍随机网络模型的相关内容。 假设有大量的纽扣( n 1 ) 散落在地上，并以相同的概率p 给每对纽扣系上一根 线。这样就会得到一个有个点，约p n ( n 一1 ) 2 条边的随机网络的实例( 图2 3 ) 。 b cd 图2 3 随机图的演化示意图( 文献 1 ) f i 醇3 t h es k e t c hm a po fe rn e t w o r k s 随机网络的平均度是( j j ) = p ( n 一1 ) p n 。设三f 詹是随机网络的平均路径长度。直观 上，对于随机网络中随机选取的一个点，网络中大约有( 七) 厶肼个其他的点与该点之间的 距离等于或非常接近于k 。因此，no c ( 后) 垴，即l e r 芘( 1 1 1 忉h 1 ( 尼) 。这种平均路径长 度为网络规模的对数增长函数的特性就是典型的小世界特征。因为1 i l 的值随增长的 很慢，这就使得即使是规模很大的网络也可以具有很小的平均路径长度。 随机网络中两个节点之间不论是否具有共同的邻居节点，其连接概率为p 。因此， 随机网络的簇系数是c = p = ( k ) n 1 ) 。当p 较小时簇系数变化也不大 ( c ( p ) c ( o ) ) ，但其平均路径长度却下降很快( l ( p ) ( k ) 时，度为k 的节点几乎不存在。因此，这类网络也称为均匀网络或指数 网络( e x p o n e n t i a ln e t w o r k ) 。近年在复杂网络研究上的另一重大发现就是许多复杂网络， 包括i n t e m e t 、w w w 以及新陈代谢网络等的连接度分布函数具有幂律形式】。由于这类 网络的节点的度没有明显的特征长度，故称为无标度网络。 为了解释幂律分布的产生机理，b a r a b a s i 和a l b e r t 提出了一个无标度网络模型，又 被称为删模型【3 j 。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重 要特性： 1 ) 增长( g r o w t h ) 特性：即网络的规模是1 i 断扩大的。例如每个月都会有大量的 新的科研文章发表，而w w w 上则每大都有大量的新的网页产生。 2 ) 优先连接( p r e f e r e n t i a la t t a c h m e n t ) 特性：即新的节点吏倾向丁与那些具有较高 连接度的“大”节点相连接。这种现象也称为“富者更富( r i c hg e t r i c h e r ) ” 或“马太效应( m a t t h e we f f e c t ) ”。例如，新发表的文章更倾向于引用一些 已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、 雅虎等著名的站点。 基于网络的增长和优先连接特性，无标度网络模型的构造算法j 如下： 1 ) 增长：从个具有m n 个节点的网络丌始，每次引入一个新的节点，并且连到m 个己存在的节点上，这里m m n 。 2 ) 优先连接：一个新的节点与一个已经存在的节点相连接的概率兀，与节点f 的 度k i 、节点，的度k i 之间满足如下关系： 大连理工大学硕士学位论文 n ，2 丽k i ( 2 6 ) 在经过f 步后，这种算法产生一个有= t + 个节点、聊f 条边的网络。 图2 6 显示了当m = m o = 2 时的无标度网络的演化过程。初始网络有两个节点，每 次新增加的一个节点按优先连接机制与网络中已存在的两个节点相连。7 ， 冀：x 髯：、稳0 番 、 “ x “滔 图2 6 无标度网络的演化( m = m 0 = 2 ) ( 文献 1 2 ) f i 醌6 t h ee v o l v e m e n to f b an e t w o r k s 1 平均路径长度 无标度网络的平均路径长度为： ，1 0 9n 从商 旺7 ) 这表明该网络模型也具有小世界特性。 2 簇系数 无标度网络的簇系数为： c = 掣r h ( 型) 一上 堕监 ( 2 8 ) 4 ( m + 1 ) l 、m 7 m + l j t 这表明与随机网络类似，当网络规模充分大时无标度网络不具有明显的聚类特征。 3 度分布 目前对无标度网络的度分布的理论研究主要有三种方法：连续场理论( c o n t i n u u m t h e o r y ) 【3 】、主方程法和速率方程法。这三种方法得到的渐近结果都是相同的。其中， 主方程法和速率方程法是等价的。下面介绍由主方程法得到的结果。 ! ? ! l 净1 ： 十t ， ， 缔、， 。o 糖矿 。晨鼍滏 混沌理论在复杂网络研究中的应用 g s l p ( k ，t ，f ) 为征幺时刻加八阴币点z 征f 时刻的度恰好是尼阴楸翠。在尢杯发网 络模型中，当一个新节点加入到系统中来时，节点f 的度增加l 的概率为所n ，= ， 否则该节点的度保持不变。由此得到如下递推关系式 赢+ 1 ) = 等m 毗卅( ，一丢) 包9 ， 而网络的度分布为 p ( 七) = l 。，i m 。( f l - z p ( 七，f ) j 2 1 。) 她，= 譬旷1 ) ， 【垅+ 2 七耽+ 1 后= m ( 2 1 1 ) m _ 揣砌2 ( 2 1 2 ) 这表明无标度网络的度分布函数可用幂指数为3 的幂律函数近似描述。 大连理工大学硕士学位论文 3 复杂网络的破坏 现在假设给定一个网络，每次从该网络中移走一个节点，这也就同时移走了与该节 点相连的所有的边，从而有可能使得网络中其他节点之间的一些路径中断。如果在节点 f 和节点歹之间有多条路径，中断其中的一些路径就可能会使这两个节点之间的距离办 增大，从而整个网络的平均路径长度三也会增大。而如果节点f 和歹之间的所有路径都 被中断，那么这两个节点之间就不再连通了，如图3 1 所演示的过程。 图3 1 去除节点对网络的破坏( 文献 1 2 ) f i 9 3 1d a m a g e db yn o d ew i p e do f f 3 1 复杂网络的直接破坏 2 0 0 0 年8 月，发表于n a t u r e 杂志的文章 e r r o ra n da t t a c kt o l e r a n c eo fc o m p l e x n e t w o r k s ) ) 开创了复杂网络破坏方面的研究 4 1 。如果复杂网络抗破坏的能力比较强，那 混沌理论在复杂网络研究中的应用 么我们就称该网络具有比较强的鲁棒性。该文分别在随机网络和无标度网络中，探讨了 两种节点去除的方式：一是随机故障，即完全随机的去除网络中的一部分节点；二是蓄 意攻击，即从网络中度最高的节点开始，有意识的去除一部分度最高的节点。假设去除 的节点数占原始网络总节点数的比例为，可以用最大连通子网络的相对大小s 和网络 的平均最短路径长度三与厂的关系来度量以上两种方式对网络的破坏程度，其中最大连 通子网络的相对大小s 为 s _ - 等 ， 其中表示网络受到破坏后其最大连通子网络的节点数，表示初始整个网络的 节点数。研究发现，随机网络和无标度网络之间存在极其显著的差异。无标度网络在随 机节点故障的情况下，受到的破坏很小，与随机网络相比，最大连通子网络的相对大小 在相对高得多的厂时才下降到零( 图3 2 ) 【4 】，而其平均最短路径长度的增长则要缓匣得 多( 图3 4 ) 4 1 。无标度网络对随机故障的这种特性，来自于网络度分布的极端非均匀性： 绝大多数节点的度都相对很小，而有少量节点的度相对很大。当厂较小时，随机选取的 节点都是度很小的节点，除掉这些节点对整个网络的连通性不会产生很大的影响。然而， 正是这种非均匀性使得无标度网络在蓄意攻击的情况下更容易受到破坏：只要有意识的 去除网络中极少量度最大的节点就会对整个网络的连通性产生很大的破坏( 图3 2 ) 。 图3 3 【1 2 】形象的比较了随机网络和无标度网络的受破坏情况。从图3 3 中可以看到，即 使随机去除网络中的大量节点，无标度网络仍可保持基本的连通性，而随机去除同样多 的节点，则可使一个同样规模的随机网络分成多个孤立的子网络；但蓄意去除少量度最 大的节点就很容易破坏无标度网络的连通性。 大连理工大学硕士学位论文 磊 铬 ， 图3 2 几种网络的破坏程度( 文献 4 ) f i 9 3 2d e s t r o yo fs e v e r a ln e t w o r k s 以i n t e m e t 为例，i n t e m e t 的前身是2 0 世纪6 0 年代后期由美国国防部高级研究计划 署( c ! 心a ) 研制的a r p a n e t 。其主要目的之一，就是为了使得在一些子网络和网关 发生故障的情况下，网络还能维持基本的通信工作。如今i n t e r n e t 已经发展成为一个规 模巨大的网络，并在人类社会生活中起着越来越重要的作用。而i n t e m e t 上每天都在发 生各种各样的故障并经常受到黑客的攻击【1 3 1 。在这种情况下，i n t e m e t 是否能保持它的 功能无疑是一个重要的课题。 混沌理论在复杂网络研究中的应用 憨巍暾绻巷虑意外故障 茺尺寝嬲络第意纛外故豫 | 、7 、0 图3 3 随机网络和无标度网络的比较( 文献 1 2 ) f i 醇3 t h ed i f f e r e n c eb e t w e e ne ra n ds fn e t w o r k s a l b e r t 、j e o n g 和b a r a b a s i 在文献( ( e r r o ra n da t t a c kt o l e r a n c eo fc o m p l e xn e t w o r k s ) ) h 中研究了两个实际网络被随机故障和蓄意攻击的破坏情况：一个是含有6 0 0 0 个节点的 i n t e m e t 结构图，另一个是含有3 2 6 0 0 0 个网页的w w w 子网。他们得到了与无标度网络 相类似的结果( 图3 4 ) ，从而进一步验证了对随机故障的鲁棒性和对蓄意攻击的脆弱 性是无标度网络的一个基本特征，并且指出其根源在于无标度网络中的度分布不均匀性 i l3 1 。事实上，近些年不同领域科学家的研究表明，“鲁棒但又脆弱( r o b u s t y e tf r a g i l e ) ” 是复杂系统的最重要和最基本的特征之一。例如，在设计航天飞机的时候，人们考虑到 彩。一 大连理工大学硕士学位论文 了各种能够想到的可能干扰因素，航天飞机的飞行对这些干扰因素具有极高的鲁棒性， 但是还是有可能存在个别意想不到的干扰，并且航天飞机对这些干扰可能是极端脆弱 的，哥伦比亚号和挑战者号失事的灾难就是佐证【1 2 1 。 f 图3 4i n t e r n e t 和w w w 对随机故障的鲁棒性和蓄意攻击的脆弱性( 文献 4 ) f i 驴4 r o b u s ta n df r a g i l eo fi n t e m e ta n dw w wn e t w o r k s b r o d e r 等人研究了更大规模w w w 子网络的受到不同程度破坏的情况【1 4 1 。他们发 现只有删除所有度大于5 的节点才能完全破坏w w w 的连通性；由于有些节点的度高 达几千，这就意味着要对整个网络实施猛烈的攻击。因此，他们认为该网络对蓄意攻击 也具有很高的鲁棒性。初看起来，这与a l b e r t 等人的结论似乎是矛盾的。其实不然，因 为w w w 具有高度倾斜的度分布，所以度数大于5 的节点在整个网络中所占的比例还 是很小的。 混沌理论在复杂网络研究中的应用 3 2 复杂网络在级联效应下的破坏 复杂网络的构成元素，节点和边，有时候会包含一些动力学信息，比如i n t e m e t 要 传输数据包，电力网要传输电流，地面交通网要传输车流量等。复杂网络所要传输的这 些内容统称为负载( 用三表示) ，与此同时，由于地理环境、费用等因素的制约，节点 或边传输负载的能力并不是无限大的，而是会预先设定一个值，表示所能承受的最大负 载，称之为容量( 用c 表示) 。在网络正常工作的情况下，节点j 的容量。正l t , 于它的 负载可【5 】， c - ，= ( 1 + 口) 三， ( 3 2 ) 其中口是一个大于0 的参数，称为容忍参数。 当由于某种原因某个节点的负载超过其容量从而产生故障时，就把该节点的负载按 照一定的策略分配给网络中其他的节点。这些节点接受了额外的负载，其总负载也有可 能超过其容量，从而导致新一轮的负载重新分配，这样的过程我们称之为级联效应。如 果这个过程反复进行，造成大面积扩散，就会对网络产生破坏，甚至达到崩溃的程度。 例如，2 0 0 3 年8 月，由美国俄亥俄州克利夫兰市的3 条超高压输电线路相继过载烧断引 起的北美大停电事故，使得数千万人时陷入黑暗，经济损失估计高达数百万美元【1 2 1 。 3 2 1 节点承载负载的动态模型 m o t t e r 等人给出了一个以节点为负载承载体，在级联效应下研究网络破坏的模型【5 】o 对于一个给定的具有个节点的复杂网络，假设信息或能量在节点之间沿着最短路径传 输，那么节点的负载定义为网络中通过该节点的最短路径的数目。当网络中的某个或一 小部分节点发生故障时，可以认为它脱离了网络变成孤立节点，这样会导致整个网络中 最短路径的分布发生了变化，从而使每个节点的负载也相应的产生变化。当任一节点的 负载超过其容量时，它自身就会发生故障，从而引发新一轮的负载重新分布。如果网络 中负载的分布是非均匀的，而且被去掉的节点的负载较大，就会导致级联效应的发生。 用最大连通子网络的相对大小g 来表示整个网络的连通性，g 值越接近1 ，说明连 通性越好。对于按照文献【1 6 】中的程序产生的无标度网络，上述模型进行模拟后发现，如 果最初去除的节点是随机选择的，那么网络的连通性几乎没有变化( g 1 ) ；但是， 如果去除的是度最大或负载最大的节点，g 的值会大大的减小，即使容忍参数口= 1 ， 也就是节点能承受比初始负载大一倍的负载，网络上的连通性也会下降2 0 。图3 5 【5 j 中的三条曲线分别表示去除的节点是随机选择的( 方格) 、度最大的( 星号) 和负载最 大的( 圆圈) 。因为无标度网络中度和负载比较小的节点占大多数，所以随机故障大多 大连理工大学硕士学位论文 发生在这些节点身上，对整个网络的破坏也就比较小。由于度或负载最大的节点对于维 持网络的拓扑结构和功能起着至关重要的作用，因此蓄意攻击会主要针对这些节点，从 3 5 图中也可以看出，无标度网络在蓄意攻击的情况下，容忍参数口值越小，网络的连 通性受到的破坏越大。 g 图3 5 无标度网络在分别按照随机去除节点、去除度最大的节点和去除负载最大的节点三种 情况下，网络受到破坏的程度( 文献 5 ) f i 酪5d a m a g eo f t h es c a l e f r e en e t w o r ku n d e rt h et h r e ed i f f e r e n tr e m o v a lo f n o d e s 在本文3 1 节中，我们曾提到，随机网络，即度分布比较均匀的网络，在直接攻击 的两种方式下，都具有很强的鲁棒性，但是像这种度分布均匀，而负载分布非常不均匀 的复杂网络，在攻击负载最大的那些节点时，是否会产生级联崩溃呢? 文献【5 l 对美国西 部电力网络【l7 j 的模拟结果给出了答案，在美国西部电力网络中，对具有最大负载的节点 攻击后，会造成网络的连通性降低5 0 ，但是随机故障和基于度最大的蓄意攻击却不易 产生大规模的破坏，如图3 6 【5 】所示，这正体现出级联效应所能产生的巨大破坏力。 混沌理论在复杂网络研究中的应用 图3 6 美国西部电力网络在分别按照随机去除节点、去除度最大的节点和去除负载最大的节点 三种情况下，网络受到破坏的程度( 文献 5 ) f i 9 3 6d a m a g eo f t h ew e s t e mu s p o w e rt r a n s m i s s i o ng r i du n d e rt h et h r e ed i f f e r e n tr e m o v a lo f n o d e s 3 2 2 边承载负载的动忑模型 在3 2 1 小节中介绍的模型只考虑节点的动态行为，复杂网络的另一构成一边却没 有考虑，实际网络中在各节点之间起连接和传输作用的边同样非常重要。m o r e n o 等人研 究了无标度网络中由于边的拥堵所引发的级联效应口1 。他们给连接节点z ，的边赋予了负 载z u ( ( o ( z ) 。时，网络 、，c 、，c 会以一定的概率处于拥堵状态；当( z ) ( z ) 。o 8 2 时，任何不稳定性都会导致整个网络 、，c 中所有的边都处于拥堵状态。图3 7 n 3 给出了网络中存在最大连通子网络的概率p 与 网络平均负载( ，) 的关系。图中三条曲线分别对应三种负载分配策略：( a ) 随机分配负 载或丢弃；( b ) 随机分配或者全局分配；( c ) 平均分配或者全局分配。 趣 ( ) 图3 7 无标度网络中存在最大连通子网络的概率p g 与网络平均负载( z ) 的关系( 文献 7 ) f i 9 3 7e x i s t e n c eo f t h eb i g g e s ts u bn e t w o r ka c c o r d i n gt ot h ea v e r a g el o a di nt h es c a l e - f r e en e t w o r k 混沌理论在复杂网络研究中的应用 4 混沌理论 非线性科学是一门研究非线性现象共性的基础科学。它是2 0 世纪6 0 年代以来，在 各门以非线性为特征的分支学科的基础上逐步发展起来的综合性学科，被誉为2 0 世纪 自然科学的“第三次革命 。在非线性科学的研究中，已涉及对确定性与随机性，有序 与无序，偶然性与必然性，量交与质变，整体与局部等范畴和概念的重新认识，它将深 刻的影响人类的思维方法，并涉及现代科学的逻辑体系的根本性问题。一般认为非线性 科学的主体包括：混沌、分形、孤子。由于混沌现象