（物理电子学专业论文）复杂网络上动力学系统的同步研究.pdf

北京邮电大学硕士学位论文 复杂网络上动力学系统的同步研究 摘要 近几年来，对复杂网络的特征以及拓扑结构对动力学行为的影响 的探索已成为网络时代极为重要的课题。历史上，人类从来就没有停 止过与复杂网络打交道。从简单的人际关系网络到复杂的社会分工及 其组织网络，从自然界的食物链网络到人类自身的细胞网络。自上世 纪八十年代以来，信息科技的高速发展使人类进入了真正意义上的网 络时代。因特网，电信网络的迅猛发展，大大促进了社会，经济，科 技等各个方面的发展。人类社会的网络化在给我们的生活带来极大便 利的同时也带来了一定的负面效应。因此，对于目前人类社会以及自 然界中的复杂网络的研究是非常必要的。 同步的研究也具有悠久的历史，物理学界中对同步的研究的最早 记录是惠更斯对同一个横梁上的两个钟的摆动。在日常生活中，同步 现象是很普遍的。今天，同步在网络系统，通信系统，激光系统等领 域起着重要的作用。然而同步也也是一把“双刃剑”，当大量人马同 时过桥时，不能齐步走动；因特网中的同步也会造成网络堵塞等现象。 事实上，大量看似巧合的同步行为都可以用数学以及物理的方法进行 理论的解释。复杂网络理论中的小世界和无标度规律的发现之后，人 们开始结合复杂网络以及非线性科学中混沌同步的研究，探讨复杂网 络中的非线性动力学，特别是混沌同步的科学规律。本文主要研究了 复杂网络上的拓扑结构和网络上的动力学过程及其两者的关系。 本论文研究的内容主要分为三个部分。首先，介绍复杂网络的一 些基本概念以及复杂网络研究的最主要的几种度量，如网络中度的概 念，最短路径的概念，聚集系数等。引出几种重要的网络模型，如随 机网络，小世界网络，无标度网络，均匀网络等几种网络模型的构造， 同时也介绍当前对复杂网络研究的进展以及建立在复杂网络基础上 的动力学过程的研究等。这些都为接下来的研究作了理论铺垫。 其次，在本文中，我们研究了复杂网络的拓扑结构及其生长过程 北京邮电大学硕士学位论文 研究，特别是以手机短信网络为代表的真实网络的生长过程；重点讨 论短信网络模型及其生长机制，主要介绍当前一些网络生长模型的演 化方式，模拟了短信网络的生长过程并研究其拓扑结构，提出了基于 局部优先连接机制的短信网络生长模型。 我们研究网络上拓扑结构的规律及其形成过程的目的就是为了 讨论并研究控制网络上的动力学过程。在引入复杂网络中的混沌同步 的概念之后，基于寻找最适合于同步的网络结构的目的，我们研究了 复杂网络中的混沌同步及其与所在的网络的拓扑结构的关系，讨论了 网络结构对同步的影响。数值模拟结果显示均匀网络最适合网络同 步，均匀网络拥有小的平均最短路径，小的集聚系数和小的网络最大 流。这种均匀网络同规则网络不同点在于，均匀网络拥有小的平均最 短路径，同时从网络上的节点观点来看，均匀网络拥有小的等级层次。 关键字：复杂网络混沌同步短信网络网络模型拓扑结构动力 学系统 北京邮电大学硕士学位论文 s y n c 的n i z a n o no ft h ed y n a n c a l s y s ，】陋 重s 玎呵t h ec o l e xn e t w o r k s i n s p i r e db yt h ec u r r e n tr a p i dd e v e l o p m e n t0 ft h er e s e a r c hf i e l do n c o n t r o l l i n gt h es y n c h r o m z a t i o no fc h a o t i co s c i l l a t o r s i nt h ec o m p l e x n e t w o r k s ，w ec a r r i e do u tt h er e s e a r c hw o r ko nt h et o p o l o g i c a lc h a r a c t e r s a n dt h es y n c h r o n i z a b i l i t yo ft h en e t w o r k sa sw e l la st h e i rr e l a t i o n s h i p s t h ep a p e rc a nb ed i v i d e di n t ot h r e ep a r t s i nt h ef i r s tp a r t ，w ed i s c u s s e dt h e r e s e a r c hb a c k g r o u n do ft h e c o m p l e xn e t w o r k st h e o r ya n d i t sf u n d a m e n t a lt h e o r y , s u c h 鹤t h e n e t w o r k s t o p o l o g i c a lp a r a m e t e r s ，t h em e a ns h o r t e s tp a t h - l e n g t h ，t h e c l u s t e r i n gc o e f f i c i e n t ，t h em a x i m a ll o a do ft h el i n ki nt h en e t w o r k s ，e t c w - ea l s od i s c u s s o ds o m eb a s i cn e t w o r k st o p o l o g i e s w h i c hh a v eb e e n w i d e l ys t u d i e da n da l s os e r v ea st h eb a s eo fo u rr e s e a r c hw o r k i nt h es e c o n dp a r t ，b a s e do nt h er e a ld a t aa b o u tt h es h o r tm e s s a g e n e t w o r k s ( s m n ) ，w ei n v e s t i g a t e dt h eg r o w i n gp r o c e s sa n dt o p o l o g i c a l f e a t u r e so fs m n o u rs i m u l a t i o n ss h o wt h a tt h en e t w o r k s d e g r e e d i s t i l b u f i o n ，a v e r a g ed e g r e ea n dt h ec o r r e l a t i o nb e t w e e nt h en o d e s d e g r e ea n di t st i m ei nt h en e t w o r ka r ed i f f e r e n tf r o mt h o s eo fp r e v i o u s n e t w o r k sm o d e l s b a s e do nt h e s ec h a r a c t e r i s t i c so fs m n w ec o n s i d e ra n e wt y p eo fn e t w o r kg r o w i n gp r o t o c o l ：l o c a l p r e f e r e n c ec o n n e c t i n g p r o t o c 0 1 t h en u m e r i c a lr e s u l t ss h o wt h a tt h en e t w o r k sg e n e r a t e df r o m o u rm o d e la r em o r er e p r e s e n t a t i v ei ns i m u l a t i n gr e a ln e t w o r k s r e p r e s e n t e db ys m nw h e nc o m p a r e dw i t ho t h e rn e t w o r k sm o d e l s i nt h el a s tp a r to ft h i sp a p e r , w es t u d i e dt h es t a b i l i t yp r o b l e mo ft h e c h a o ss y n c h r o n i z a t i o ni nd i f f e r e n tk i n d so fc o m p l e xn e t w o r k s w eh a v e s t u d i e dt h et o p o l o g i e so fd i f f e r e n tn e t w o r k sc o m p r i s i n gm a n yc h a o t i c o s c i l l a t o r s ，a n di n v e s t i g a t e d t h er e l a t i o n sb e t w e e nt h e t o p o l o g i c a l p a r a m e t e r sa n dt h es y n c h r o n i z a b i l i t yo ft h e s ec h a o t i co s c i l l a t o r sf o rt h e 北京邮电大学硕士学位论文 p u r p o s eo ff i n d i n gt h eb e s tn e t w o r kf o rs y n c h r o n i z a t i o no fc h a o t i c o s c i l l a t o r s s p e c i f i c a l l y , w es t u d i e dc h a o t i cs y n c h r o n i z a t i o ni nc o m p l e x n e t w o r k sb yu s i n ga ne v o l u t i o n a r ym o d e la n dd e v e l o p e da no p t i m i z a t i o n a l g o r i t h mc a p a b l eo fi n c r e a s i n gs y n c h r o n i z a b i l i t yo fn e t w o r k s w ef i n d t h a tw h i l et h e r e l a t i o n s h i p sb e t w e e nt h en e t w o r k s s t r u c t u r a l a n d d y n a m i c a lp a r a m e t e r sa r ec o m p l i c a t e d ，t h ew i n n e rt h r o u g ht h ee v o l u t i o n i sah o m o g e n e o u sn e t w o r ki nw h i c he a c hn o d eb e h a v e st h es a m e g e o m e t r i c a l l ya n dt o p o l o g i c a l l y t h eh o m o g e n e o u sn e t w o r kh a st h e a d v a n t a g e si nt h a tt h et r a f f i cf l o wt h r o u g ha n yn o d ei sa l m o s tt h es a m e a n di ta v o i d sh u b sa n db o u n d a r yn o d e si nt h en e t w o r k s k e yw o r d s ： c o m p l e xn e t w o r k s m e s s a g en e t w o r k s n e t w o r km o d e l s y s t e m c h a o ss y n c h r o n i z a t i o ns h o r t n e t w o r kt o p o l o g y d y n a m i c a l 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 1 1 ，一1 、 本人签名：乏塑坐日期：竺厶! ： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：塑2 ：王三三 日期：k 弘扛乒一 北京邮电大学碗士学位论文第一章引言 第一章引言 混沌的发现是2 0 世纪相继相对论和量子力学最后的物理学中最伟大的发现 之一。对混沌理论的研究为我们认识世界改造世界提供了新的思想和方法。混沌 作为一种复杂的非线性运动行为，在物理学、信息学和经济学等领域得到了广泛 的研究。因此混沌控制与混沌同步的产生就成为了历史发展的必然。从2 0 世纪 末开始，复杂网络理论正在渗透到物理学、数学、生命科学、工程学等多个不同 的学科领域。发展速度非常迅猛。复杂网络理论和混沌理论的结合是科学发展的 必然结果。对混沌的研究具有重大的意义。 复杂网络中的同步的研究基础是图论，统计物理学，非线性动力学和复杂性 科学等领域的科学研究。科学家对于复杂网络的研究开始于数学家e r d o s 和 r e n y i 对随机图的研究和探索。1 9 9 8 年6 月，康奈尔大学的w a t t s 和s t r o g a t z 在n a t u r e 上发表了小世界网络的群体动力行为“1 的文章，揭示了复杂网络 的小世界特性。1 9 9 9 年1 0 月，圣母大学的b a r a b a s i 和a l b e r t 在s c i e n c e 杂 志发表了随机网络中标度的涌现“1 一文，揭示了复杂网络的无标度性质。这 两件工作掀起了人们对复杂网络的研究热潮。复杂网络的研究不仅仅局限于数学 和物理领域，它受到各个学科领域的科研工作者的关注。它已经渗透到管理学科， 工程理论等众多学科，是一门综合了数学、物理、计算机、管理等学科的跨学科 研究课题。复杂网络的研究具有深远的现实意义。我们生活中的很多问题都涉及 到复杂网络的研究，比如传染病在人类社会以及动物界中的传播，电力网络中局 部小的故障引发的大面积的停电事故，交通网络的优化等一些现实中急需解决的 问题。复杂网络理论研究的是各种看上去互不相同的复杂网络之间的共性以及处 理它们的一些普适性方法以及建立在复杂网络基础上的动力学系统的行为预测 和控制。在当今时代，复杂网络已经逐渐形成一门新的学科随“。复杂网络研究 的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网 络上的模型性质，以及网络的结构稳定性，网络的动力学机制等问题。在过去的 十年中，以物理学家和数学家为代表的广大科研工作者的努力下，复杂网络理论 得到了很大的发展。 人们普遍关心的一个问题是复杂网络的生成过程和其机制，也就是网络的来 源和形成问题。网络本身的生长演化过程是一个非常有趣的问题。每一个系统中 的网络，每一种类型的网络的生长都有其自身的独特的性质，有其紧密联系在一 起的一些特有现象，这些都和网络其自身的演化和生长机制有关。建立在研究网 络的生成机制基础上，人们可以探索复杂网络上的动力学行为。例如传染病或者 北京邮电大学硕士学位论文 第一章引言 谣言在社会关系网络上的传播，病毒在互联网上传播和扩散，非线性振子组成的 复杂网络的行为预测和控制等。同时，也可以研究网络的同步稳定性和自身的稳 定性等与网络结构的关系。研究网络的形成机制，网络的几何性质，网络生长的 规律，网络上的动力学模型，以及网络的结构稳定性，并把它们与现实生活中的具 体系统结合起来，这是是复杂网络研究的中心内容。可以期望，复杂网络的研究 最终会揭示各种不同的复杂系统中的普适共性和各个系统的独特性。加深了热门 对于广泛的实际应用领域中根本规律的理解。 本文的一个研究重点是关注复杂网络的拓扑结构及其对混沌同步的影响，通 过对真实短信息网路的研究，构造了一个模拟现实生活中真实网络生长过程模 型，研究网络拓扑结构方面的特点，并与传统的网络模型相比较，来揭示了以 人际关系为基础的短信通讯网络的生长机制。通过该研究可以进一步讨论并建立 一些真实网络的模型以及在该网络模型上的动力学行为。必须指出，当前对网络 生长的研究大多关注网络的整体拓扑几何量对网络生长的影响。对于大型的复杂 网络，整个网络的几何结构并没有真正影响到局部量的生长过程。复杂网络中节 点的生长更多地依赖于网络的局部信息。或者说，网络的整体结构信息对局部的 生长是透明的。 另外，根据当前最新的研究进展，在研究对复杂网络中的混沌同步中，利用 白组织的演化方法，本文研究了网络结构对同步的影响，力求寻找到最适合于同 步的网络结构。我们进一步得到了网络的同步能力和网络的各个拓扑结构参数没 有严格依赖性的结论。这不仅帮助人们更好的认识复杂网络上的混沌同步的特 征，也对人们进一步研究复杂网络上同步的控制，网络结构的优化提供了更多的 方法论。 网络化是今后人类社会发展的一个主流方向。在当今社会，对复杂网络的 研究显得愈来愈重要。当前，我们正在建立或者使用着各种各样复杂网络，如电 信网络，交通网络，金融网络等，这些网络与我们的日常生活紧密相联系。这就 需要我们深入研究和更深刻的理解这些复杂网络的拓扑结构，动力学行为，同步 能力，抗干扰能力等，以便更好的设计和管理这些实际的复杂网络。研究复杂网 络，在理论和实际应用上都具有十分重要的意义。 2 北京邮电大学硕士学位论文第一章引言 参考文献 【l 】w a t t sdj ，s t r o g a t zsh ，n a u l r e1 9 9 8 ，3 9 3 ：4 4 0 - 4 4 2 【2 】b a r a b a s ial a l b e r trs c i e n c e , 1 9 9 9 ，2 6 8 ：5 0 9 5 1 2 3 1 b a r a b a s iall i n k ：t h en e ws c i e n c eo fn e t w o r k m a s s a c h u s e t t s ：p r e s s p u b l i s h i n g , 2 0 0 2 【4 】w a t td j t h e n e w ”s c i e n c eo fn e t w o r k a n n u a lr e v i e wo fs o c i o l o g y , 2 0 0 4 ， 3 0 ：2 4 3 2 7 0 3 北京邮电大学硕士学位论文 第二章复杂网络的研究综述 2 1 引言 第二章复杂网络的研究综述 近年来，复杂网络引起了许多相关领域研究人员的关注。网络可以用来描述 个体与个体之间的关系。包括人与人之间的关系，计算机之间的通信连接，通信 网之间的网络联接，以及非线性振子之间的耦合。复杂网络就是具有复杂拓扑结 构和动力行为的大规模网络，它是由大量的节点通过边的相互连接而构成的。复 杂网络的节点可以是任意具有特定动力和信息内涵的系统的基本单位。而边则 表示这些基本单位之间的关系或联系。例如，英特网、食物链网络、生物网络、 通讯网络、公路网、航空网络、电力网络、病毒传播网络等都是复杂网络。由于 我们生活中存在着大量的复杂网络，这促使我们去研究这些复杂网络的行为。 我们生活在不断变化的复杂网络中。尽管无论是i n t e r n e t 、w 聊、e m a i l 网络、生物网络还是短信网络。这些网络形式在现在的社会生活中极大的影响着 人们的生活。如果失去了这些网络或者这些网络被破坏，我们的生活将会彻底地 被改变。无论哪种网络，我们对它们的认知都是有限的。理解好这些网络，对于 提高网络安全性，增加网络容量，提高网络的运行效率和鲁棒性都是有着重大的 意义的。 研究并分析这些网络的一个重要目的就是要理解建立在网络基础上的动力 学行为和网络的关系，并进而改善网络上的动力学行为和性能。例如，在充分理 解这些网络的拓扑特征以及动力学模型基础上，我们就可以掌握病毒在网络中的 传播规律，从而更好的预防病毒的传播；我们也可以大大提高网络的容量，从而 节省了有限的资源；我们还可以使我们的网络变得更通畅，有利于信息的流动， 提高网络的运行效率。 然而，复杂网络由于其“天生”的复杂性，也给人类的研究带来了困难。这 主要表现在以下三点“，： 1 复杂网络的连接复杂性。复杂网络的拓扑结构看上去及其混乱，表现出 其错综复杂的一面。节点之间的连接方式也是多样性的，要考虑到连接 的权重和连接的方向。单纯的依靠人类的大脑是很难研究这些内容的。 2 复杂网络的节点复杂性。网络中的节点是多样性的。从最简单的理想化 质点到具有混沌等非线性行为的动力系统。网络中的节点种类，复杂度 都对研究提出了挑战。 3 大部分的复杂网络的拓扑结构是变化的。实际的复杂网络会因为自身的 4 北京邮电大学硕士学位论文第二章复杂网络的研究综述 机制或者各种外界因素的影响和作用而发生变化。而且网络的节点也具 有复杂的时间演化行为。这使得复杂网络的分析变得更加困难 但是，随着科学技术的发展，特别是计算机的计算能力不断提升，各学科的 不断渗透以及学科边界被不断打破，网络理论的研究得到了飞速的发展，新的理 论研究、新的应用领域的发展和开辟，大大促进了复杂网络研究的发展。例如， 2 0 世纪中叶以来，非线性动力学，统计物理已经逐渐发展成为分析复杂动力系统 的有力工具。复杂网络的研究还涉及到很多的领域，计算机科学技术的发展为复 杂网络的研究提供了有力的条件。我们还发现，计算机的数值模拟与图论都是研 究复杂网的有力工具。在研究网络节点的相互作用的时候，利用统计物理及图论 的工具，可以从宏观和微观角度研究网络节点间的相互作用。在本文中我们重点 关注的短信网络和基于同步能力的网络优化中，我们暂时不考虑网络的方向性问 题，而是仅仅考虑网络的相互作用。 2 2 复杂网络的研究简史 2 2 1 欧拉与“七桥问题” 任何一个网络都可以抽象成一些节点按照某种方式连接在一起而构成的系 统。一种比较简单的抽象方法就是用抽象的点表示网络中的节点，用节点之间的 连线代表具体网络中节点的联系。 实际网络的研究可以从1 8 世纪著名数学家欧拉( e u l e r ) 的“k o n i g s b e r g 七桥问题“2 1 开始，如图2 1 。欧拉对“七桥问题”的抽象和论证思想，开创了 数学中的一个分支一一图论( g r a p ht e h o r y ) 的研究。事实上，关于复杂网络的 研究和欧拉当年对“七桥问题”的研究在某种程度上是一脉相承的。 c b 图2 - 1 ：k o n i g s b e r g “七桥问题”的图示 d 北京邮电大学硕士学位论文第二章复杂网络的研究综述 2 2 2e r d o s 和r e n y i 的随机图论 欧拉在解决“七桥问题”之后的相当长一段时间，图论并未得到足够的发展 直到2 0 世纪6 0 年代，e r d o s 和r e n y i 建立的随机图论( r a n d o m6 r a p ht h e o r y ) 被公认为是在数学上开创了复杂网罗理论的系统性研究 2 2 3 小世界网络的实验及其理论的提出 2 0 世纪6 0 年代，哈佛大学的社会心理学家s t a n l e ym i l g r a m 通过一些社会 调查后得出了结论：地球上的任意两个人的平均距离是6 。也就是说，只要通过 5 个人，地球上的任意两个人就可以发生联系。这就是著名的六度分离( s i x d e g r e eo fs e p a r a t i o n ) 结论。之后的科学研究表明。1 ，m i l g r a m 的小世界实验 具有划时代的意义。然而m i l g r a m 的实验不是严格意义上的科学试验，由于统计 数据量的因素，其可信度是非常低的。m i l g r a m 的实验之后，也有一些其他的实 验来验证“六度分离”的正确性。包括k e v i nb a c o n 游戏、e r d o s 数等。直到 1 9 9 8 年w a t t s 和s t r o g t z 引入了著名的小世界网络模型。1 。科学界才真正开始大 规模关心这一方面的发展。 2 2 4 无标度网络的提出 无标度网络的最明显的特征就是网络的度分布服从幂律形式。随机网络和小 世界网络的度分布是钟形分布的。也就是说度非常小的和度非常大的节点存在概 率比较小。网络当中绝大部分是度比较“中等”的节点。然而，现实中的网络并 不是都是遵循这个“中庸之道”的。研究表明，许多复杂网络，包括因特网， 万维网等网络的连接度分布具有幂律形式，称为无标度网络。 2 2 5 复杂网络研究的热潮 2 0 世纪6 0 年代以来，复杂网络的研究一直是基于随机图理论。但是，事实 上大多数复杂网络的结构不是完全随机的，而是具有其独特的拓扑结构的。从2 0 世纪9 0 年代末期开始，复杂网络的科学研究发生了重大的转变，两篇分别关于 小世界网络0 1 和无标度网络“的标志性文章可以看作复杂网络研究的里程碑。这 两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型 以阐述这些特性的产生机理。 复杂网络的在最近几年得到了突破性的进展，得益于广大科学工作者的努 6 北京邮电大学顼士学位论文 第二章复杂网络的研究综述 力，也得意于越来越强大的计算机计算能力以及各个学科之问的互相渗透。 2 3 复杂网络的基本概念 人们在刻画复杂网络的特征上提出了许多许多刻画复杂网络的概念和方法。 在这里我们介绍复杂网络的基本概念和拓扑特征量。要想深入理解网络，我们得 从网络的基本概念和刻画网络的参数谈起。 2 3 1 网络的图表示 在图论中，网络g = ( y ，占) 的概念是指由一个点的集合矿( g ) 和一个边的集 合e ( g ) 组成的一个图，且e ( g ) 中的每条边e ，有v ( g ) 的对点f 点和，点与之对 应。记项点数为n 爿v l ，边数为l = e i 。如果从i 点连到歹点的边与从，点连至n j 点的边对应同一条边，称为无向网络( u n d i r e c t e d n e t w o r k s ) ，否则为有向网络 ( d i r e c t e dn e t w o r k s ) ，如果任意i e 。 l ，则称为无权网络，否则为加权网络。 同时，网络当中还可能包含不同类型的节点。图2 2 给出了一个简单的网络例子。 2 l 5 3 图2 - 2 ：一个由5 个节点，4 条边组成的无向网络 表示网络的图的结构信息用邻接矩阵b 来表示，如果节点i 与节点，存在着 连接的边，那么矩阵上相应位置上b “我们就用1 来表示，如果不存在连接我们 就用0 来表示，显然一个无向图的邻接矩阵是对称矩阵。 2 3 2 网络的平均最短路径 网络中任意两个节点f 和_ ，的最短路径，定义为连接这两个节点的最短路径 上的边数。一个集团是指一系列连接在一起的节点的集合，如果一个用来表示网 络的图只包含一个集团，那么我就说该图是全连接的。当一个图是全连接的，我 7 北京邮电大学硕士学位论文 第二章复杂网络的研究综述 们就存在着这样一个概念，网络的平均最短路径，它定义为网络中任意两个节点 之间的距离的平均值： 三= 志d 口 ( 2 一1 ) n ( n + 1 ) 智9 同时，我们也把网络中任意两个节点之间的距离的最大值称为网络的直径。 在上述定义中，把节点到自身的距离定义为o 。如果不考虑节点到自身的距 离，可以在公式的右边乘以一个常数因子。事实上，在实际研究中，这种差别是 可以忽略不计的。例如，在短信网络中，网络的平均最短路径是连接两个手机号 码的最小手机号码个数。最近的研究表明，尽管短信网络规模庞大，但是短信网 络的平均最短路径长度却很小4 1 。 2 3 3 节点的度与度分布 网络中节点的度是刻画网络的局部特征量，节点i 的度定义为该节点连接的 其它节点的个数。 节点的度的概念在物理领域中代表节点的局域连通性。第i 个节点的度见可 以由邻接矩阵的表达式推导出来： 南= ( 曰2 ) 。= e 岛 ( 2 2 ) 对于有向网络，要把度推广为入度和出度，节点的入度指从其它节点指向该 节点的边的数目。节点的出度指从该节点指向其它节点的边的数目。 = 艿” ( 2 3 ) 悝y 以及 砖= 万” v e r ( 2 - 4 ) 很显然网络中的各个节点的度不一定都一样。系统各节点度可以用一个分布 函数p ( | ) ( 度分布函数) 描述，度分布函数反映了网络系统的局部统计特征。 单靠节点的度的数值还不能完全区分不同的网络。 节点度的分布用分布函数p ( k ) 来表示，只j j ) 表示网络中的节点具有度为k 的概率。节点度的分布是整个网络的基本统计特性，表征网络的全局性质。一般 来说，节点的度越大就意味着该节点在网络中越“重要”。 8 北京邮电大学硕士学位论文第二章复杂网络的研究综述 2 3 4 集聚系数 网络的一个很重要的特征就是集聚性质。集聚系数c 是表示图中某一节点的 两个最近邻同时也互相连接的概率。一般来说，如果某个节点i 的度为k ，那么 这k 个节点之间最多可能有k ( k 一1 ) 2 条边。而实际存在的边数e 和总的可能边 数的比值就定义为该节点的集聚系数。网络中某个节点i 的集聚系数e 的为： c ：= 2 e t “t ( 岛一1 ) ) ( 2 5 ) 其中岛是节点i 的度，层是与i 相连接的节点之间的实际存在的连接个数。 我们可以得出，c = 与i 相连的三角形个数除于与i 相连的三元组的个数。与节 点i 相连的三元组是指包括节点i 的三个节点，其中至少存在从节点i 到其它两 个节点的连接。 很明显，c 的取值范围为 o ，1 ，c = 0 表示网络中没有三角形连接，c = 1 表示网络是全连接的。很高的集聚系数反映在图中就是具有很多的三角形。整个 网络的集聚系数定义为所有节点的集聚系数的平均值。表征了整个网络的平均的 “成簇性质”。此外还存在着另一种定义集聚系数的方法嘲。 2 3 5 网络的介数 顶点i 的介数含义为网络中所有的最短路径中，经过珀q 数量。它反映顶点i 的影响力，是网络拓扑结构的一个全局特征量。这一概念是由g i r v a n n e v a n a n ( 2 0 0 2 ) 提出的： y 置：y 竺型 ( 2 6 ) 1 s 这一物理量可以衡量网络中节点对网络联通性的贡献度。相应的具有最高介 数值的节点被称作网络的中心节点。类似地，可以定义边的介数，n e w m a n 等人发 现，边的介数可以用于分析顶点的聚类0 1 。其基本思想是在包含不同集团的网络 中所有最短路径经过次数最多的边，也就是介数最大的边，必然是联接两个集团 之间的边。 同时，还有另一种计算网络介数的方法，该方法的核心思想是把网络看成一 个无源电阻网络，把网络中的每一条边当成固定大小的电阻，同时在网络的两个 节点之间加上电压，利用k i r h o l f 定律计算经过每条边的电流。利用此方法在不 同的节点对之间加上电压，统计并归一化经过每条边的平均电流从而得到每条边 的介数( 同时也可以计算经过每个节点的电流，并计算其介数) ，利用此方法计 算得到的结果可以反映网络中节点和边对网络联通性的贡献度。在我们的实验 9 北京邮电大学硕士学位论文 第二章复杂网络的研究综述 中，利用网络里面随机行走的办法得到的节点或者边的介数和上述方法得到的结 构是一致的。说明这种方法的现实可行性和依据。 2 4 一些基本的复杂网络拓扑模型及其特性 科研工作者对实际生活中的复杂网络系统的一些拓扑结构的进行分析，归 纳出了一些简单的理论模型。一方面，这些模型可以用来研究系统本身的拓扑性 质，使人们更清晰的认识网络的拓扑结构，从而指导人们如何有效地利用和构造 网络，如预防和控制传染病等。另一方面，为其他领域的研究提供了平台，如i s i n g 模型、混沌同步等。下面对几个基本的复杂网络的模型做一下介绍。 2 4 1 规则网络 最常见的规则网络是最近邻耦合网络，如图2 - 3 ( b ) ，在这种网络中，每个 节点指和它周围的“邻居”相连。在研究中比较常见的是具有周期性边条件的最 近邻耦合网络。假设网络包含n 个节点，平均度为k ( k 为偶数) ，那么，规则网 络中每个节点和与它左右各k 2 个邻居点相连。对于比较大的k ，最近邻耦合的 网络集聚系数是： c f f i o 7 5 + ( k - 2 ) ( k - 1 ) ( 2 - 7 ) 网络的平均最短路径长度是： l 0 5 + k ( 2 - 8 ) 常见的规则网络也有星形耦合网络，如图2 - 3 ( c ) ，它是有一个中心节点， 其它的节点都只与中心节点连接。星形网络的平均最短路径长度是 三：2 一2 ( n - i )( 2 9 ) n ( n 1 ) 星形网络的集聚系数是： c = ( n - i ) n 啼l 当( 斗哪 ( 2 1 0 ) 按照规则网络的定义和性质，全耦合网络也是规则网络图2 3 ( a ) 。它具有 最小的平均最短路径和最大的平均集聚系数。由于现实中大部分的复杂网络都是 比较稀疏的。所以全局耦合网络研究的比较少。 l o 北京邮电大学硕士学位论文第二章复杂同络的研究综述 图2 - 3 ：规则网络( a ) 全连接网络，( b ) 最近邻连接网络，( c ) 星形网络 2 4 2 随机网络 与规则网络相对应的是随机网络。随机网络模型时由e r d s s r e n y i 在1 9 5 9 年提出的“1 ，随机网络理论是复杂网络理论研究的一个重要方面，也是复杂网络 理论的一个基础理论，在交通规划，通信设计，传染病的控制等许多工程实际领 域都有很重要的应用。 在理论计算或者模拟中，随机网络模型的构造方法一般有很多种。比较常用 的方法是按照它的定义进行构造的，如图2 4 所示。 其构造该法是：假设网络有n 个节点。如果对于任意两个节点的连接概率是 相等的，那么就有n ( n 一1 ) 2 个可以连接的边。连通概率p 是指任意两个节点 相连接或者说这两个节点问存在边的概率： p ：栉 幽】( 2 1 1 ) 。 2 如果这个随机网络有力个随机边，根据排列组合的知识，有g 卅i ，：个等价的随 机网络模型。 p 叫o 豢蟒ii 图2 - 4 ：随机网络图分别为连接概率为o ，0 1 和0 1 5 的情况下连接而成的网络 节点度的分布p 阮j ( b o l l o b a s ，1 9 8 1 ) 9 1 满足二项式分布： 尸( 后) = c ：一l p ( 1 一p ) ”1 “ ( 2 1 2 ) 1 1 北京邮电大学硕士学位论文第二章复杂网络的研究综述 当n 很大时，近似为p o i s s o n 分布，其表达式如式3 - - 1 3 所示，节点度分布如图 2 - 5 所示 聃= ，“鲁 ( 2 _ 1 3 ) = ( 2 - 1 4 ) 这里 表示平均度的分布。 图2 - 5 ：当n 很大时，随机网络度的分布近似于p o i s s o n 分布，该图中横坐标七代表节点的 数，纵坐标是取相应度的概率 随机网络的许多性质是突然涌现的( 相变性质) 。比如说，对于任一给定的 概率，要么几乎每个网络都具有某个性质q ，要么几乎每个网络都不具有该性质。 如网络的连同性。当p o f i n n ) n 时，整体网络是处于一个连接状态的，此时 网络的平均度 = p ( n 1 ) “p n 。半径为 k 口i n n i n ( 2 - 1 5 ) 集聚系数是： c o = p * 尘 ( 2 1 6 ) n 随机网络有比较小的半径，这一特征与许多自然界中的网络相似，但是当网 络规模非常大的时候，成簇系数几乎是可以忽略的，这一特征与自然界中许多实 际网络的特征却有很大的出入。人们可以从多个角度对随机网络机型扩展以使其 更接近真实的网络。比如，可以构造不同的算法生成网络，从而得到不同于随机 网络的拓扑结构参数，更真实地模拟现实网络。 1 2 北京邮电大学硬士学位论文第二章复杂网终的研究综述 2 4 3 小世界网络 在现实生活中，我们经常发现我们要找的某个不认识的人居然就是我们朋友 的朋友，也就是说现实中的人际关系网络具有高的集聚系数。因此，我们常常感 叹这个世界是多么的小。很显然，现实的网络不是规则的网络。直观地，我们可 能认为现实中的人际关系网络是随机网络，但是我们上文的结论发现随机网络并 没有高的集聚系数。因此规则网络和随机网络都不能用来有力地刻画真实网络。 人们提出了一些不同类型的小世界模型“”，其中最为著名的是w a t t s 和s t r o g a t z 的 s 小世界网络模型和n e m e a n - w a t t s 的舰小世界模型。 1 9 9 8 年，w a t t s 和s t r o g a t z 引进了非常有趣的小世界网络模型0 1 ，也就是 著名的w s 小世界网络模型。 w - s 模型的构造是从一个具有n 个节点的最近邻耦合规则网络为基础，每个 节点与其k 个最近邻连接：然后，以概率p 重新选取每个边，也就是对每个节点 的边，以概率保持一端不变，另一端随机地网络中的节点。保持边的总数目不变， 避免重连接和自连接。如图2 7 ( a ) 所示。 图2 - 6 ：w - s 小世界网络的集聚系数和平均最短路径随着重连接概率p 的变化图“ 用w - s 网络模型构造出来的网络模型的集聚系数c 和平均最短路径长度l 随着重连接概率p 的变化而变化。w a t t s 和s t r o g a t z 画出了网络的集聚系数和 平均最短路径随着p 的变化的曲线。如图2 - 6 所示( 两个参数量都做了归一化处 理) 。 可以看出从规则网络到完全随机的网络的过渡过程。当p - - - - o 时( 规则网络) ， 网络具有高的集聚系数( a o ) “3 4 ) 和大的平均最短路径长度 ( l ( o ) “2 k 口1 ) 。当p 有比较小的变化时，重连后的网络和原来的规则网络 1 3 北京邮电大学硕士学位论文 第二章复杂网络的研究综述 之间的变化很小，但是平均最短路径长度却变化很大。这种既具有大的集聚系数 又具有小的平均最短路径的网络称为小世界网络。 另一种构造小世界的改进方法是n e w m a n - w a t t s 模型( 1 9 9 9 年) m 1 ，该模型 ( n w 模型) 是从一个具有n 个节点的规则网络开始，以概率p 加随机边，边的总 数目是变化的。具体构造的步骤如下： ( 1 ) 从规则网络开始：从一个具有n 个节点的最近邻耦合规则网络开 始，每个节点与其七个最近邻连接。 ( 2 ) 随机化加边：随机选取一对节点，以概率p 连接。不考虑重连和 自相连。 对于w 模型，p = o 对应的网络是原来的规则网络，p = 1 对应的网络是全连 接的网络，也算是规则网络，如图2 - 7 。 o 彰 m w m n g o f l i n k + o 枷搦o no p l i n l 口 图2 - 7 ：两种方式构造小世界网络模型( a ) 卜s 模型：m + m m - , p 边的总数目不变即平均 度数不变，将原来的边进行重联；( b ) n - w 模型：在保持原来的连接方式的情况下，增加新 的连接，边的个数增加，平均度数不再保持恒定 对于两种不同的小世界网络模型，它们的集聚系数是不一样的。w s 小世界 网络的集聚系数是： = 黼帅) 3 协1 7 ) 姗网络的集聚系数是： c ( p ) = 丽面3 ( 而k - ；2 ) 丽 2 一1 8 ) 1 4 北京邮电大学硕士学位论文第二章复杂网络的研究综述 对于小世界网络的平均最短路径的表达式，利用重整化群方法可以得到它的 近似表达式： 三( p ) ：g f ( n k p 2 ) ( 2 1 9 ) 其中，函数是一个普适标度函数，到目前为止还没有它的精确表达式。n e w m a n 等人基于平均场的方法给出了它的近似表达式“。： m * 赤一压( 2 - 2 0 ) 以上两种不同的构造方式也给出了不同的小世界网络的度分布表达式。对于 w s 小世界网络，度分布满足： 删= 露( 甜”秒“ 时( 2 - 2 1 ) p ( k ) = 0k k 时 ( 2 2 2 ) 对于n w 模型，网路中的每个节点的度至少为k 2 ，节点的度分布满足： 以鼢：，必，一”p 扣竺兰! 兰! 。一焉 c z z s ， 删= 7 豹, c ：2 ”p n 扣蔷笔茫焉 ( 2 - 2 3 ) 2 4 4 无标度网络 前面我们提过了无标度网络的，也就是s c a l e f r e e 网络。无标度网络中每 个节点的度数并不均匀，网络中总是存在少数几个具有较大度数的点。许多现实 生活中的实际网络