（微电子学与固体电子学专业论文）复杂网络稳定性研究.pdf

贵州大学博士学位论丈 d o c i d r a ld i s s e r i a 叮o n 摘要 本文从复杂网络的拓扑统计特性和动力学机制出发，将非平衡统计理论、 非线性系统理论、随机微分方程方法以及f o k k c r - p l a n k 方程的定态解应用到复 杂网络的研究中。主要研究了在非平衡涨落驱动下复杂网络的动力学稳定性， 以及在蓄意攻击情况下病毒在复杂网络上的传播机理，这两个方面的研究无论 在理论上还是在实践中都有着十分重要的意义。通过对复杂复杂网络的稳定性 的研究，一方面可以使我们更清晰的认识和理解实际网络所表现出的各种动力 学现象；另一方面，我们可以将复杂网络稳定性研究的成果应用到实际中去， 可设计出更好性质的网络或使网络处于更有利的状态。对在蓄意攻击情况下病 毒在复杂网络上的传播机理的研究，一方面可为研究和开发新的免疫机制与策 略提供理论基础，另一方面也有利于提高网络信息传输能力另外，复杂网络 在许多领域都得到了较为广泛而深入的应用，作为本课题的一个主要内容，我 们综述了复杂网络理论在电子电路与微电子学方面的应用。 本文的主要内容和创新之处可作如下概述： 1 非平衡涨落与小世界网络稳定性的研究 针对小世界特性是复杂网络的普遍特性，我们首先研究了故障对小世界网 络稳定性的影响。在把实际网络元素的差错、失效等等“故障 抽象为非平衡 随机涨落的前提下，利用非平衡统计理论、随机微分方程方法以及f o k k c r - p l a n k 方程的定态解，来研究小世界网络稳定性。研究从小世界网络模型的非线性相 互作用系数九和n w 长度标度( 两个具体参数展开。 ( 1 ) 通过理论研究，我们首次发现了，小世界网络的特性参量n w 长度标 度是网络突变发生的敏感因子。当非平衡涨落发生在特性参量n w 长度标度 ：- ( 上时，n w 长度标度的平均值；在涨落s 2 的驱动下迅速增长。在随机化连接 概率p 不变时，网络的度值k 将迅速减小。当k 减d , n 某一值时( 比如k 1 ) ， 复杂网络系统的稳定性将发生突变。由n w 长度标度( 的定义可知，复杂网络 辅要 的节点这时应仍然存在，但是节点之间的连接边基本被删除。这种情况，对应 于整个网络系统出现了崩溃。这一研究结论充分说明，作为小世界网络特性参 量的n w 长度标度( 是传播稳定性的主要决定因素。电力网络由于个别节点跳 闸而发生大停电事故，是这一发现的最好例证。 ( 2 ) 相比之下，当非线性相互作用系数九发生非平衡涨落时，n w 长度 标度( 随涨落s 2 呈迅速下降趋势。在随机化连接概率p 不变的情况下，小世界 网络系统的度值k 会缓慢增加。这表示网络系统连通性会增强，网络会向更稳 定的方向发展。也就是说，系统的非线性相互作用系数发生的涨落，不是引起 复杂网络系统稳定性发生宏观突变的主要因素。 2 蓄意攻击与复杂网络稳定性的研究 或许蓄意攻击会有较多的方式，但病毒的攻击方式在网络上是如此的泛滥， 必然引起我们的高度重视。因此，本课题中我们主要研究了病毒的传播机理及其 稳定性。 ( 1 ) 我们提出了一种描述病毒传播的新模型s i s b d 模型。利用这一模型以 及非平衡统计理论，随机过程的理论和方法，从病毒传播的前期、后期及传播的 全过程三个方面进行了研究。得到了病毒传播的三个时期病毒感染密度函数的分 布规律。比较实际数据可知，这个分布过程与实际数据符合得较好。 ( 2 ) 研究过程中我们发现，病毒的有效传播速率并不是一个常数，而是一 个可以用类l d 幽t i c 微分方程描述的函数。这与传统传染病研究中，病毒的传 播速率通常是一个常数明显不同。通过求解类l o g i s t i c 微分方程和用实际数据 拟合出相关的常数，并结合前两部分的研究结果，得到了病毒传播全过程的感 染密度分布函数。这个分布函数曲线与实际病毒传播数据曲线十分吻合。 ( 3 ) 进一步分析有效传播速率我们知道，它与网络的结构参量密切相关。 由此，我们用理论分析的方法讨论了有效传播速率与复杂网络结构参量的关系。 经过分析，推论了网络节点的平均度值与有效传播速率变化率成正比；网络的 聚类系数与有效传播速率成正比。从而得到病毒传播的有效速率与网络结构参 量之间的更为普适的函数关系式。 青州大学博士学位论文 d o c 阳r a ld i s s e r 【衄o n 3 非平衡统计理论与方法 利用非平衡统计理论与方法研究复杂网络，从研究方法上来说本身与是一 种创新。 在本文的最后，我们介绍了复杂网络理论在电子电路与微电子学方面结合 实际的可能应用。重点对目前引起了广泛研究兴趣，并成为最新研究热点的量 子相干网络、纳米线网络等作了简要介绍，这是复杂网络理论应用在量子信息 技术上的一些探索。 关键词：复杂网络稳定性涨落蓄意攻击非平衡统计随机过程母函数 s i s b d 模型 a b s t r a c t t h i st h e s i si sc o n c e r n e dw i t ht h es t u d yo ft h ed y n a m i c ss t a b i l i t yo fc o m p l e x n e t w o r kd r i v e nb yn o n - e q u i l i b r i u mf l u c t u a t i o na n dv i r u s ss p r e a d i n gm e c h a n i s mo n c o m p l e xn e t w o r ku n d e rt h ei n t e n t i o n a la t t a c k , w h i c hu s et h en o n e q u i l i b r i u m s t a t i s t i c a lt h e o r y , t h es t o c h a s t i cd i f f e r e n t i a l e q u a t i o n m e t h o da sw e l la st h e f o k k e r - p l a n ke q u a t i o ns t e a d y s t a t es o l u t i o n t h e s es t u d i e sa r ev e r yi m p o r t a n tb o t h i nt h e o r ya n di np r a c t i c a la p p l i c a t i o n s b ys t u d y i n gs t a b i l i t yo fc o m p l e xn e t w o r k , o n t h eo n eh a n d ，w ec a nu n d e r s t a n da n de x p l a i nt h ed y n a m i cp r o p e r t i e sp r e s e n t e di n r e a l - w o r l dn e t w o r k s ；a n do nt h eo t h e rh a n d ，w ec a na p p l yt h e s et h e o r e t i c a lr e s u l t so f c o m p l e xn e t w o r ks t a b i l i t yt os o m ep r a c t i c a la p p l i c a t i o n s ，f o ri n s t a n c e ，w em a y d e s i g no fr e a ln e t w o r kt oa c h i e v ea b e t t e rp e r f o r m a n c eb yu s i n gt h i sr e s u l t s b y s t u d y i n gv i r u s ss p r e a d i n gm e c h a n i s mo nc o m p l e xn e t w o r ku n d e rt h ei n t e n t i o n a l a t t a c k , o nt h eo n eh a n d ，w ec a np r o v i d et h er a t i o n a l et os t u d ya n dd e v e l o pt h en e w i m m u n i t ym e c h a n i s ma n dt h es t r a t e g y ；o nt h eo t h e rh a n d ，t h e r ea l ea d v a n t a g e o u si n r a i s i n gt h en e t w o r kt r a n s m i s s i o ne f f e c t i o n i na d d i t i o n , c o m p l e xn e t w o r kt h e o r y m o r ea n dm o r ew i d e s p r e a da p p l i e si nm a n yd o m a i n s a st h i st o p i cm a i nc o n t e n t s ，w e s u m m a r i z e dt h ea p p l i c a t i o no fc o m p l e xn e t w o r kt h e o r yi nt h ee l e c t r o n i cc i r c u i ta n d m i c r o e l e c t r o n i c s t h em a i nc o n t e n t sa n d o r i g i n a l i t i e si nt h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： 1 n o n e q u i l i b r i u mf l u c t u a t i o na n ds m a l l - w o r l dn e t w o r ks t a b i l i t y u s i n gt h en o n e q u i l i b r i u ms t a t i s t i c a lt h e o r y , t h es t o c h a s t i cd i f f e r e n t i a le q u a t i o n m e t h o d 勰w e l la st h ef o k k e r p l a n ke q u a t i o ns t e a d y s t a t es o l u t i o n ，w eh a v es t u d i e d t h es m a l l w o r l dn e t w o r ks t a b i l i t yb ya b s t r a c t i n gt h er e a ln e t w o r kf a c t o r so fe l e m e n t m i s t a k e ，n o d eb r e a k d o w na n ds oo na st h en o n - e q u i l i b r i u ms t o c h a s t i cf l u c t u a t i o n w ed i s c u s ss e p a r a t e l yt w ok i n d so fs i t u a t i o n st ou n i f ys t r u c t u r e p a r a m e t e r so f v曲 贵州大学博士学位论文 d o c i d r a ld i s s e r i 觚o n s m a l l - w o r l dn e t w o r km o d e l ，o n ei st h ef l u c t u a t i o nt oo c c u ri nt h en o n l i n e a r i t y a f f e c t st h ec o e f f i c i e n ta n da n o t h e ri si nt h en w l e n g t hs c a l e ( 1 ) t h r o u g hf u n d a m e n t a lr e s e a r c h ，o u ri n i t i a lf m do u t ：i ft h en o n - e q u i l i b r i u m f l u c t u a t i o no c c u r si nt h en w l e n g t hs c a l e t h en wl e n g t hs c a l e sm e a nv a l u er a p i d g r o w t hd r i v e nb yf l u c t u a t i o nsz i ti m p l i e st h a tr a n d o m i z a t i o nc o n n e c t i o np r o b a b i l i t y p i si n v a r i a b l e ；t h ec o m p l e xn e t w o r kd e g r e e sv a l u ekw i l lb er a p i d l yr e d u c e d w h e n kr e d u c e st os o m ev a l u e ( f o ri n s t a n c e ：七 1 ) ，t h es t a b i l i t yo fc o m p l e xn e t w o r ks y s t e m s t r u c t u r ew i l lh a v eaf i e r c ec h a n g e m a yk n o wb yt h en w l e n g t hs c a l e ( d e f i n i t i o n , t h ec o m p l e xn e t w o r kn o d es h o u l ds t i l le x i s t ，b u tt h ec o n n e c t i o nb e t w e e nt h en o d e si s d e l e t e dc o m p l e t e l y t h i sk i n do fs i t u a t i o nm i g h tc o r r e s p o n di nt h ee n t i r ec o m p l e x n e t w o r ks y s t e mc o l l a p s e t h i sc o n c l u s i o nf u l le x p l a i n st h a tt h en w l e n g t hs c a l e ( i s ap r i m a r yf a c t o rt od e c i d et h ed i s s e m i n a t i o ns t a b l ea st h es m a l l - w o r l dn e t w o r k c h a r a c t e r i s t i cp a r a m e t e r w h e ni t a p p e a r sf l u c t u a t i o na n da p p r o a c h ac e r t a i n t h r e s h o l d ，t h ec o m p l e xn e t w o r ks t a b i l i t ya n dt h em a c r o s c o p i cd y n a m i c sb e h a v i o r w i l lh a v et h ef i e r c ec h a n g e ，u n t i lw i l la p p e a rt h ee n t i r en e tc o l l a p s e i ti sr e v e a l e d t h a tt h en w l e n g t hs c a l e 乏i so n eo fe x t r e m e l ys e n s i t i v ef a c t o r si nt h ec o m p l e x n e t w o r kd y n a m i c sp r o c e s s ( 2 ) c o m p a r a t i v e l y , i f t h e n o n - l i n e a r i t ym u t u a l l y c o e f f i c i e n t 九h a st h e n o n - e q u i b i r u mf l u c t u a t i o n ，t h en wl e n g t hs c a l efa l o n gw i t ht h ef l u c t u a t i o ns zh a s t h et e n d e n c yt od r o pr a p i d l y i fr a n d o m i s a t i o nc o n n e c t i o np r o b a b i l i t ypi si n v a r i a b l e ， c o m p l e xn e t w o r kd e g r e ekc a ni n c r e a s es l o w l y t h e s ep h e n o m e n o n ss h o wt h e n e t w o r ks y s t e mc o n n e c t i v i t ys t r o n g l ya n dc o m p l e xn e t w o r kc a nd e v e l o pt oas t a b l e r d i r e c t i o n i ti st os a y , i ft h ef l u c t u a t i o no c c u r si nt h es y s t e mn o n - l i n e a rm u t u a l l y c o e f f i c i e n t ，i tc a l ln o tl e a dt ot h ec o m p l e xn e t w o r ks y s t e ms t a b i l i t yt os u d d e nc h a n g e 2 i n t e n t i o n a la t t a c k sa n dc o m p l e xn e t w o r ks t a b i l i t y p e r h a p si n t e n t i o n a la t t a c k sh a v em a n yw a y s ，b u tv i r u sa t t a c k so nn e t w o r ka r e l i k et h i sb e i n gi nf l o o d ，w eh a v et ot a k ei ts e r i o u s l y ( 1 ) w ep r o p o s e do n ek i n do fn e wm o d e l s i s - b dm o d e lw h i c hr e p r e s e n tv i r u s d i s s e m i n a t i o n u s i n gt h i sm o d e la n dn o n - e q u i b i r u ms t a t i s t i c a lt h e o r ya sw e l l a s s t o c h a s t i cp r o c e s st h e o r ya n dm e t h o d , w es t u d yt h ev i r u ss p r e a d i n gf r o mt h r e e a s p e c t s ：e a r l i e rp e r i o d ，t h el a t e rp e r i o da n dt h ed i s s e m i n a t i o ne n t i r ep r o c e s s w eg e t t h ev i r u si n f e c t i o nd e n s i t yf u n c t i o nd i s t r i b u t e dr u l eo fv i r u ss p r e a d i n gi nt h r e e p e r i o d s t oc o m p a r ew i t ht h ea c t u a ld a t a , w ek n o wt h a tt h i sd i s t r i b u t i o nf u n c t i o n a c c o r dw i t ht h ea c t u a ld a t aw e l l ( 2 ) i nt h er e s e a r c hp r o c e s sw ed i s c o v e r e dv i r u s se f f e c t i v ed i s s e m i n a t i o ns p e e d i sn o tac o n s t a n t ，i ti sak i n do ff u n c t i o nw h i c hc a nd e s c r i b eas i m i l a rl o g i s t i c d i f f e r e n t i a l e q u a t i o n i ti s o b v i o u s d i f f e r e n ti nt h et r a d i t i o n a li n f e c t i o u sd i s e a s e s t u d i e si nw h i c hv i r u s sd i s s e m i n a t i o ns p e e di su s u a l l yac o n s t a n t b ys o l u t i o nt h e s i m i l a rl o g i s t i cd i f f e r e n t i a le q u a t i o na n du s e i n gt h ea c t u a ld a t af i r i n gt h ec o r r e l a t i o n c o n s t a n t ，a n du n i o nt w op a r to ff i n d i n g s ，w eo b t a i nt h ei n f e c t i o nd e n s i t yd i s t r i b u t i o n f u n c t i o no fv i r u ss p r e a d i n go ne n t i r ep r o c e s s ( 3 ) b yf u r t h e ra n a l y z e st h ee f f e c t i v ed i s s e m i n a t i o ns p e e dw ek n o wt h a ti tc l o s e c o r r e l a t ew i t hn e t w o r ks t r u c t u r ep a r a m e t e r t h e r e f o r , w cu s e dt h et h e o r e t i c a la n a l y s i s t h em e t h o dt od i s c u s st h ee f f e c t i v ed i s s e m i n a t i o ns p e e da n dt h ec o m p l e xn e t w o r k a r c h i t e c t u r ep a r a m e t e rr e l a t i o n f i n a l l y , w eg e tt h ev i r u sd i s s e m i n a t i o ne f f e c t i v e s p e e dt or e l a t e 、们t ht h en e t w o r ka r c h i t e c t u r ep a r a m e t e rm o r eg e n e r a lf u n c t i o n 3 n o n - e q u i l i b r i u ms t a t i s t i c a lt h e o r ya n dm e t h o d i ti so n ek i n do fi n n o v a t i o nt e c h n i q u et h a tu s e st h en o n - e q u i l i b r i u ms t a t i s t i c a l t h e o r ya n dm e t h o dt or e s e a r c hc o m p l e xn e t w o r k f i n a l l y , w ed i s c u s s e dt h ea p p l i c a t i o no fc o m p l e xn e t w o r kt h e o r y i nt h e e l e c t r o n i cc i r c u i ta n dm i c r o e l e c t r o n i c s f i r s t ，w ei n t r o d u c et h em a i na p p l i c a t i o na n d a c h i e v e m e n to fc o m p l e xn e t w o r ko ne l e c t r o n i cc k c u i t s e c o n d , w em a k et oab r i e f i x 贵州大学博士学位论文 d o c t o r a ld i s s e r i 觚0 n r e p o r ta b o u tt h ec o m p l e xn e t w o r ka p p l i c a t i o ni nt h eq u a n t u mc o h e r e n tn e t w o r ka n d n a n o m e t e rw i r en e t s ，w h i c hb e c o m et h en e w e s tr e s e a r c hh o ts p o ta n da t t r a c tt oh o w w i d e s p r e a dr e s e a r c hi n t e r e s ta tp r e s e n t k e yw o r d s ：c o m p l e xn e t w o r k , s t a b i l i t y , f l u c t u a t i o n ，i n t e n t i o n a l a t t a c k , n o n e q u i l i b r i u ms t a t i s t i c , s t o c h a s t i cp r o c e s s ，g e n e r a t i o nf u n c t i o n ，s i s - b dm o d e l x 首言 前言 自然界和人类社会中广泛存在复杂系统，而复杂系统正好可以通过各种各 样的复杂网络来描述。作为复杂系统主要研究手段的复杂网络，是一门与众多 学科领域广泛交叉的正在兴起的崭新的网络科学。事实上，复杂网络的研究极 大地促进了复杂系统的研究和发展。业已成为当今复杂系统与复杂性科学研究 中最受关注和最具挑战性的科学前沿课题之一。 l 、背景简介 复杂网络的研究可追溯到1 8 世纪欧拉开创的图论。在随后的2 0 0 多年时间 里，图论一直是研究网络图表示的基本方法。直到上世纪6 0 年代，e r d 6 s 和r 6 n y i 创立随机图理论( r a n d o mg r a p ht h e o r y ，pe r d 6 s ，1 9 5 9 ) 。从此，随机图理论在 将近4 0 年的时间里一直是研究复杂网络结构的基本理论。但是，绝大多数实际 复杂网络结构并不是完全随机的。世纪之交( 1 9 9 8 1 9 9 9 ) ，科学家冲破了传统 图论，特别是随机图理论的束缚，以小世界网络( djw a t t s 等，1 9 9 8 ) 和无标 度网络( a l b a r a b f i s i 等，1 9 9 9 ) 两项重要发现为标志，复杂网络的研究取得了 突破性进展。此后，复杂网络的研究迅速地扩展到了广泛的学科领域，并不断 与这些学科领域交叉促进，取得了丰硕的成果。另一方面，由于计算机信息技 术的发展，人们可以研究1 0 8 甚至更高量级的节点组成的系统。使复杂网络的 研究对象范围进一步得到极大的扩展。随着理论出现的重大突破、研究领域的 迅速扩展、研究内容的不断深入和研究手段与方法的不断创新，开创了复杂网 囊 络研究的新纪元。 研究复杂网络的主要目的是理解复杂网络上的动力学行为，特别是理解网 络拓扑结构对其动力学的影响( mjen e w m a n ，2 0 0 2 ) 。众所周知，绝大多数 复杂网络功能的实现和作用的发挥，都是靠网络中的个体和个体之间的相互作 童州大学博士学位论文 d o ( 1 0 r a ld i s s e i l ：i 觚o n 用实现的。譬如：i n t e m e t 通过主机、路由器等来传送信息，高压输电网络通过 变电站来传输电力，电子电路系统通过电子元件实现信号放大与传送等等。因 此，优化网络的传输效率成为网络动力学研究的一项重要内容( rfc a n c h o 等， 2 0 0 1 ) 。另外，在一些特殊情况下，也会出现i n t e r n e t 上的信息拥堵，电力网络 大面积停电，电子电路系统崩溃等等。如何定量描述这些网络受到的影响也是 复杂网络研究的另一个方面的重要问题。再次，复杂网络理论的应用，正在迅 速扩展到可能的实际工程技术领域。然而，复杂网络的研究毕竟才刚刚起步， 还有许多问题有待进一步的探索和研究。 2 、本文研究的主要内容 本文从复杂网络的拓扑统计特性和动力学机制出发，从故障与蓄意攻击两 个方面研究了复杂网络的稳定性。并综述了复杂网络在电子电路设计与微电子 方面的应用。 对复杂网络的稳定性而言，其主要威胁来源于两个方面，一是由于内因或 外因引起的各种“故障 ，而另一个方面是针对网络的蓄意攻击。 针对小世界特性是复杂网络的普遍特性，我们首先研究了故障对小世界网 络稳定性的影响。在把实际网络元素的差错、失效等等“故障 抽象为非平衡 随机涨落的前提下，利用非平衡统计理论、随机微分方程方法以及f o k k e r - p l a n k 方程的定态解，来研究小世界网络稳定性。研究从小世界网络模型的非线性相 互作用系数九和n w 长度标度两个具体参数展开。 通过理论研究，我们首次发现了，小世界网络的特性参量n w 长度标度f 是网络突变发生的敏感因子。当非平衡涨落发生在n w 长度标度f 上时，n w 长度标度的平均值考在涨落j 2 的驱动下迅速增长。在随机化连接概率p 不变 时，网络的度值k 将迅速减小。当k 减4 , n 某一值时( 比如k 1 ) ，复杂网络系 统的稳定性将发生突变。由n w 长度标度f 的定义可知，复杂网络的节点这时 应仍然存在，但是节点之间的连接边基本被删除。这种情况，对应于整个网络 x u 首言 系统出现了崩溃。这一研究结论充分说明，作为小世界网络特性参量的n w 长 度标度f 是传播稳定性的主要决定因素。电力网络由于个别节点跳闸而发生大 停电事故是这一发现的最好例证。 相比之下，当非平衡涨落发生在非线性相互作用系数a 时，n w 长度标度 f 随涨落呈迅速下降趋势。在重连概率p 不变的情况下，小世界网络系统的度 值k 会缓慢增加。这表示网络系统连通性会增强，网络会向更稳定的方向发展。 也就是说，系统的非线性相互作用系数发生的涨落，不是引起复杂网络系统稳 定性发生宏观突变的主要因素。 或许蓄意攻击会有较多的方式，但病毒的攻击方式在网络上是如此的泛滥， 必然引起我们的高度重视。因此，在本课题中我们主要研究了病毒的传播及其 稳定性。 在病毒传播的研究中，我们把传统的s i s 模型与非平衡统计理论中的生灭 方程结合，提出了一种描述病毒传播的新模型，s i s b d 模型。利用这一模型以 及非平衡统计、随机过程的理论和方法，从病毒传播的前期、后期及传播的全 过程三个方面进行了研究。得到了病毒传播的三个时期病毒感染密度函数的分 布规律。比较实际数据可知，这个分布过程曲线与实际数据符合得较好。 研究过程中我们发现，病毒的有效传播速率并不是一个常数，而是一个可 以用类l o g i s t i c 微分方程描述的函数。这与传统传染病研究中，病毒的传播速 率通常是一个常数明显不同。通过求解类l o g i s t i c 微分方程和用实际数据拟合 出相关的常数，并结合前两部分的研究结果，得到了病毒传播全过程的感染密 度分布函数。这个分布函数曲线与实际病毒传播数据曲线十分吻合。 进一步分析有效传播速率我们知道，它与网络的结构参量密切相关。由此， 我们用理论分析的方法讨论了有效传播速率与复杂网络结构参量的关系。经过 分析，推论了网络节点的平均度值与有效传播速率变化率成正比；网络的聚类 系数与有效传播速率成正比。从而得到病毒传播的有效速率与网络结构参量之 间的更为普适的函数关系式。 x i i i 贵州大学博士学位论文 d o c i d r a ld i s s e r r 仰o n 在本文的最后，我们介绍了复杂网络理论在电子电路与微电子学方面结合 实际的可能应用。重点对目前引起了广泛研究兴趣，并成为最新研究热点的量 子相干网络、纳米线网络等作了简要介绍。 复杂网络的研究才刚刚起步，既方兴未艾，又在迅速发展。因此，许多的 理论和方法还在探索与发展之中。本文所描述的研究工作也是阶段性的。对其 中一些课题，例如：复杂网络理论在大规模电路、量子相干网络、纳米线网络 等等中的理论应用与实践，还处于探索之中。这些问题将作为我们今后研究工 作主要努力的方向。 3 研究的目的和意义 ( 1 ) 研究的目的 用非平衡统计理论来研究复杂网络稳定性，一方面是要找到更优化的控制 方法使网络达到稳定的定态点，提高控制效率；另一方面，是要找到网络突发 事件的定量描述机理，控制突发事件的发生或减少突发事件所造成的损失。研 究网络病毒传播的过程中的动态行为和动力学机理，是为在真实网络的传播过 程中，探索更简单有效的免疫策略和方法。 ( 2 ) 研究的意义 从认识论的角度来看，通过对复杂网络动力学稳定性的研究，可以使人们 对自然和社会中各种复杂网络的整体性质、复杂动态行为有更加清晰和深入的 理解与认识，了解自然与社会、认识自然与社会是科学研究的最主要的目的。 从理论上来说，本课题的研究成果，一方面将使复杂网络的理论得到进一 步的丰富和发展：另一方面，也将使非平衡统计理论得到进一步的丰富与扩展。 从应用层面看，可以将复杂网络研究的理论成果应用到具体问题当中去， 为网络优化设计、稳定控制、优化免疫机制与策略提供理论基础与指导。 4 、课题来源 x i v 首 吉 ( 1 ) 本人承担的贵州省科技基金项目：复杂网络的稳定性、动力学与统计行为 研究( 合同号：黔科合j 字 2 0 0 6 1 2 0 0 6 ) 。 ( 2 ) 国家自然科学基金资助项目，基金号：1 0 3 4 7 0 0 3 ，参与导师项目。 ( 3 ) 国家自然科学基金资助项目，基金号：1 0 6 4 7 0 0 5 ，参与导师项目。 ( 4 ) 贵州省教育厅自然科学基金重点项目：复杂网络的稳定性与安全性研究( 基 金号：2 0 0 5 1 1 5 ) ，参与导师项目，第二研究者。 ( 5 ) 本人承担的贵州省教育厅自然科学基金重点项目：非平衡复杂网络的统计 行为研究( 合同号：黔教科( 2 0 0 7 ) 0 0 6 ) 。 t 州大学博士学位论文 d o ( 1 _ ；0 r a ld i s s e r ，i 仰o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究曾做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名：l 巍眙勺李 l ) 一j 一 日期： 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅扣借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 者签桦雌爱雄 幂1 幸蔓杂目蝽蚝计 量与模i 第1 章复杂网络的统计参量与模型 1 1引言 自然界和人类社会中广泛存在着复杂系统，而复杂网络( c o m p l e xn e t w o r k ) 正是描述各类复杂系统的十分有效的理论和工具。近年来。复杂网络的研究受 到了来自科学和工程各个领域研究人员的广泛关注，已经成为非常活跃的一个 研究热点( b a r a b a s i 等，2 0 0 2 ：w a t t s ，2 0 0 4 ) 。 常见的复杂网络有i n t e r n e t 、w w w 、通信网、电力网、v l s i 电路与系 统、航空网、科研合作网等等。图1 1 一图14 是一些典型的复杂网络。 粼赢 量燃鼍吲恻剐 图l _ 1 复杂网络结构图本图取自文献( ra l b e r t 2 0 0 2 图12 复杂阿络结构图： a ) 为一个淡水湖中生物的食物链两绍；伯) 为某一研究机构科学家协作网络； c ) 为人类个体之间的性关系网络。本图取自文献( mejn e w m a n 2 0 0 3 ) 1 盘刍嚣盎+ i s 。黧编产 幽l3 复杂网络结构崮：两种数字逻辑电路结构( f e r r e r i 等2 0 0 恻j4 复球网络结构幽：一种模拟电视机电路结构( f e r r e r i 等2 0 0 从这些例子可以看出，复杂网络是对真实复杂系统的高度概括和抽象，是 包含了大量个体以及个体之叫相互作用的系统。它把复杂系统中的某种现雾或 某类实体抽象为节点( n o d eo fv e r t e x ) ，把个体之问的相互作用抽象为边( e d g c s ) ， 从而形成了用来描述这一系统的图。这样的图，是对系统模型化的抽象与表达， 2 第1 章复杂网络的统计参量与模型 它的结构特征和性质可以用一组简要的统计参量来进行刻画。另外，一个合适 的动力学模型可能十分有益于理解网络系统为什么具有这些共性。 现实世界的复杂系统经常通过模型来抽象和简化，复杂网络模型就是其中 一种，它使得我们可以更好地理解系统中事物间的关系。复杂网络中的节点可 以代表人、计算机、城市、电子元件等任何事物；边( 连线) 则表示节点之间 的关系，例如，两个人相互认识，两台计算机可以通信，两个电子器件相互连 接等等。复杂网络模型在很多科学领域都得到广泛的应用。在复杂网络模型中， 我们抛开了具体的技术层面的一些细节，如节点的大小、形状和位置、边的物 理距离、几何形状等。我们把复杂网络不依赖于节点的具体位置和连线的具体 形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结 构。 由于现代计算机和通讯网络技术的发展，1 9 9 8 年以来复杂网络的研究进入 了一个新阶段，注意力转到大量的顶点( 几十万到上百万个) 和边构成的大规模 网络的统计性质。相应地，研究方法除传统的随机图理论等方法外，更多地转向 了采用统计物理学、凝聚态物理学等学科的各种方法( a e l b t e r 等，2 0 0 2 ) ，这 种趋势必然会对各个具体网络系统的研究产生影响。 在这一章里，我们将简要回顾复杂网络理论的发展历程，然后介绍一组描 述复杂网络的常用统计参量，最后再回顾复杂网络的几个主要的动力学模型。 1 2 复杂网络及其发展 公认的复杂网络的研究，最早可以追溯到1 8 世纪欧拉( e u l e r ) 开创的图 论，它起源于著名的哥尼斯堡七桥问题。1 8 世纪在东普鲁士的首都哥尼斯堡( 今 俄罗斯加里宁格勒市) 市的普莱格尔河上建有七座桥，将河中间的两个岛和河 岸连结起来。城中的居民常沿河过桥散步，于是人们提出了一个问题：能否每 座桥都只走一遍，最后又回到原来的位置。这个看似简单的问题，却经过若干 次的尝试后都没有成功。1 7 3 6 年大数学家欧拉用一种独特的方法，解决了这个 3 ：黝纛。盖萎赢 问题。他首先把这个问题简化，用a 、b 、c 、d 四个点表示陆地和小岛，把连 接陆地和小岛的七座桥看成这四个点之间的连线，如图11 所示。这样就把问 题简化成：能不能用一笔把这个图形画出柬。仔细分析后欧拉发现，每个点必 须对应着进去和出柬的边，因此，每个点连接的边数应该为偶数才能一笔画成。 而图l _ 1 中，每个点都连接着奇数条边，所以，不可能每座桥只走一遍，最后 回到原来位置。欧拉证明了这个问题没有解。这种独特的方法是把问题只用点 和线束抽象，最后相当于得到了一个图。欧拉把这个问题作了推j “，并给出了 对于一个给定图可以某种方式走遍的判定方法，从此开创了图论研究先河。在 随后的近两百年