（理论物理专业论文）遭袭复杂网络的修复策略与关联特征研究.pdf

博士学位论文 d o c t o r a ld 塔s e i 玎盯幻n 摘要 本文主要研究了复杂网络在遭袭事件下的修复策略和关联特征，并对美国航空网 络的拓扑结构作了实证研究，同时运用计算机模拟，研究了美国航空网络在“出错” 和“遭袭”两种突发事件下的应变能力。 “出错”和“遭袭”是通过计算机模拟，用来研究复杂网络自身演化的动力学机 制的两种常用策略。“出错”的模拟是指随机地删除复杂网络中的一些结点或连线； “遭袭”的模拟则是指有目的地删除复杂网络中的一类结点或连线，比如删除网络中 连接度非常大的结点。 我们首次提出了复杂网络在遭袭事件下的修复策略。研究了e r d 6 s _ r 6 n y i 随机网 络、w a t t s s t r o g a t z 小世界网络、b a r a b 矗s i a l b e r t 无标度网络在这种修复策略下的稳 定性、关联特征、以及在修复前后这三种复杂网络的拓扑结构变化。 我们提出了一个新的概念：抗毁性j ( 8 ) 。抗毁性j ( s ) 反映了复杂网络对攻击事件 的承受能力。，( s ) 为阶梯式递增函数，在经过长时间的演化后，最终会出现一个稳定 值厶，系统达到稳定状态。在稳定状态，l 的值是系统中最大的。j ( s ) 的逐渐增大表 明系统在遭袭事件和修复策略的共同演化过程中，变得越来越不容易受到攻击，越来 越安全。另一方面，稳定状态的最大连接度( k 。：) 。是系统中最小的。换句话说，系统 在演化中的任一时刻，其最大连接度都不会小于( k 。) 。 对随机网络，在稳定状态下，稳定值厶与网络的大小、连接几率p 都没有关 系，而只与随机网络的平均连接度( ) = p 有关，且为幂次关系。另外，稳定值厶与 修复几率p ，。也呈现幂律关系，在相同的修复几率下，幂指数r 与系统大小有关， 并随着系统大小的增大而逐渐减小。 无标度网络的连接度分布为幂律分布，其拓扑结构与指数型连接度分布的随机网 络完全不同。稳定状态下的无标度网络，在相同系统人小和修复几率下，其稳定值厶 略大于随机网络，相应地，最大连接度( ) 。则略小于随机网络的。另一方面，无标 度网络的稳定值厶与修复几率p r 。也有幂律关系。在相同的系统大小下，修复几率越 大，稳定值就越小；在相同的修复几率下，系统大小越大，稳定值反而越小。 我们电简单地研究了小世界网络的抗毁性，( s ) ，发现小世界网络的抗毁性，( s ) 最 博士学位论文 d o c t o r a l d i s s e r i j 奸l o n 终也可以到达稳定状态下的l 。 通过对比随机网络和无标度网络在初始状态和稳定状态下的拓扑结构变化，研究 了修复策略对这两种具有完全不同拓扑结构的网络的影响。研究发现，稳定状态下的 随机网络变成了一个高度小集团化的网络，而无标度网络的“两极分化”则更加严 重：少数结点占有系统中更多的连线数目，大多数结点则只拥有系统中更少的连线数 目。 研究发现修复策略的引入不仅使复杂网络在经历长时间的演化之后，可以达到稳 定状态，同时还大大增强了复杂网络抵抗持续攻击的能力，提高了复杂网络的抗攻击 能力。 用去趋势涨落分析方法分析了随机网络和无标度网络的关联特征。 代表复杂网络局域特征量的最大连接度自。通过其序列的d f a 分析，发现随机 网络和无标度网络的。序列在小的时问观察尺度内是完全随机的，而在非常大的时 间观察尺度内呈现很强的负关联。 代表复杂网络整体特征量的平均连接度( ) ，通过其序列的d 队分析，发现随机网 络的( ) 序列在整个时间尺度内呈现长程幂律关联；无标度网络的( ) 序列在小的时间 观察尺度内毫无关联，在大的时间尺度上呈现负关联，负关联会| 3 直着修复几率的增加 而增强。 通过对美国航空网络的实际数据分析，发现美国航空网络具有小世界网络的特 征，即大的聚集系数和小的平均最短路径。但是，美国航空网络的连接度分布却呈现 两段幂律分布，与小世界网络的指数型连接度分布不同。 另一方面，通过计算机对美国航空网络的出错和遭袭两种突发事件的模拟发现， 美国航空网络的容错能力很强，抗攻击能力却很差，具有无标度网络的鲁棒性特征。 本文还对目前复杂网络的模型机制、动力学研究和应用研究作了简单回顾和综 述。 关键词：复杂网络、出错、遭袭、稳定性、去趋势涨落分析方法、关联特征、拓扑结 构、鲁棒性。 博士学位论文 d o c r a l d 疆s 日 a t f 0 n a b s t r a c t t h i sd i s 8 e r t a 七i o nj 8c o c e r n e dw i t ht h es t u d yo ft h er e p a i rs t r a t e g ya n dc o r r e l a t i o n p r o p e r t i e 8o fc o m p l e xn e t w o r k 8u n d e ra 饥a c l ( 8 ；w i t ht h es t u d yo ft o p o l o g i c a lp r o p e r t i e s o fu sa j r p o r tn e t w o r k 锄dt h er e 8 i l j e n c eu n d e re r r o r sa n da t t a c k s e r r o r s ”a n d a 乞t a c k s a r et w os i m u i a t i o ns t r a t e g i e 8t oi n v e s t i g a t et h ed y n a m i c so f c o m p l e xn e t w o r k s e r r o r i ss i m u l a t e da 8t h ed e l e t i o no fn e t w o r kn o d e 8o r1 i n k sc h 0 8 e n a tr n d o m ，w h i l ei n t e n t i o n da t t a c ka st a r g e t e dr e m d v a lo fas p e c i 6 cc l 明so fn o d c so r l j n k s ，s u c ha sn o d e 8w i t hh i g h e s td e g r e e 8 w ep r o p o s ear e p a i r8 t r a 土e g yo fc o m p l e xn e t w o r k su n d e rt h ea t t a c k sw i t ht h e r e p a i r8 t r a t e 觚w es t u d y h es t a b i l i 乞ya n dc o r r e i a j o np r o p e r 鼬so fe r d 6 础咖r a n d 。m g r a p h s ，w a t 七s s t r o g a t zs m “l _ w o r l dn e t w o r k 8a n db a r a b 直s i a l b e r ts c a l e f r e en e t w o t k 8 ， e s p e c i a j l yt h ec o r r e s p o n d i n gt o p o i o g i c a lc h a n g e so ft h e 8 et h r e ec o m p i e xn e t w o r k s an e wq u a l i t y ，i n v l l l n e r a b i l t y ( s ) i si n t r o d u c e d f ( s ) r e f l e c t st h et o l e r a n c eo f c o m p l e xn e t w o r k su n d e ra t t a c k s f ( s ) i s a8 t e p w i s en o n _ d e c r e a s i n gf u n c t i o na n dr e a c h e 8 ac o n s t a n tv a i u e 厶，t h es t a t i o n a r ys t a t e ，a f t e rm i l i i o n 80 fs t 印so fe v o l u t i o n五i st h e m a x i m u m 、，a d u ei nt h es t a t i o n a r y8 t a t e ，w h i c he x h i b i t 8t h a tt h e8 y s t e mi sg e t t i n gs a f e r a 1 1 dm o r ej n v u l n e r a b l eu n d e rc o n t i n u o u sa t t a c k sa n dr e d a i r s o nt h eo t h e rh a n d ，t h e m a x i m u md e g r e ei nt h es t a t i o n a r ys t a t e ，( d 。) c ，i st h em i n i m u mi nt h es y s t e m ， f 研t h es t u d yo fe r d 6 s r 6 n y ir a n d o mn e t w o r k si nt h e8 t a t i o n a r ys t a t e ，li si n d 印e m d e n to fn e t 、r ks i z e a n dc o n n e c t i o np r o b a b 订i t yp ，b u th a sap a w e i q a wd e p e n d e n c e o nt h ea 、帕r a g ed e g r e e ( 忌) = p t 砒s oh a sap o w e 卜l a wr e l a t i o n s h i pw i t ht h er e p a i r p r o b a b i l i t yp r e ，w i t ht h ee x p o n e n trd e c r e a 8 i n gw i t ht h ei n c r e a s i n go fn e t w o r ks i z e b a r a b 如j a l b e r ts c a l e f i 它en e t w d r k sw i t hp o w e rl a wd e g r e ed i s t i j b u t i o n ，j sac o m p l e t e l yd i f f e r e n tt o p o l o g i c a ls t r u c t u r ef r o mr a n d o mg r 印h sw i t he x p o n e n t i a l d e g r c ed i s tr i b u t j o n f b r 亡h es c a i e - f e en e e w o r k si n h es t a i o n a r ys t 8 t e ，厶i ss i i g b ! yg r e a e rt h a n t h a to ft h er a n d o mg r a p hu n d e rt h e8 a m en e t w o r ks i z e a n dr e p a i rp r o b a b i l i t yp ，e c o r r e 8 p o n d i n g iy t h em a x i m u md e g r e ei nt h es t a t i o n a r ys t a t e ( 七m 口z ) ci 8s l i g h t i yi e s 8 l l l 博士学位论文 d o c t o r a l d i s s e i f t i o n t h a nt h a to ft h er a n d o mg r a p ht h es t a t i o n a r yv a l u e 厶f o rs c a l e _ f r e en e t w o r k sh a sa p 0 r e r 。1 a wd e p e n d e n c eo nt h er e p a i rp r o b a b i l i t yp r e u n d e ra x e dn e t w o r k8 i z e ，t h e h i g h e rt h er e p a i rp r o b a b m 妙i s ft h es m 出】e rt h es t a t i o n a r y 、，a l u eli s o nt h eo t h e r h a n d ，u n d e rt h ef i x e dr e p a i rp r o b a b i l i t y ，t h el a r g e rt h en e t w o r ks i z ei s ，t h es m a l l e rl i s as i m p l es t u d yt ot h ew a t t s - s t r o g a t zs m a l l - w o r l dn e t w o r l c s8 h o w 8t h a t ( s ) c a na l s o r e a c h 七h es t a t i o n a r yv a l u ela f t e ral o n gt i m ee v o l u t i o n t h ee f r e c t so fr e p a i rs t r a t e g yt ot h ec o m p l e xn e 七w o r k sa r e8 t u d i e db yc o m p a r i n g t h et o p o l o g i c a lc h a n g e so fr a n d o mf a p h 8a n ds c a l e f r e en e t w o r k si nt h ei n i t i a la n d s t a t i o n a r ys t a t e u n d e rt h es t a t i o n a r ys t a t e ，r a n d o mg r a p h sa r ec o m p o s e do fh i g h l y c l l l 8 t e r e ds m d lc l u s t e r i n g s jw h i l e8 c a l e - f r e en e t w o r k 8 出s p l a y 七w o e x t r e m ed i v i s i o n ，w i t h f e wn o d e 8o c c u p y j n gm o r ec o n n e c t i o n 8a n dm o r en o d e sh a v i n g1 e s so n e s t h ei t r o d u c eo fr e p a i rs t r a t e g yn o to n l yl e tt h es y 8 t e me v 0 1 v et ot h es t a t i o n a r y s t a t e 以e rm i l l i o n 8o ft i m cs t e p 8 ，b u ta b oi n c r e a s et h et o l e r a n c eo fe o m p l e x e t w o r k 8 u n d e rc o i l t i n u o u 8a t t a c k s w e8 1 1 以y z et h ec o r r e l a t i o np r 叩e r t i e 8o ft h ee r d 6 s - r 6 n y ir a n d o mg r a p ha n dt h e b a r a b 缸i a l b e r ts c a l 争f r e en e t w o r ku n d e rt h ea t t a c k 姐dr e p a i rs 虹a t e g yw i t hd e t r e n d e d b u c t u a t i o na n a l y s i s ( d f a )t h em a x i m u md e g r e e 七眦，r e p r e 8 e n t i n gt h el o c a lp r o p e r t y o f t h es y s t e m ，s h o w 88 i m i l a rs c a u n g b e h a v i o r 8f o r r a n d o mg r a p h sa n ds c a l e _ f r e en e t w o r k s t h en u c t u a t i o n 8a r eq u i t er a n d o ma t8 h 叫tt i m es c a l e 8b u td i s p l a ys t r o n ga n t i c o r r e l a t i o n a tl o n g e rt i i n es c a l e 8u n d e rt h es a m es y s t e ms i z e a n dd i 行e r e tr e p a i rp r o b a b i l i t yp r e t h ea v e r a g ed e g r e e ( 七) ，r e v e a l i n gt h es t a t i 8 t i c a ip r o p e r t yo ft h es y s t e m ，e x h i b i t sc o m - p l e t e l yd i f f e r e n ts c a l i n gb e h a v i o r sf o rr a n d o mg r a p h 8a n d s c a l e _ f r e en e t w o r k sr a n d o m g r a p h sd i s p l a yl o n 哥r a n g ep o w e r l a wc o r r e l a t i o n s s c a l e - f r e en e t w o r k 8a r eu r l c o r r e l a t e d a ts h o r tt i m es c a l e s ；w h i l ea n t i c o r r e l a t e da t1 0 n g e rt i m es c a l e sa n dt h ea n t i c o r r e l a t i o n b e c o m i n gs t r o n g e rw i t ht h ei n c r e a s eo f 肼e t h r o u g ht h e8 t u d yo fu sa i r p o r tn e t w o r k ，w e 矗n dt h a tt h en e t w 口r kd i s p l y st w o i m p o r t a n tf e a t u r e 8o fs m a l l w o r l dn e t w o r k 8 h i g hc l u s t e r i n gc o e m c i e n ta n ds m a l la v e r a g e p a t hl e n g 乞h h o w e v e r ，t h ed e g r e ed i s t r i b u t i o no fu sa i r p o t tn e t w o r kf o l i o w st w o _ s e g m e n t l v 博士学位论文 d o c t o r a l d i s s e r l a t i o 咐 p o w e r l a w s ，d i h 色r e n t l yf r o mt h ee x p o n e n t i a ld e g r e ed i s t r i b u t i o no fs m a l l w o r l dn e t w o r k s o nt h eo t h e r h a n d ，t h eu sa i r p o r tn e 七w o r ke x h i b i t sah i g hd e g r e eo fe r r o rt o l e r a n c ea n d a ne x t r e m ev u l n c r a b i l i t yt oa t t a c k s ，w h i c hi st h es a m ea st h er o b u s t n e s so fs c a l e f r e e n e t w o r l ( su n d e re r r o r 8a n da t t a c k s ar e v i e wo fr e c e n tr e s e a r c ho nt h em o d e l s ，d y n a m i c 8a n da p p l i c a t i o n 8o fc o m p l e x n e 七w o r k 8i si n t r o d u c e d k e yw o r d s ：c o m p l e xn e t w o r k s ，e r r o r ，a t t a c k ，8 t a b i l i t d e t r e n d e da u c t u a t i o na n a l y s i s c o r r e l a t i o np r o p e r t ) - t o p o l o g i c a ls t r u c t u r e ，r o b u s t n e s s 博士学位论文 d o c t o r a l d l s s 碰i o n 华中师范大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名：础而辱日期： 6 年弘月讪日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：她面摹 日期： b 年毕月计日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程” 中的规定享受相关权益。同意论文提交后滞后：畔年；口 学位论文作者签名：她西辛 日期：卯【年争月伽日 指导教师签名： 日期蕊移函 发布。 泐， 覆啪 一：毕 詹乍 三 签，胜 师 们 一砧 导 期 措 日 博士学住论文 d o c t o r a l d i s s e 裂l 辄i o n 前言 谈到复杂网络，很多人都会想到i n t e r n e n t 。其实i n t e r n e t 只是复杂网络的一种。自 然界中的很多复杂系统都可以用网络的形式来加以描述。网络是由结点和结点之间的 连线构成的，其中结点代表复杂系统中的元素，而结点之间的连线则代表复杂系统内 元素之间的关系。像i n t e r n e t ，每一个路由器可以看作是网络中的一个结点，而路由 器之间的光纤连接则可以看作是网络中两个结点之间的连线。还有，社会系统中的人 际关系可以看作是人以及人与人之间的朋友关系所构成的网络；食物链系统可以看作 是动物和动物之间的捕食关系构成的网络；等等。 对复杂网络的研究可以追溯到图论中的柯尼斯堡七桥问题f 1 1 。1 8 世纪在柯尼斯 堡城( 今俄罗斯加罩宁格勒) 的普莱格尔河上有7 座桥，将河中的两个岛和河岸连结， 如图1 ( a ) 所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走 遍7 座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是著名的“七桥问 题”。 这个问题看起来似乎不难，但人们始终没有能找到答案。1 7 3 6 年，大数学家欧拉 解决了这个问题。欧拉用抽象分析法将图中被河隔开的陆地看成a 、b 、g 、d4 个 点，把7 座桥表示成7 条连接这4 个点的线，如图l ( b ) 所示。 欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数 必须为偶数才能完成一笔画。图1 ( c ) 的每个点都连接着奇数条边，因此不可能一笔画 出，这就说明不存在一次走遍7 座桥，而每座桥只许通过一次的走法。 欧拉对“七桥问题”的研究是图论研究的开始。在随后的近2 0 0 年间，图论 只是用来研究规则网络或是结点个数比较少的小结构网络。到2 0 世纪5 0 年代 】 博士学位论文 d o c t o r a l d i s s e j m 蟑1 0 n 图1 ：著名的柯尼斯堡七桥问题。 末，e r d 6 s 和r 6 n y i 将随机方法引入到图论中，提出了随机网络的概念，从此开辟 了复杂网络研究的先河 2 ，3 】o 随机网络的概念在接下来的4 0 年里一直主导着人们对现实世界的理解和思维。直 到1 9 9 8 年w 乱t 8 和s t r o g a t z 提出小世界网络的概念1 4 】和1 9 9 9 年b a r a b 自i 和a 1 b e r t 提出无 标度网络的概念【5 ，6 】，才又掀起了新一轮的复杂网络研究热潮。他们发现现实生活中 的网络远远不止是传统的随机网络，对复杂网络的研究也不再是只与数学和计算机科 学有关，而是与许多科学领域都有关，如物理、生物、社会科学、经济学等。 如今复杂网络的研究又开始从网络的拓扑结构研究转向网络的动力学机制研究。 我们知道，大多数网络都通过网络中个体之问的相互作用来实现它们的功能和作用。 比如，电力网络通过变电站来传输电力，交通网络通过车站或机场来运输乘客。于是 如何优化网络的传输效率成为了网络动力学研究的一项重要内容 7 ，8 】。另一方面，由 于一些特殊情况的出现，如交通系统中的公路堵塞，互联网上的信息阻塞，电力系统 中的停电事故等，因此，如何定量地描述网络所受到的影响也是复杂掰络研究的另一 个重要问题。当然，对复杂网络的研究毕竟才刚开始起步，还有很多问题有待我们去 研究和探索。 本文从复杂网络的动力学研究出发，主要探讨了复杂网络在遭袭情况下的修复研 究，以及复杂网络在修复机制下的稳定性与关联特征，并对美国航空网络给予了实证 研究。 2 博士学位论文 d o c t o r a l d i s s e r r i o n 我们首次提出了复杂网络遭受重大袭击后的修复研究。研究了e r d j s r e n y i 随机网 络、w a t t 8 s t r o g a t z 小世界网络、b a r a b 缸i a 1 b e r t 无标度网络在这种修复机制下的稳 定性，以及在修复前后，这三种复杂网络的拓扑结构变化。 我们提出了一个新的概念：抗毁性j ( s ) 。抗毁性j ( s ) 反映了复杂网络对攻击事件 的承受能力。j ( s ) 为阶梯式递增函数，在经过长时间的演化后，最终会出现一个稳定 值厶。系统达到稳定状态。在稳定状态，l 的值是系统中最大的。，( s ) 的逐渐增大表 明系统在遭袭事件和修复策略的共同演化过程中，变得越来越不容易受到攻击，越来 越安全。另一方面，稳定状态的最大连接度( k 。) 。是系统中最小的。换句话说，系统 在演化中的任一时刻，其最大连接度都不会小于( 。) 。 对随机网络，在稳定状态下，稳定值厶与网络的大小、连接几率p 都没有关 系，而只与随机网络的平均连接度( ) = p 有关，且为幂次关系。另外，稳定值厶与 修复几率p r 。也呈现幂律关系，在相同的修复几率下，幂指数r 与系统大小有关， 并随着系统大小的增大而逐渐减小。 无标度网络的连接度分布为幂律分布，其拓扑结构与指数型连接度分布的随机网 络完全不同。稳定状态下的无标度网络，在相同系统大小和修复几率下，其稳定值厶 略大于随机网络，相应地，最大连接度( 。) 。则略小于随机网络的。另一方面，无标 度网络的稳定值厶与修复几率肼。也有幂律关系。在相同的系统大小下，修复几率越 大，稳定值就越小：在相同的修复几率下，系统大小越大，稳定值反而越小。 我们也简单地研究了小世界网络的抗毁性j ( s ) ，发现小世界网络的抗毁性，( s ) 最 终也可以到达稳定状态下的厶。 通过对比随机网络和无标度网络在初始状态和稳定状态下的拓扑结构变化，研究 了修复策略对这两种具有完全不同拓扑结构的网络的影响。研究发现，稳定状态下的 随机网络变成了一个高度小集团化的网络，而无标度网络的“两极分化”则更加严 重：少数结点占有系统中更多的连线数日，大多数结点则只拥有系统中更少的连线数 目。 研究发现修复策略的引入大大增强了网络抵抗持续攻击的能力，提高了网络的抗 攻击能力。 用去趋势涨落分析方法分析了随机网络和无标度网络的关联特征。 3 博士学位论文 d o c t o r a l d i s s e r m 奸1 0 n 代表复杂网络局域特征量的最大连接度，通过其序列的d f a 分析，发现随机 网络和无标度网络的。序列在小的时间观察尺度内是完全随机的，而在非常大的时 间观察尺度内呈现很强的负关联。 代表复杂网络整体特征量的平均连接度( ) ，通过其序列的d f a 分析，发现随机网 络的( ) 序列在整个时间尺度内呈现长程幂律关联；无标度网络的( ) 序列在小的时间 观察尺度内毫无关联，在大的时间尺度上呈现负关联，负关联会随着修复几率的增加 而增强。 通过对美国航空网络的实证研究，我们发现美国航空网络具有小世界网络的特 征，太的聚集系数和小的最短路径。但是，美国航空网络的连接度分布却呈现两段幂 律分布，与小世界网络的指数型连接度分布不同。 另一方面，从美国航空网络的鲁棒性来说，美国航空网络的容错能力很强，抗攻 击能力却很差，具有无标度网络的鲁棒性特征。 全文共分七章。第一章介绍了复杂网络的基本概念，包括描述复杂网络的主要拓 扑参量，研究复杂网络的主要模型：随机网络、小世界网络、无标度网络等。第二章 从两个层面介绍了复杂网络的动力学研究。( 1 ) 以复杂网络为背景的动力学研究， 包括疾病在复杂网络上的传播。以及各种复杂网络上的伊辛模型、b a k s n e p p e n 模型 等。( 2 ) 复杂网络自身演化的动力学研究。主要从复杂网络拓扑结构的改变( 删除 或增加结点和连线) 来研究复杂网络自身的演化。第三、第四和第五章是本文的主要 部分，介绍了我们的研究工作。在第三章，我们提出了复杂网络遭受袭击后的修复性 研究，引入了一个新的概念“抗毁性”，并进一步研究了复杂网络在修复机制下的稳 定性，以及在修复前后复杂网络拓扑结构的变化等。在第四章，利用去趋势涨落分析 法，探讨了随机网络和无标度网络在修复机制下的关联特征。在第五章中，利用从美 国交通统计局的官方网站上收集到的数据，对美国航空网络的拓扑结构，以及美国航 空网络对出错和遭袭两种突发事件的应变能力作了实证研究。第六章简要介绍了复杂 网络在社会关系、信息交流、交通系统、电力系统、人类语言等方面的应用研究。最 后一章是工作总结和展望。 4 博士学位论文 d o c t o r a l d i s s e r i i o n 第一章复杂网络模型 我们经常用模型来抽象和简化现实世界，复杂网络模型也是其中一种，它使得我 们可以更好地理解事物间的关系。复杂网络中的结点可以代表人、计算机、城市等任 何事物，复杂网络中的连线则表示结点之间的关系，如两个相互认识的人，两台可以 通信的计算机，两个有直达航线的城市等。很多科学领域都用到了复杂网络模型。化 学上用复杂网络模型来研究分子之间的相互作用，城市规划者用复杂网络模型来分析 交通流量，经济学上用复杂网络模型来探讨金融市场中的博弈，等等。 在复杂网络模型中，我们并不关心结点的大小和形状，也不关心它在坐标系中的 位置，至于连线，也不管它是弯曲还是笔直，它的实际物理距离等。我们把复杂网络 不依赖于结点的具体位置和连线的具体形态就能表现出来的性质叫做网络的拓扑性 质，相应的结构叫做网络的拓扑结构f 8 6 1 。 这一章将首先介绍常用的描述复杂网络拓扑结构的参量，然后再简单回顾描述复 杂网络的几个主要模型。 1 1复杂网络的拓扑参量 到目前为止，并没有一个普适的参量可以表征所有的复杂网络。下面我们将简单 介绍几个常用的描述复杂网络的拓扑参量。 【1 】连接度( d e g r e e ) 结点i 的连接度是指与此结点相连的所有连线的数量。由于每一条连线有 两个端点，网络中总的结点数为，于是网络中总的连线数目可以写为： 5 博士学位论文 d o c t o r a l d 璐s e i m 叮1 0 n e = ； ( 1 1 ) 平均连接度也是网络中一个非常重要的参量，可以简单写为： = 专= 等 ( 1 。) 对于有向网络，连接度又分为出度( o u t g o i n gd e g r e e ) 和入度( i n c o m i gd e _ g r e e ) 。 【2 】连接度分布( d e g r e ed i s t r i b u t i o n ) 连接度分布p ( ) 表示网络中一个结点的连接度为的几率。在有向网络中，分 为出度分布p 一( ) 和入度分布a 。( 七) 。 【3 】聚集系数( c l u s t e r i n gc o e m c i e n t ) 聚集系数反映了网络集聚成团的程度。在社会关系网络中，通常指你的朋友之 间彼此互相熟悉的程度。 目前聚集系数主要有两种定义方法f 1 0 ，1 1 】o 第一种，选择网络中的一个点 ，假 定这个点的连接度为，即这个点有个最近邻。这h 个最近邻之间所有可能 的连线数目为既= ( 一1 ) 2 。我们用啦表示实际存在于这些最近邻之间的 连线数目，那么点 的聚集系数可以写为： g 。高， ( 1 3 ) 因此聚集系数的取值在0 到1 之间。整个网络的聚集系数则是g 的平均， 聚集系数的另一个定义是 a = 嘉g 6 ( 1 4 ) 博士学住论文 d o c t o r a l d i s 懿璁i i a l 1 0 n 图1 1 ：按第一种方法计算出来的聚集系数为。c = i 耳兰聊= ，g = 器；按第二种方法计算 出来的聚集系数为：g = 3 = ； e = 黧裂筹等舞糍鬻 n s ， 礼“r n d e ro rc 帆礼e c z e dt r 4 口化so ru e r z c e 5 图1 1 给出了用两种方法所计算出来的聚集系数。 【4 】平均最短路径( s h o r t e s tp a t hl e n g t h ) 从结点 到结点j 的最短路径是指所有从i 到j 的连通的通路中，所经过的 其他结点最少的一条或几条路径。平均最短路径工是对所有岛的平均。 三= 耐可吾 ( 1 s ) 【5 】效率( e 币c i e n t ) 结点 和结点j 之间的效率与它们之间的平均最短路径岛成反比【1 2 ， 1 3 】，5 玎= 1 岛。这样当结点 和j 之间没有连线时，= + o 。，而效率则为 = 0 。整个网络的效率可以定义为： ( 1 7 ) 土岛 喇 南 ， 昱 ” 博士学位论文 d o c t o r a l d i s s 1 0 n 结点t 的介数 1 4 1 含义为网络中所有的最短路径之中，经过i 的数量。它反映了 结点i 的影响力【9 1 。 ( 1 8 ) 其中，表示从结点j 到的所有最短路径的数目，k ( i ) 表示从结点j 到 的所有最短路径中经过结点i 的数目。在考虑信息的传输时，也有人称之为负 载( 1 0 a d ) 1 5 】。经过结点t 的最短路径越多，就表明结点i 所承受的信息流量 越大，因此其负载也越大。 【7 】匹配性( 8 0 r t a t i v i t y ) 匹配性主要是考察连接度之间的关联，即连接度大的结点倾向于和连接度大的 结点连接，还是倾向于和连接度小的结点连接。这个概念最先由n e w m 8 i l 提 出【1 6 ，l7 ，其方法是，通过任意一条边都可以找到两个结点，进而得到两个 连接度的值，这样通过所有的连线我们就得到了两个序列，分析这两个序列的 相关性即可。匹配系数r 的取值在0 到1 之间，当0 r l 时，网络j 下向匹配 ( 阳8 0 r t a t i v i 七y ) ，当一1 r 0 时，网络反向匹配( d i s a s s o r t a t i v i t y ) 。 还有一种方法就是通过一个结点的最近邻的平均连接度来定义连接度之间的关 联【2 2 】。结点 的最近邻的平均连接度定义为： k 严恚塾b ， 。， 其中为连接矩阵元素，当结点i 和j 之间有连接时。玎= 1 否则。坩= 0 ，如 图1 2 所示。于是连接度为的结点的最近邻的平均连接度可以表示为： = 黼 ( 1 1 0 ) 如果k 。( 女) 随连接度而增加，则网络是正向匹配( a 8 8 0 r t a t i v e ) ；如果。( ) 随 连接度而减少，则网络是反向匹配( d i 8 a s s o n a t i v e ) 。 8 警 辨 | | 8 博士学位论文 d o c t o r a l d i s s e i i o n 圈1 2 ：计算k 。，i 的一个示侧，k 。= ( 4 + 6 + 4 + 3 ) 4 = 4 5 。 【8 】最大连通子图( g i a n t ( 1 a r g e 8 t ) c o m p o n e n t ) 一个网络总是存在一个最大连通子图，这个子图内所包含的结点比网络中其它 子图的都要多，并且任意两个结点之间都存在通路。 描述复杂网络拓扑结构的参量还有很多【1 8 】 如群落结构【l 弘2 l 】等，在此就不一 一介绍了。下面我们将简单介绍几种主要的复杂网络模型。 1 2 规则网络 图1 3 ：规则网络：( a ) 一维链；( b ) 二维晶格。 9 博士学位论文 d o c t o r a l d i s s e r i m 1 0 n 我们把如图1 3 所示的一维链、二维正方晶格等称为规则网络。规则网络所有结点 的连接度都相同 2 3 】，均为，其连接度分布则为j ( 一k ) 。如图1 3 ( a ) 所示，每一 个结点的连接度为= 4 ，这样一个网络的平均聚集系数为： g = 黼 ( 1 1 1 ) 当耳很大时，其极限值为3 4 。规则网络的平均最短路径大致为一1 d ，其中d 表 示规则网络的维数。因此规则网络有着大的聚集系数和大的平均最短路径。 1 3 随机网络 图1 4 ：e r d 穗一r 6 1 1 y i 随机网络的演化过程。网络中有= 1 0 个结点，连接几率p = o 时，网 络中没有连线：p = o 1 时，网络中有5 条连线；p = o 1 5 时，网络中有7 条连线。 随机网络的研究始于2 0 世纪5 0 年代匈牙利的两位数学家e r d 6 s 和r 6 n y i 2 ，3 】，随 机网络模型在随后的近4 0 年罩一直主导着人们对网络系统的认识。按照e r d 洳一r 叠n y i 模型，以几率p ( o p 1 ) 随机连接个网络结点之间的任意两个结点，这样便构成 了一个随机网络【2 3 口由于个结点之间最大可能存在c 舞条连线，因此网络中实际 存在的总连线数目为： 随机网络的平均连接度为 e 叩岛叩业 1 0 ( 1 1 2 ) 葑 一窃 博士学位论文 d o c t o r a l d j s s e i 函盯i o n = 等刊叫= p ( 1 1 3 ) 由于随机网络的任意两点之间都是以相同的几率p 连接的，因此随机网络的聚集系数 为： 随机网络的平均最短路径为： 。：p 。磐 v ( 1 1 4 ) 一端 ( 1 1 5 ) 从式( 1 1 4 ) 和( 1 1 5 ) 可以看出，随机网络有着小的聚集系数和小的平均最短路径。 自e r d 6 8 和r 6 n y i 提出随机网络的构造模型后，有很多科学家对随机网络的结构和 演化特征作了更加细致的研究 2 4 3 2 】。 1 4 小世界网络 1 9 9 8 年，w a t t 8 和s t r o g a t z 发现现实世界中的很多网络系统都具有被称为“小世 界”的特征【4 ，3 3 】，即尽管网络中的个体数很多，网络中的任何个体也只需要经过有 限的几步就可以到达同一网络中的任何其它个体。这个发现导致了一类网络结构一一 小世界网络( s m a i i w o r l dn e t w o r k ) 的诞生。 w a t t s 和s t r o g a t z 的