（无线电物理专业论文）复杂网络的拓扑、动力学行为及其实证研究.pdf

华东师范大学博士论文论文摘要 论文摘要 复杂网络近年来在国内外掀起了研究的热潮，受到来自科学与工程各个领域 研究者的强烈关注。复杂网络可以用来描述从技术到生物直至社会各类开放复杂 系统的骨架，而且是研究它们拓扑结构和动力学性质的有力工具。因此人们致力 于研究、揭示节点数众多、连接结构复杂的实际网络的整体特性，特别是网络拓 扑结构与功能之间的关系、与网络动力学行为之间的关系、结构与功能的形成机 制、演化规律等。 本论文从现实网络中寻找了航空网络、电路网络、科技文章下载网等三个典 型的非线性复杂网络系统作为实证研究对象，结合应用图论和拓扑学、非线性科 学、现代统计物理学、工程技术上的网络设计原理等现代科学理论，对复杂网络 的特殊性和普适性进行了深入的研究；探讨了网络结构与功能之间的关系，如网 络的拓扑结构与网络的容错能力之间的关系：并分析了复杂网络在动态演化期 间，其拓扑特性和动力学性质随时空变化而展示的复杂行为。通过对复杂网络动 力学性质的研究，不但可以更好地了解和解释真实网络所呈现的各种复杂动力学 现象，而且可以建立更真实反映现实世界网络特性的模型，可以设计一个具有良 好性能的网络，使得网络理论为我们所用。 本文的主要研究内容和创新点有以下几方面： 1 以一个特定航空公司( 奥地利航空公司) 的航空网络作为有向加权网络 的典型代表，对其小世界性、无标度性作了全面细致的分析；模拟计算了加权网 络中重要的统计特征量；以一周航班信息的实时数据为基础，深入研究了航空网 络中节点和权重的演化规律及演化机制模型，讨论了网络的关联动力学性质及其 演化，为修改经典含权演化模型( b b v 模型) 的假设条件提供了必要的基础， 使之与真实系统更加接近。在上述工作的基础上，我们发现了该航空网络与众不 同的统计复杂行为：( 1 ) 奥地利航空网的度度相关性特征表现出无论k 值为多 少，均是明显的负相关匹配特征，即大机场更明显地倾向与较小机场相连。( 2 ) 簇度相关性表明在k 7 时奥地利航空网络没有明显的层次结构，仅在娩7 时才具 有层次结构。对于这种具有层次拓扑结构的网络形成机制无法用e r 随机模型和 b a 无标度模型解释，因为它们不包含有利于模块涌现的机制。因此，我们的实 证结果对建立既能再现层次性，又考虑几何效应的新网络演化模型具有借鉴意 华东师范大学博士论文论文摘要 义。 2 电路网络的有效设计在很大程度上依赖元件组之间的连接是否采用了不 同的短连接，因此电路网络比其他真实系统更接近w s 小世界模型。本文的研究 工作在国内首次把复杂网络理论应用于一个系统级的无线接收机电路的分析中， 对电路网络的拓扑结构特征、元器件节点及其对应的连接度函数关系、元器件节 点连接度的概率分布函数曲线等进行了模拟计算和讨论：分析了网络连接度分布 的统计特性，确认连接度分布是一个带有指数截断的幂律分布，不同于典型的 b a 无标度网络模型，并分析了造成这种网络演化结构的可能原因。从电路设计 的角度说明了我们需要使用不同的短距离连接和集成电路把各个单元模块电路 集成在一起，即物理设计要达到最优化，电路使用元件最少，连线简捷。此外， 运用统计物理学的逾渗理论和网络攻击策略对电路网络在遭受随机故障及蓄意 攻击时拓扑结构所发生的变化进行了模拟仿真和计算，进一步分析了电路的动力 学行为一鲁棒性和脆弱性之间的关系，可为电路的优化设计提供理论指导。 3 本文把科技文章下载网看作演化网络的原型，对它的动力学和演化机制 进行重点研究，为整个信息网络结构研究提供了支持，这是一项创新性的尝试。 在分析文章下载网的下载频率分布是否具有无标度幂律现象时，本文从z i p f 定 律、p a r e t o 幂律分布定律和t s a l l i s 熵等三个不同角度进行了研究。该研究思想 是复杂领域研究中从未有过的，因此在我们发表了这方面的研究成果之后，陆续 有学者沿用了这种思想。进而，本文又研究了该下载网络在三年期间节点流量随 着时间变化所表现出的复杂动力学行为，并分析了普遍存在于宏观世界和微观世 界中的涨落尺度现象，对其是否具有两个普适分类( 即a = 1 2 和a = 1 ) 进行了讨论， 发现平均下载率( 厂) 与文章等级呈现出快速指数衰减关系，而方差与文章等级却 没有明显的函数关系。下载率分布的方差。与平均流量( ，) 满足幂律尺度行为， 即o ( 厂) 4 。尺度参数a 随时间窗变化，从0 6 0 变化n 0 8 9 。并以m e n e z e s 和 b a r a b a s i 提出的外部驱动模型和一个简单的流量模型对涨落形成机制进行了解 释。 关键词：拓扑结构，动力学行为，实证研究，电路网络，航空网络，文章下载 网络，涨落尺度 华东师范大学博士论文 a b s t r a c t a b s t r a e t c o m p l e xn e t w o r k sh a s s e to f far e n a i s s a n c eh o m ea n da b r o a di nr e c e n t y e a r s s c i e n c ea n de n g i n e e r i n gr e s e a r c h e r sf r o md i f f e r e n ta l e a , sa r ca l l h a v e s t r o n g ( ：o i l c e r l l _ t oi t c o m p l e xn e t w o r k sc a nb eu s e dn o to n l yt od e s c r i b et h es k e l e t o no f v a r i o u sn e t w o r k ss u c ha st e c h n o l o g y , b i o l o g ya n dc o m p l i c a t e ds o c i a ls y s t e m , b u t a l s oap o w e r f u lt o o lo fs t u d y i n gt h e i rt o p o l o g i c a ls t r u c t t t r ea n dd y n a m i cb e h a v i o r s r e s e a r c h e r sf o c u s0 1 3 t h eg e n e r a lc h a r a c t e r i s t i c so ft h ea c t u a ln e t w o r kw h i c hh a v e h u g en o d e sa n de o m p l i c a t c ( 1c o n n e c t i n gs t r u c t u r e ，p a r t i c u l a r l yt h er e l a t i o n s h i p b e t w e e nn e t w o r kt o p o l o g ya n di t sf u n c t i o n , i t sn e t w o r kd y n a m i c sb e h a v i o r , i t s f o r m a t i o nm e c h a n i s mo f t h es t r u c t u r ea n df u n c t i o na n di t se v o l u t i o r t , e c t t h i st h e s i ss e l e c t e dt h r e et y p i c a ln o n l i n e a rc o m p l e xn e t w o r k sf r o ma c t u a l n e t w o r k s ：a i r l i n en e t w o r k , e l e c t r i c a lc i r c u i tn e t w o r k , t h es c i e n c ep a p e rf o rd o w n l o a d n e t w o r k w ec a r r i e do u ti n - d e p t hr e s e a r c h0 1 3 t h eu n i v e r s a la p p l i c a t i o na n d p a r t i c u l a r i t yo fc o m p l e xn e t w o r k , c o m b i n e d 、 i 也g r a p ht h e o r y a n dt o p o l o g y , n o n l i n e a rs c i e n c e ，m o d e ms t a t i s t i c s p h y s i c sa n dn e t w o r kd e s i g np r i n c i p l e s o f e n g i n e e r i n gt e c h n o l o g y w ed i s c u s s e dt h ec o n n e c t i o no ft h en e t w o r k ss t r l 1 c t u ma n d i t sf t m e t i o n , s u c h t h er e l a t i o nb e t w e e nn e t w o r kt o p o l o g ya n dn e t w o r kt h ef a u l t t o l e r a n c ec a p a b i l i t y w ea n a l y z e dt h ec o m p l e xb e h a v i o r sw h i e l ad i s p l a y e d a c c o r d i n g t ot h ec h a n g e so ft h en e t w o r k st o p o l o g ya n dd y n a m i cc h a r a c t e r i s t i c sd u r i n gt h e d y n a m i ce v o l u t i o np e r i o d t h er e s e a r c h 0 1 3c l r l l a m i cc h a r a c t e r i s t i c so fc o m p l e x n e t w o r kc l t nh e l pu sn o to n l yt oh a v eb e t t e ru n d e r s t a n d i n ga n de x p l a n a t i o no ft h e c o m p l e xd y n a m i c sp h e n o m e n o nw h i c ht h e r e a ln e t w o r ks h o w e d , b u ta l s ot h e f o t m d a t i o no fat r u e rr e f l e c t i o nn e t w o r km o d e l w ec a nm i l k et h en e t w o r kt h e o r yf o r o u ro w nu s et od e s i g nn e t w o r k st h a th a v eg o o dp e r f o r m a n c e t h em a i np o i n t sa n di n n o v a t i o n si nt h i st h e s i sa r ct h ef o l l o w i n g ： 1 w ec h o s eo n en e t w o r ka f f i l i a t e dw i t has p e c i f i ca i r l i n ec o m p a n y ( a u s t r i a n a i r l i n e s l 越at y p i c a lr e p r e s e n t a t i v eo fd i r e c t e d w e i g h t e dn e t w o r k w eh a d c o m p r e h e n s i v ea n dd e t a i l e da n a l y s i so fi t ss m a l lw o r l dc h a r a c t e r i s t i ca n ds c a l e - f r e e n l 华东师范大学博士论文a b s t r a c t f e a t u r e ，s i m u l a t e da n dc a l c u l a t e dt h ei m p o r t a n ts t a t i s t i c a l f e a t u r e so fw e i g h t e d n e t w o r k b a s e do nt h er e a l - t i m ed a t ao fo n e - w e e kf l i g h t s ，w eh a di n - d e p t hs t u d yo n t h em e c h a n i s ma n de v o l u t i o nm o d e lo fa l r l m en e t w o r k sn o d e sa n di t sw e i g h t s w e d i s c u s s e dt h ed y n a m i c so f t b en e t w o r ka n di t se v o l u t i o nw h i c hp r o v i d e dt h en e c e s s a r y b a s i st oa m e n dt h ea s s u m p t i o no f t h eb b vm o d e li no r d e rt oc l o s e rt ot h er e a ls y s t e m o nt h ef o u n d a t i o no fa b o v em e n t i o n e dw o r k , w ed i s c o v e r e dt h ed i s t i n c t i v es t a t i s t i c a l c o m p l e xb e h a v i o ro ft h i s a i r l i n en e t w o r k ：( 1 ) t h ed e g r e e - d e g r e ec o r r e l a t i o no f a u s t r i a sa i r l i n es h o w e dt h a t n om a t t e rh o wt h ekv a l u ew a s ，i td i s p l a y e dt h e n e g a t i v ec o r r e l a t i o nm a t c h i n gc h a r a c t e r i s t i co b v i o u s l y , t h a ti s t os a y , t h e s ek e y a i r p o r t st e n d e dt ol i n k w i t ht h es m a l l e ra i r p o r t s 。( 2 ) t h ec l u s t e r - d e g r e ec o r r e l a t i o n i n d i c a t e dt h a ti nk 7c i r c u m s t a n c e s ，a u s t r i aa i r l i n en e t w o r kh a dn oc l e a rh i e r a r c h y o n l y k 2 7 ，i th a dh i e r a r c h i c a ls t r u c t u r e s u c han e t w o r kt o p o l o g ym e c h a n i s m w h i c hh a dl a y e r e dt o p o l o g yw i t he rr a n d o mm o d e la n db as c a l e - f r e em o d e lc o u l d n o tb ee x p l a i n e da st h e yd on o tc o n t a i nm e c h a n i s m sc o n d u c i v et ot h ee m e r g e n c eo f m o d u l e s t h e r e f o r e ，o u re m p i r i c a lr e s u l t si sau s e f u le f f o r tn o to n l yf o rr e a p p e a rt h e h i e r a r c h yb u ta l s of o r t h en e wn e t w o r ke v o l u t i o nm o d e lw h i c hc o n s i d e r e dt h e g e o m e t r i c a le f f e c t 2 a ne f f e c t i v ed e s i g no fe l e c t r i c a lc i r c u i tn e t w o r kd e p e n d so nw h e t h e rt h e r ea r e d i f f e r e n ts h o r tc o n n e c t i o n sb e t w e e nt h ec o m p o n e n tg r o u p st oal a r g ee x t e n t t h e r e f o r e ， t h ec i r c u i tn e t w o r ki sc l o s e rt ot h ew sm o d e lc o m p a r et oo t h e rr e a ls y s t e m s o u r r e s e a r c hi st h ef i r s to n ei nc h i n at h a ta p p l i e dt h ec o m p l e xn e t w o r kt h e o r yt oa n a l y z ea s y s t e m l e v e lw i r e l e s sr e c e i v e rc i r c u i tn e t w o r k w ed i s c u s s e dt h et o p o l o g yo fc i r c u i t n e t w o r ka n dt h ef u n c t i o no fi t sc o m p o n e n t s a tt h es a m et i m e ，w es i m u l a t e da n d c a l c u l a t e dt h ep r o b a b i l i t yd i s t r i b u t i o nf u n c t i o nc u r v e so fc o m p o n e n t s w h a t sm o r e ， w ea n a l y z e dt h es t a t i s t i c a lp r o p e r t i e so fn e t w o r k sc o n n e c t i n gd e g r e e sd i s t r i b u t i o n , c o n f i r m e dt h a ti ti sa l li n d e xp o w e rl a ww i t hc u t - o f fw h i c hu n l i k et y p i c a lb a s c a l e f r e en e t w o r km o d e l t h e n , w ea n a l y z e dt h ep o s s i b l er e a s o n st h a tc a u s e dt h i s n e t w o r ke v o l u t i o n w en e e dt ou s ed i f f e r e n ts h o r t - r a n g ec o n n e c t i v i t ya n di n t e g r a t e d c i r c u i t si ni n t e g r a t i n g “lm o d u l e s t h a ti st os a y , t oa c h i e v et h eo p t i m i z a t i o no f p h y s i c a ld e s i g n , t ou s et h el e a s tc i r c u i tc o m p o n e n t s a n dt os i m p l i f yc o n n e c t i o n i n 华东师范大学博士论文a b s t r a c t a d d i t i o n , w es i m u l a t e da n dc a l c i l 】删t h ec h a n g e so ft o p o l o g yw h e nt h ec i r c u i t n e t w o r kf a c e dt h er a n d o mf a i l u r e sa n dd e l i b e r a t ea t t a c k sb yu s i n gp e r c o l a t i o nt h e o r ) r i ns 诅t i s t i c a lp h y s i c sa n ds t r a t e g i e si nn e t w o r ka t t a c k d ot h ef u r t h e ra n a l y s i so ft h e r e l a t i o n s h i pa m o n gt h ed y n a m i cb e h a v i o r , t h er o b u s t n e s sa n dt h e 舰i i 咄a c c o r d i n g t ot h ea b o v e ，w ep r o v i d et h e o r e t i c a lg u i d a n c et oo p t i m a lc i r c m td e s i g n 3 w et r e a t e dt h es c i e n c ep a p e rf o rd o w n l o a dn e t w o r ka sap r o t o t y p eo fe v o l u t i o n n e t w o r k sw h i c hi sa ni n n o v a t i v ea t t e m p t , f o c u s e do ni t sd y n a m i c sa n de v o l u t i o n m e c h a n i s m s i ts u p p o r t e dt h es t u d yo ft h ee n t i r ei n f o r m a t i o nn e t w o r k ss t r u c t u r e t h r g ed i f f e r e n ta n g l e sw e r eu s e di nt h ef r e q u e n c yd i s t r i b u t i o no fa r t i c l e sd o w n l o a d n e t w o r k w h e t h e ri th a dp o w e r - l a wa n ds c a l e f x e ep h e n o m e n a , t h o s ew e r ez i p f f sl a w , p a r c t o sp o w e r - l a wd i s t r i b u t i o nl a wa n dt s a l l i se n t r o p yt h e o r y t h et h o u g h tn e v e r a p p e a r e di nt h ea r e ao fc o m p l e xn e t w o r kr e s e a r c h a f t e rw ep u b l i s h e dt h er e s u l t so f r e s e a r c ho nt h i sa r e a , m a n yo t h e rs c h o l a r sm a d er e f e r e n c e t h e n , w ea l s oc o n s i d e r e d t h ec o m p l e xd y n a m i cb e h a v i o ro fd o w n l o a dn e t w o r ks h o w e db yn o d e st l b 币ci na t h r e e y e a rp e r i o d , a n da n a l y z e dt h ef l u c t u a t i o ns c a l ep h e n o m e n at h a ti sc o m m o n l y f o u n di nb o t hm a c r o s c o p i cw o r l da n dm i c r ow o r l d w ed i s c u s s e dt h eu n i v e r s a l c l a s s i f i c a t i o n ( t h a ti s ，a = 1 2a n d 口= 1 ) ，f o u n dt h a tt h ea v e r a g ed o w n l o a dr a t et h e g r a d i n gv a r i a n c ew e r ei nt h er a p i de x p o n e n t i a ld e c a yw h i l et h ev a r i a n c et h eg r a d i n g v a r i a n c eh a dn oo b v i o u sr e l a t i o n s t h ev a r i a n c eoo ft h ed o w r d o a dr a t ed i s t r i b u t i o n m e t 谢也t h ea v e m g ef l o w ( ，) 。fp 。w e r - l a ws c _ 如d a r d s ，t h a ti s ，。芘( ，) 4 s c a l e p a r a m e t e rc h a n g e dw i t ht h et i m ew i n d o w , f r o mo 6 0 t o0 8 9 w ee x p l a i n e dt h e f o r m a t i o no ff l u c t u a t i o nm e c h a n i s mb yu s i n gb a r a b a s ia n dm e n e z e s e x t e m u l d r i v i n gm o d e la n das i m p l ef l o wm o d e l k e yw o r d s ：t o p o l o g y , d y n a m i c a lb e h a v i o r , e m p i r i c a lr e s e a r c h , e l e c t r i c a lc k c m t n e t w o r k , a i r l i n en e t w o r k , s c i e n c ep a p e rf o rd o w n l o a dn e t w o r k , f l u c t u a t i o ns c a l i n g v 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：盟塾虚日期：羔1 2 三 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：鄂庭定 导师签名： 籼懈纫 伽。7 ：限7 华东师范大学博士论文第一章绪论 第一章绪论 h l t e m c t 和w w w 也许是自人类有文明以来最有影响力的创造。它对我们的 影响无处不在，它是我们生活环境的一部分。离开它，我们现在和将来的生活将 不可想象。然而，我们对它的了解远小于客观的预测：对于它的结构、复杂的组 织形式，全局的拓扑结构和局部的特性我们都知之甚少。而这方面的知识对充分 发挥i n t e m e t 和w w w 这两种通信信息网的功用和确保i n t c m e t 的安全来说，却 是十分重要的。 事实上，这些令人惊叹的通信网络仅仅是网络演化过程中出现的几个特殊的 例子，此外还有很多类型的网络，比如科研合作网络、人际关系网络、科学引文 网络、大型电力工业网络、全球交通网络、企业和金融机构网络、电话网络、生 物种群网络、食物链和生态网络等等，可以说，人类已经生活在一个充满着各种 各样的复杂网络的世界中。人类社会的“网络化”既给我们带来了极大的便利， 提高了人类生产效率和生活质量，但又给我们的生活带来了一定的负面冲击，如 传染病的流行、计算机病毒在i n t e r i l e t 上的快速传播、局部故障触发大面积的停 电事故等。因此，人类社会的日益网络化需要我们对各种人工和自然的复杂网络 行为有更好的认识。长期以来，通信网络、技术网络、社会网络和生物网络等分 别是通信科学、技术科学、社会学和生物学等不同学科的研究对象，而复杂网络 理论所要研究的是以上种种真实网络之间的共性和处理它们的普适方法。从2 0 世纪末开始，复杂网络的研究逐步渗透到数理学科、人文学科、工程学科、生命 学科等众多不同的领域，对复杂网络的定量及定性特征的科学理解，已成为网络 时代研究工作中极其重要的挑战性课题，甚至被称为“网络新科学( n e w i e n c e o f n e t w o r k s ) ”。【1 ，2 】 随着近年来大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网 络的研究进程大大加快，人们对社会系统、大型基础性设施和生物系统中大量的 真实网络数据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现 支配和影响这些复杂系统的动力学和演化规律的内在本质。复杂网络的理论及实 证研究的发展将会对网络安全、网络控制、疾病传播的控制与防御、社会活动中 人的行为动力学的研究、生物网络的演化机制的研究等产生重要影响。 华东师范大学博士论文第一章绪论 本章首先对复杂网络的发展及其研究内容、研究意义与面临的挑战作一个简 要的回顾；然后对全文的研究内容及各章节的组织结构作一概括。 1 1复杂网络的发展 复杂网络借助于图论和统计物理的一些方法，结合不同学科的特点，捕捉并 描述系统的演化机制、演化规律( 拓扑结构) 和整体行为( 功能) ，这是复杂网络的 研究蓬勃发展的重要原因之一。 自然界的许多复杂系统都可以用网络来描述。一个典型的网络是由许多节点 与连接两两节点之间的一些边所组成的，其中节点用来代表真实系统中不同的个 体，而边则用来表示个体间的关系。相邻节点是指具有某种特定关系连上一条边 的节点，非相邻节点则指无边相连的两个节点。例如，科技文章下载网中，节点 和边分别表示被下载的文章和u i 也链接；在航空网络中，节点表示机场，边表 示机场之间的航班；电路与系统网络中，节点表示电子元器件，边表示连接器件 的导线等等。图1 1 和图1 2 是一些典型的复杂网络图。 ：= 2 = 2 ：= = = ：嚣怒r 。一“。一一“一。一“。“ 图l0 1 毒品使用者网络：最大连接元素的结构和形状。节点聚集成三个主要的种族群 具体分析见参考文献【4 】。 2 华东师范大学博士论文第一章绪论 f i l e 【0i 单r 州咖眦唧i o2 0 0 0 t k r 叫s a m 口一l d 衄 ) 岫r t ，m ，删弼硼o f _ - 嘲啦c 内嘶蛙埔日d _ o k b t 印即旺h 叫世胛如一瞄l 佃) e i t 咖d - 呻玛呻譬咖柚。r 岫叩_ 啪s m 自e r 口d 肿眦- 曲t 柚耐脚n m 瞻 图1 2 ( a ) 短尾猿大脑皮层的侧面图，图中各标号表示每个区域的近似位置； ( b ) 大脑皮层网络中的连接。图摘自文献【5 】 现实网络系统的拓扑结构看上去错综复杂，极其混乱( 图1 1 ，图1 2 ) ，而 且网络拓扑结构可能随时都会发生变化；网络演化导致网络节点不断增加，节点 间的连接也在不断地增长，且连接之间存在着多样性；网络的动力学具有复杂性， 每个节点本身可以是非线性系统，具有分岔和混沌等非线性动力学行为而且在不 停地变化。这就是网络系统的复杂性。 由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知 或未曾探索【6 。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个 阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些 规则的图( 经典图论所考虑的) 来表示，例如二维平面上的欧几里德格网：2 0 世纪5 0 年代末到9 0 年代末，两位匈牙利数学家p a u le r d o s 和a l f r e dr e n y i ( e 鼬 在图论领域做出了一个重要突破，即在文献 7 9 】中提出的随机图理论。他们用随 机图来描述网络的拓扑结构，这为复杂网络的研究奠定了一个数学理论基础。随 机图的思想主宰复杂网络研究达四十年之久；直到最近几年，科学家们发现大量 的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计 特性的网络，其中最有影响的是小世界( s m a l lw o r l d ) 网络和无标度( s c a l e f r e e ) 网络。这两种网络的发现是复杂网络研究领域的重要进展。之后，在上述两项重 要发现的推动下人们又相继提出了多种复杂网络模型，并研究了其相关性质。从 而掀起了一股研究复杂网络的热潮。 华东师范大学博士论文第一章绪论 1 2 复杂网络的研究概况 1 2 1 复杂网络的研究内容 继二十世纪末复杂网络的小世界特性及无标度特性的发现之后，有关复杂网 络的各种研究方兴未艾，一方面是新的理论模型和新的分析方法不断地涌现；另 一方面在现实网络中不断发现新结构与新现象，研究者们希望从复杂网络的角度 来观察、理解和解决具体领域的问题。概括说来，复杂网络的研究主要集中在以 下几个方面； 一、复杂网络的实证研究，分析真实网络的统计特征 不论是现实世界中具体网络的研究，还是模型的理论分析、仿真分析，描述 复杂网络统计特征的基本参量：度与度分布、聚集度、簇类系数以及平均路径长 度等都是研究的焦点之一。在此基础上，进一步探索它们之间的相互关系，试图 认识、掌握各种内在的规律。 二、复杂网络的建模研究 通过生成算法构建符合真实网络统计性质的网络演化模型，模仿真实网络的 行为，再现真实网络的几何特性。 最初的w a t t s s t r o g a t z 小世界网络模型和b a r a b a s i a l b e r t 无标度网络模型及 以b a 模型为典型代表的一大类演化模型可以较好地解释无标度网络的形成机 制，也能在现实世界的网络中印证其模型一定程度的合理性，但是它对于真实网 络来说过于简化。因此建立合适的网络模型，帮助人们理解这些统计性质的意义 和产生机理仍然是目前的一个重要研究方向。 三、复杂网络的动力学行为研究 通过把复杂网络看成动力系统或在复杂网络中引入动力学单元，很多研究者 对复杂网络的动力学行为展开了研究：如复杂动态网络的鲁棒性和同步能力，特 别是混沌动力系统在网络上的同步性能吸引了大量科学家的关注；网络的拥塞及 疾病、信息和知识在复杂网络上的传播；小世界网络中的自组织临界现象，网络 拓扑结构是否会影响沙堆模型中的自组织临界现象，一直以来是该领域争论的焦 点；小世界网络中的湍流、小世界振荡器网络中的振荡消失现象，小世界网络中 的随机共振等；复杂网络的控制问题等。 4 华东师范大学博士论文第一章绪论 在复杂网络动力学性质的研究中，网络的拓扑结构如何影响网络的动力学性 质是一个研究的热点。 四、复杂网络的应用研究 虽然复杂网络的研究尚处于起步阶段，但随着社会和技术的发展，研究者们 依然针对不断涌现的应用问题，用复杂理论解决这些具体问题，迄今已发现了很 多潜在的有趣的应用。例如m i c r o s o f t 的复杂网络计算小组，结合网络虚拟社群、 即时通讯交流软件，研究社会关系网络的演化动力学；i b m 研究中心的协同用户 体验设计小组，研究多用户的非线性协作问题、社会关系网络分析在知识管理中 的应用等问题；复杂网络鲁棒性的研究成果应用于网络拓扑优化设计；网络同步 问题的研究可在移动通信领域中发挥作用；复杂网络稳定性的研究，对于互联网、 电力网 1 0 ，1 1 、航空网 1 2 ，1 3 等技术网络的设计保护及基础设施网络的保护 1 4 具有重要的意义，也可以有效地防止黑客侵入互联网、阻止病毒在万维网上 传播蔓延 1 5 ，1 6 ；现实复杂网络中的语言网的小世界特性可以部分地解释人脑 具有很快的联想功能等 1 7 ；w w w 特殊的复杂结构使人们可以提出相应的搜索算 法，为获取所需信息提供方便 1 8 ；小世界的思想用于b p 网络 1 9 ，可以减少 b p 网络的学习时间和学习误差，使得b p 网可以更好地用于数据挖掘、语音识别、 图像处理及模式识别等多个领域；复杂网络用于h o p f i e l d 网络 2 0 ，2 1 ，可以改 变神经网络的联想记忆功能。 可以预见，随着复杂网络领域研究成果的不断涌现，对这些成果的应用也将 成为今后研究的一个主要方向。 综上所述，复杂网络的理论需要不断地完善，大量真实网络的拓扑结构需要 进一步地实证研究，层出不尽的应用问题的研究需要逐步展开。复杂网络的研究 正处在方兴未艾的阶段，还有很多前沿性的研究方向需要我国科学家做出一些原 创性的成果，如控制计算机病毒传播的目标防御策略和扼杀策略的数据和模型支 持及实证分析；利用同主题的万维网来研究个人关系网络；社会网络中的身份和 查询；无标度网络系统的阻塞有限性；寻找社会网络的基本构造单元，即社会网 络的基序；复杂网络的容错性和抵御攻击性能等等。 华东师范大学博士论文第一章绪论 1 2 2 复杂网络的研究意义 复杂网络作为复杂系统的一种抽象和描述方式、作为复杂系统的结构形态， 它突出强调了系统结构的拓扑特征。可以说，任何复杂系统都可以当作复杂网络 来研究。以复杂网络形式研究复杂系统，可以加深人们对系统结构的深入了解， 随着复杂网络研究的深入以及用网络理论研究系统演化工作的深入开展，复杂系 统演化的研究必将出现新的突破性成果。因此，复杂网络的研究，为我们提供了 一种复杂性研究的新视角、新方法，并且提供了一种比较的视野。可以在复杂网 络研究的旗帜下，对各种真实网络进行比较、研究和综合概括。复杂网络涉及 到很多交叉学科，其中包括复杂性科学、非线性科学、电路与系统、计算机科学、 控制理论、理论物理、数学、生物学等多个学科领域。为什么对复杂网络的研究 会引起各个学科领域的广泛兴趣呢? 因为对复杂网络的研究无论在理论上还是在 应用中都有重要意义。 首先，网络的现象涵盖极其广泛，因此，对网络的研究有普遍意义。例如， 科学家发现大多数实际的系统都是复杂网络，从细菌、细胞和蛋白质系统，到人 类性关系，甚至到科学家之间的合作、论文之间的引证联系、大型的i n t e r n e t 和w w w 网络等，它们都遵循某种网络关系，也构成某种复杂网络系统。因此，如 若发现一种概括它们的共同特性的观点和方法，则能够攫取这类网络的关键，形 成深入的认识。而复杂网络研究恰恰在这点上发现了各种真实网络同时都具有的 三个主要特征：小世界、无标度性和高聚集度。 其次，复杂网络的研究，在大量网络现象的基础上抽象出两种基本复杂网络： 即小世界网络和无标度网络。这两种网络都同时具有两个基本特征：高平均集聚 程度、小的最短路径，而无标度网络的度分布又具有幂律分布特征。因此无标度 网络的复杂性程度还高于小世界网络的复杂性程度。高平均集聚程度反映了事物 在小世界的境况下白发走向有序的态势；小的最短路径特征反映了演化速度快的 特征。系统的低层次的因素之间的局部交互作用会更密集。作用会更频繁，在系 统层次会涌现出更多的性质。例如，在w a t t s 和s t r o g a t z 文章研究的传染病模 型中，其接触传染率为1 ，感染的顶点( 可能是个体的人) 在一个单位时间以后 退出系统。对于任何网络，这样的传染病都将在整个网络扩散。研究其扩散时间， 发现对于从规则网络到随机