（计算机软件与理论专业论文）复杂网络的动力学行为研究.pdf

摘要 摘要 复杂网络是交叉学科中最为活跃的领域之一，受到了来自各个领域的广泛关 注。本文内容主要研究复杂网络的动力学行为。其中包括：1 ) 关于时滞复杂网络 同步的局部稳定性及全局稳定性的若干研究；2 ) 关于时滞耦合权重网络同步的扰 动研究；3 ) 关于切变复杂网络中相同步及同步过程研究；4 ) 关于复杂网络连接的 离散耦合映射同步分析方法的研究；5 ) 关于移动无线网络上病毒传播的研究。 本文的主要创新成果如下： 1 、时延复杂网络同步的局部稳定性及全局稳定性 由于信号受传输速度的限制或节点受自身处理能力的限制，复杂网络中通常 存在时延。根据时延产生的原因不同，分别研究了由传输导致的时延耦合的复杂 网络同步以及由节点自身引起的时延复杂网络同步。针对带时滞的时变耦合复杂 网络同步，提出了用子空间分解和l y a p u n o v i 函数分析同步流形稳定性的方法。对 由节点动力学引起的时滞复杂网络，分别获得了局部渐进同步和全局指数同步的 判据。此外，还研究了时滞耦合的多个神经网络同步的问题。 2 、时延耦合权重网络同步的扰动 实际生活中的网络大多数是动态的，网络中不断的有新的边加入或者旧的边 移除，势必造成对网络同步性的影响。本文研究了拓扑结构随时间变化的时延权 重网络同步的扰动现象，通过理论分析得到了与网络拓扑结构直接相关的同步性 准则。根据同步性在网络拓扑受到微小扰动时的变化情况进一步分析了结构对动 力学的影响。 3 、切变复杂网络中相同步及同步过程 在一些分布式通信系统中，网络节点之间的连接往往在某个时刻是以概率随 t 机存在的。本文研究了一组相位振荡器以切变方式耦合时产生的同步现象，发现 了在较快的切换速度下，网络总是能够获得同步。另外，还研究了不同的网络拓扑 结构在同步的形成过程中所起的作用，从切变网络模型中得到了均匀网络与非均 匀网络不同的同步过程。 4 、新的耦合映射复杂网络同步的分析 基于目前复杂网络同步稳定性分析方法中存在的一些局限性，提出了一种利 用矩阵测度来研究同步的方法，并通过对离散耦合映射网络的分析，得到了较易 验证的局部同步和全局同步的准则。 i 摘要 5 、动态复杂网络上病毒传播 复杂网络拓扑结构对网络上动力学的影响也体现在传播行为上。本文提出了 一种描述移动无线a dh o c 网络的动态复杂网络模型，该模型刻画了网络节点的移 动性、通信信道的竞争机制以及物理连接的限制。借助于s i r 模型研究了蠕虫在该 模型上的传播行为，揭示了网络节点的移动性与病毒传播之间的关联关系。 关键词：复杂网络，小世界网络，无标度网络，时滞，同步，稳定性，神经网络，切 变网络，扰动 i i a b s t r a c t a b s t r a c t a so n eo ft h em o s ta c t i v ea r e a si nt h ei n t e r d i s c i p l i n a r yr e s e a r c hf i e l d ，c o m p l e x n e t w o r k sa t t r a c te x t e n s i v ea t t e n t i o n sf r o mv a r i o u sf i e l d so fs c i e n c ea n de n g i n e e r i n g i nt h i sd i s s e r t a t i o n ，w ep e r f o r md y n a m i c ss t u d yo nc o m p l e xn e t w o r k s t h em a i n c o n t e n t so ft h i sd i s s e r t a t i o ni n c l u d e ：( 1 ) l o c a la n dg l o b a ls t a b i l i t yo fs y n c h r o n i z a - t i o ni ns o m ed e l a y e dc o m p l e xn e t w o r k s ；( 2 ) s y n c h r o n i z a t i o na n di t sp e r t u r b a t i o no f w e i g h t e dn e t w o r k sw i t hd e l a y e dc o u p l i n g s ；( 3 ) p h a s es y n c h r o n i z a t i o na n ds y n c h r o - n i z a t i o np r o c e s si ns w i t c h i n gn e t w o r k s ；( 4 ) a p p r o a c ht oa n a l y z es y n c h r o n i z a t i o n o fc o u p l e dm a po nc o m p l e xn e t w o r k s ；( 5 ) e p i d e m i cs p r e a d i n go nm o b i l ew i r e l e s s n e t w o r k s t h em a i nc o n t r i b u t i o ni nt h i sd i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： 1 l o c a la n dg l o b a ls y n c h r o n i z a t i o ns t u d yo fd e l a y e dc o m p l e xn e t - w o r k s d u et ol i m i t e dt r a n s m i t t i n gs p e e da n dp r o c e s sa b i l i t yo nn o d e s ，u s u a u yt h e r e a r et i m ed e l a y si nc o m p l e xn e t w o r k s c o n s i d e r i n gt h ed i f f e r e n c e sb e t w e e nt h ef a c - t o r st h a ti n d u c et i m ed e l a y s ，w es t u d yt h es y n c h r o n i z a t i o no ft i m e - d e l a y e dc o u p l e d c o m p l e xn e t w o r k sw h e r et h ed e l a y sa x ec a u s e db yl i m i t e dt r a n s m i t t i n gs p e e da n d s y n c h r o n i z a t i o no fc o u p l e dt i m e - d e l a y e dd y n a m i c a ls y s t e m sw h e r et h ed e l a y sa x e c a u s e db yp r o p e r t i e so fn o d e s ，r e s p e c t i v e l y f o rt h ed e l a y e dc o m p l e xn e t w o r k s w i t ht i m e - v a r y i n gc o u p l i n g s ，w ep r e s e n tan e wa p p r o a c ht oa n a l y z et h es t a b i l i t y o fs y n c h r o n i z a t i o nm a n i f o l db yc o m b i n i n gs u b s p a c ed e c o m p o s i t i o na n dl y a p u n o v f u n c t i o n s a st ot h es e c o n dc a s e ，w ed e r i v et h ec r i t e r i af o rl o c a l l ya s y m p t o t i c a l s y n c h r o n i z a t i o na n dg l o b a l l ye x p o n e n t i a ls y n c h r o n i z a t i o n 2 t h es t u d yo fs y n c h r o n i z a t i o na n di t sp e r t u r b a t i o ni nw e i g h t e d c o m p l e xn e t w o r k sw i t ht i m ed e l a y m a n yr e a l - w o r l dn e t w o r k sa r ed y n a m i c a l l ye v o l v i n g ，f o re x a m p l e ，n e we d g e s a r ei n t r o d u c e do ro l de d g e sa x er e m o v e dc o n t i n u a l l y , w h i c hc e r t a i n l yw i l lh a v ea n e f f e c to nn e t w o r ks y n c h r o n i z a b i l i t y i nt h i sd i s s e r t a t i o nw es t u d yt h ep e r t u r b a t i o n p h e n o m e n o no fw e i g h t e dc o m p l e xn e t w o r k sw i t ht i m ed e l a yw h e nd i s t u r b i n gt h e c o u p l i n gc o n f i g u r a t i o n s i nt h ef i g h to ft h e o r e t i c a la n a l y s i s ，w eo b t a i n e dt h ec r i t e r i o n i i i a b s t r a c t f o rs y n c h r o n i z a t i o nw h i c hi s d i r e c t l yr e l a t e dw i t hn e t w o r kt o p o l o g y w ef u r t h e r i n v e s t i g a t e dt h ei m p a c to ft o p o l o g yo nd y n a m i c su n d e rs m a l lc o u p f i n gp e r t u r b a t i o n s b ya p p l y i n go u rt h e o r e t i c a lr e s u l t s 3 p h a s es y n c h r o n i z a t i o ns t u d yo ns w i t c h i n gn e t w o r k so fc o u p l e d o s c i l l a t o r s i ti so f t e nt h ec a s et h a td u et ot h ed y n a m i cn a t u r eo fe a c hu n i t ss t a t e si ns o m e d i s t r i b u t e dc o m m u n i c a t i o ns y s t e m s ，t h ee x i s t e n c eo fa l li n f o r m a t i o nc h a n n e lb e - t w e e na p a i ro fu n i t sa te a c ht i m ei n s t a n c ei sp r o b a b i l i s t i ca n di n d e p e n d e n to fo t h e r c h a n n e l s ；h e n c e ，t h et o p o l o g yo fs u c hn e t w o r k sv a r i e so v e rt i m e t a k i n gt h i sc a s e i n t oa c c o u n t ，w es t u d yt h eo n s e to fs y n c h r o n i z a t i o ni na r r a y so fp h a s eo s c i l l a t o r s w i t hs w i t c h i n gc o u p l i n g s w ef o u n dt h a tt h en e t w o r ka l w a y sc a na c h i e v es y n c h r o - n i z a t i o nu n d e rf a s ts w i t c h e s 。m o r e o v e r ，w ef u r t h e rs t u d i e dt h er o l eo fn e t w o r k t o p o l o g i e si nt h es y n c h r o n i z a t i o np r o c e s sa n do b s e r v e dt h ed i f f e r e n ts y n c h r o n i z a - t i o np r o c e s s e sb e t w e e nh o m o g e n e o u sn e t w o r k sa n dh e t e r o g e n e o u sn e t w o r k sf r o m o u rs w i t c h i n gn e t w o r km o d e l 4 s t u d yo ns y n c h r o n i z a t i o no fc o u p l e dm a pn e t w o r k sb yan e w a p p r o a c h c o n s i d e r i n gt h el i m i t a t i o no fe x i s t i n gs t a b i l i t ya n a l y s i sm e t h o d sf o rc o m p l e x n e t w o r ks y n c h r o n i z a t i o nt os o m ee x t e n t ，w ep r e s e n tan e wa p p r o a c ht os t u d yt h e s y c h r o n i z a b i l i t yb yu s i n gm a t r i xm e a s u r e t h r o u g ht h e o r e t i c a la n a l y s i so fc o u p l e d d i s c r e t em a p s ，w eo b t a i n e dt h el o c a la n d g l o b a ls y n c h r o n i z a t i o nc r i t e r i aw h i c hc a n b ee a s i l yv e r i f i e da n da p p l i e di np r a c t i c e 5 s p r e a d i n gd y n a m i c ss t u d yo nd y n a m i c a lc o m p l e xn e t w o r k s t h ee f f e c to fn e t w o r kt o p o l o g yo ns y s t e md y n a m i c sc a na l s ob em a n i f e s t e di n e p i d e m i cs p r e a d i n gb e h a v i o r s i nt h i sd i s s e r t a t i o n ，w ep r e s e n tad y n a m i c a lc o m p l e x n e t w o r km o d e lt od e s c r i b et h em o b i l ew i r e l e s sa dh o cn e t w o r k s t h i sm o d e lc a p - t u r e st h em o b i l i t yo fn o d e si nn e t w o r k s ，c h a n n e lc o n t e n t i o nd u r i n gc o m m u n i c a t i n g a n dl i m i t e dp h y s i c a lc o n n e c t i o n s b ym e a n so fb a s i cs i rm o d e l ，w es t u d i e dt h e s p r e a d i n gd y n a m i c so fw o r m so nt h i sm o d e l ，f i n d i n gt h er e l a t i o n s h i pb e t w e e nt h e m o b i l i t yo fn o d e sa n de p i d e m i cs p r e a d i n g k e y w o r d s ：c o m p l e xn e t w o r k s ，s m a l l - w o r l dn e t w o r k s ，s c a l e - f r e en e t w o r k s ，t i m e - d e l a y , s y n c h r o n i z a t i o n ，s t a b i l i t y , n e u r a ln e t w o r k s ，s w i t c h i n gn e t w o r k s ，p e r t u r b a t i o n i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 躲查翌 眺冲易月明 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 盔殖 日期：沙呷年6 月4 日 第一章绪论 第一耄绪论 在人们的日常生活中，网络无处不在。它可以是具体的实体对象，如电力网 络、i n t e r n e t 、公路网络、神经网络等，也可以是抽象的不可触摸的，如社会关系网 络、科学家合作网络等。各种各样的个体( 蛋白质、神经元、人、城市、国家等等) 组成了网络的基本单元节点，网络的边代表了个体之间存在的某种特定关联，有 边相连的两个节点被看做是相邻的。另外，对于一组节点来讲，如果定义在节点上 的关联关系不同，那么在同样的节点上产生的网络其拓扑结构也不一样。 人类的生活一直处于一个纷繁复杂的网络世界中，人际关系网络、科研合作 网络、产品供应链网络、食物链网络、生物种群网络、金融机构网络等等紧密围绕 在我们周围，成为我们生活中不可或缺的一部分。图1 - 1 、图1 - 2 及图1 3 所示为一 些典型的复杂网络实例。然而我们对于这些网络的拓扑结构、统计特性、形成机 制等却知之甚少。而这样的知识对于有效配置资源、防l t 病毒( 疾病) 传播、维持 图1 - 1 酵母蛋白网络1 1 1 电子科技大学博士学位论文 图i - 2 ( a ) w w w 网络，网络中节点为w w w 文档，边表示u r l 链接【q 。( b ) i n t e r n e t 网络 拓扑【3 l 圈1 - 3 美国成斯康辛州岩湖中的食物网络f 4 系统的稳定性和提高系统的各种功能又是极度重要的。 近年来，随着计算技术、存储技术的迅猛发展，人们得以从真实的数据中寻找 存在于复杂系统的表象之下的内在机制和模式，试图发现影响和支配这些复杂系 统的动态行为和演化规律的本质。而复杂网络的研究将对认识复杂系统的整体行 为、网络中各种扩散和传播行为、网络的演化机制等产生重要影响。 第一章绪论 1 1复杂网络的产生 早期的网络研究属于离散数学中图论的一个分支，研究对象是一些规则图如 二维平面上的欧几里德网格，或者是最近邻环。当时的科学家认为真实系统内部 之间的相互关联关系可以用这样一些规则的拓扑结构来描述。其时，网络研究中 重要的研究成果来自社会科学领域。从大约1 9 2 0 年开始，社会网络分析主要集中 在社会实体之间的关系上，如群组成员之间的交流沟通、国际贸易、公司之间的经 济交易等。n - - 十世纪五十年代末六十年代初，匈牙利的两位伟大的数学家p a u l e r d s s 和a 班6 dp 涵n y i 提出了随机图理论【5 1 1 6 7 ，用以描述没有明显产生规则的大 规模网络。随机图理论在随后的四十年中一直被很多科学家认为是最合适的描述 真实系统的工具。然而，随着计算机处理数据和计算能力的飞速发展，人们发现 现实世界中的大量网络既不是规则的也不是完全随机的，而是具有与传统网络不 同的统计特征的网络：大多数网络都具有平均最短路径较小的小世界效应( s m a l l w o r l de f f e c t ) 【8 】和度分布非均匀的无标度( s c a l ef r e ep r o p e r t y ) 【g 】特性。不仅如此， 网络的拓扑结构可能随时发生变化，网络节点可能增加也可能消失，节点之间的 边随时间可能断开也可能连接；整个网络的动力学行为呈现复杂性，网络中的节 点本身可以是非线性的动力学系统，具有复杂的非线性动力学行为。这样的网络 被科学家称为复杂网络( c o m p l e xn e t w o r k s ) 4 1 n 1 0 。过去的1 0 年间，复杂网络迅速 发展起来，为人们认识世界提供了一种新的视野。 所谓复杂网络，是指那些结构非规则的、复杂的、随时间动态演变的大规模网 络。复杂网络是大量复杂系统得以存在的拓扑基础，因此对复杂网络的研究被认 为是有助于理解“复杂系统之所以复杂”这一至关重要的问题【9 5 】。 1 2 复杂网络简介 我们通常所说的网络是由一组节点以及所有连接节点的边所构成。按照节 点之间相互作用的方向，网络可以分为无向网络( u n d i r e c t e dn e t w o r k ) 和有向网 络( d i r e c t e dn e t w o r k ) 两种。为了定义网络路径的长度，所有的边都采取统一的长 度标准。需要指出的是，在复杂网络的研究中，通常自连接( 边的始点和终点都是 同一个点) 和多重连接( 两个点之间有多于一条的边) 是不考虑的。有向网络的例 子比比皆是，如食物链网络、大脑神经网络、硼删网络等，无向网络普遍存在于 个体之间相互作用且地位相等的复杂系统中，如朋友网络、公路网络等等。另外， 按照是否考虑网络中节点相互作用的强度，网络又可以分为权重网络( w e i g h t e d 3 电子科技大学博士学位论文 n e t w o r k ) 和无权重网络( u n w e i g h t e dn e t w o r k ) 。具体系统属于哪一种网络跟研究 的问题考察的对象密切相关。 自从d w a t t s 和s h s t r o g a t z 以及b a r a b a s i 等人在复杂网络研究上的开创性工 作以来，科学家们提出了许多刻画和度量网络的概念。其中有几个概念至关重要： 平均路径长度、聚类系数、度分布和谱性质。事实上，w a t t s 和s t r o g a t z 最初就是试 图构造一种具有小的平均路长( 像随机网络) 和高聚类系数( 像规则网络) 的网 络。根据这种原则，最后得到了小世界网络模型。无标度网络的发现来自于对许多 大规模网络中节点度的观察，这些网络的节点度原来呈幂指数分布律。这几个概 念在复杂网络的奠基性研究中起到了至关重要的作用，并在之后的研究中它们也 扮演着重要的角色。因此我们下面先来介绍这些概念。 1 2 1复杂网络的统计特性 1 2 1 1平均路径长度 在一个网络中，连接任意两个点i 和j 的最短路径上的边数称为这两个点之间的 距离奶，网络中任意两点之间的距离的最大值称为这个网络的直径d ，即： d = m a x 奶 网络的平均路径长度定义为任意两点之间距离的平均值： l 2 赢b 若奶 m 2 ， 其中为网络中节点数目。一个有趣的现象是，在很多大规模复杂网络中，网络 的平均路径长度都相对较小，即使是在节点间连接很稀疏的网络中也是如此。这 个“小 也就是所谓的小世界效应，也就是小世界网络名称的来源。最为流行的 诠释是“六度分离( s i xd e g r e e so fs e p e r a t i o n ) ，于1 9 6 7 年被社会心理学家s t a n l e y m i l g r a m 所发现。通过一系列的实验，m i l g r a m 断定，在美国绝大多数人最多只要 通过六个人就可以认识其他陌生人。而w a t t s 和s t r o g a t z 在他们发表于1 9 9 8 年的论 文中指出，平均路径长度与网络规模之间存在一定的关系，当网络规模增加时，网 络的平均路径长度通常也将随之增大。若网络平均路径长度的增加是h l 的阶数， 则认为这种网络的平均路径比较小，称之为“小世界 现象。如电影演员合作网络 的平均最短路径长为3 6 5 n ，w 、v w 网络的平均最短路为3 1 【3 】。 4 第一章绪论 冈 c = ic = 1 2c = o 图1 - 4 不同结构下对应的聚类系数 1 2 1 2 聚类系数 ， 社会网络中的一个普遍特点是小集团现象，或者说朋友圈子。一个简单的例 子是在朋友网络中，很容易发现你朋友的朋友也是你的朋友。也就是说，你的两个 朋友，他们之间也是朋友关系。为了刻画网络集团化的程度，定义了一个参数叫聚 类系数( c l u s t e r i n gc o e f f i c i e n t ) 。聚类系数用于衡量网络节点的邻居之间仍然为邻 居的概率有多大。一般地，假设网络中节点i 有k ；个邻居节点，从而有条边。显然， 这k i 个邻居节点之间最多可能的边数为k t ( 一1 ) 2 。而这些邻居节点之间实际存 在的连接数最与最多可能存在的边数之比就定义为节点i 的聚类系数g ，即： g 2 翻( 1 - 3 ) 网络的聚类系数e 即是所有点的聚类系数的均值，即： c = 丙1 g ( 1 4 ) 可以看出，聚类系数是一个在o 至l j l 之间的值。当所有节点均为孤立点或星型结构 时，c 为0 ；当所有点都相互连接时，g 为1 ，这时网络为全连接网络，如图1 4 所示。 在具有个节点的随机网络中，网络的聚类系数c 一1 n 。而实际网络的c 通常远 大于1 n 而小于1 。由此也可以看出，随机网络和全连接的规则网络都不能很好的 描述现实世界中的网络。 1 2 1 3度分布 度是刻画网络局部特征( 节点特征) 的最基本的参数，网络中节点i 的度是指 与之相连的其他节点的个数。然而并非所有网络中的节点都具有相同的度。通 常来说，一个节点的度越大，它在网络中的重要性越大。节点度的散布用分布函 数尸( 南) 来描述，尸( 后) 定义为随机选择一个度为k 的点的概率。最简单的度分布是 5 电子科技大学博士学位论文 全连接的网络，因为每个节点的度都相同，所以分布函数p f 斛是一个d e l t a 函数。 在随机网络中，由于边是随机产生的，因此绝大多数的点都具有相同的度，其度数 接近于平均度 ，从而网络的度分布为泊松分布如图1 - 5 所示。 度分布为泊松分布的还有小世界网络。有趣的是，通过对大量真实网络的统 计分析发现，大多数实际网络的度分布明显偏离泊松分布而呈幂指数分布，即分 布函数p ( k ) k - ，。其中，1 通常介于2 到3 之间。具有这样度分布规律的网络我们 称之为无标度网络。幂律分布在双对数坐标下是一条下降的直线，如图1 - 6 航空网 络的度分布。 1 2 1 4 谱性质 任何一个具有n 个节点的图g 都可以用矩阵且( g ) = ( 如) n 。来表示。任意 p o i s s o nd i s t r i b u t i o n 图1 - 5 美国高速公路网及其对应的度分布p 1 】。其中节点代表城市，边为连接两个城市的高速 公路 6 逵钆 第一章绪论 p o w e r 1 a wd i s t r i b u t i o n 图1 - 6 航空网络图及对应的度分布 3 q 。网络图中，节点为机场，边为机场之间的航线 一对节点。和，之间有连接则a “= 1 ，否则h 。= 0 a 图g 的谱就是它的邻接矩阵 的特征值的集合。谱密度定义如下： p ( a ) 2 嘉6 ( 一 ( 1 - 5 ) 当n 呻o o 时，谱密度函数接近于连续函数。有趣的是谱密度与图的拓扑特征直 接关联着。因为它的第个特征值可以如下表示： 南( a ，) 2 寺a i l , i z ， j 2 l1 1 1 2 “ 1 - 8 ) 即从一点出发叉回到该点的路径数，这些路径中可以包括曾经被访问过的节点 图的谱属性也可以反映图的一些固有性质1 6 s 1 1 6 4 以及动力学上的性质i “l 呻i 。 电子科技大学博士学位论文 p - 0 人 - 、 p - - - 0 1 一厂 岁 7 穴 - i p - - 0 1 5 图1 7e r 随机图随连接概率演化的过程【3 】 1 2 2复杂网络模型 由于经典的规则网络模型无法恰当地反映现实世界中各种网络的统计特性， 人们试图构建各种各样的模型来重现真实网络的性质，探索形成这些网络结构的 各种内在演化机制。其中主要的三种网络模型分别是：e r d 6 sr 6 n y i ( e r ) 随机网 络、小世界网络和无标度网络。 1 2 2 1e r 随机网络 随机网络研究始于2 0 世纪5 0 年代末，由两位匈牙利数学家p a u le r d s s 和a l 矗e d l 髓n y i 提出，简称e r 模型。模型描述如下：假设网络中有个节点，以概率p 随机连 接网络中任意一对节点。这样就生成了一个具有个节点和大约p n ( n 一1 ) 2 条边 的随机图( 如图1 7 所示) 。随机图理论研究的主要问题是确定随机图产生某个特 定性质的概率。随机图网络的平均度为 = p ( n 一1 1 ，度分布为泊松分布。其 平均路径长度l i n 较小，具有典型的小世界特性。但是，e r 随机图的 聚类系数c 1 ，而实际网络的聚类系数远大于随机网络的聚类系数值。 1 2 2 2 小世界网络 通过观察我们发现，虽然随机网络具有小世界特性，但聚类系数很低。而实际 网络并非完全随机的，它既有某种规则性，又有一定的随机性。例如，人们都会认 8 第一章绪论 识自己周围的人，但有一部分人可能还认识离自己更远的人。 为了描述从规则网络到随机网络的转变，1 9 9 8 年w a t t s 和s t r o g a t z ；l 入了一种 称为小世界网络的有趣模型。为了与后来其他人提出的小世界模型相区别，这里 我们把它称为w s 小世界模型吼w s d , 世界模型的基本算法描述如下： l 构造一个具有 个节点每个节点有t 个邻居的最近邻网络。为使生成的网络 稀疏，需满足。 2 对网络中的每一条边而言，虬概率p 断开其中一端并随机选择网络中的其他 节点作为新的端点，并保证节点没有自连接以及节点对之间重复连接。这样， 网络中就产生j p n k 2 条“长程连接”( 或“非局部连接”、“捷径”等) 。通过 改变p 的值，便可u 实现从规则网络4 随机网络的过渡( 见图l 一9 ) ，而小世界 嘲络正是在介于这两种网络之间的一种网络。 在规则网络向随机网络转变的过程中从圈l 一1 0 我们可以看到，网络的聚类 系数和平均路径长度也在随着p 的增加而变化。值得注意的是，在一定的概率下， 聚类系数维持在较大的值而平均路径长度却减小到一个较小的值，这时所对应的 网络结构便是小世界网络。w s 模型结合了规则网络较大的聚类系数和随机网络小 的平均路径长度的特点，很好地再现了真实网络的小世界特性( 如图1 - 8 所示) 。 在以上所给出的w s d , 世界模型中，由于长程连接是通过断开原来的边重新 连接到其他节点上而产生的，因此有可能因为断开边而造成整个网络不连通的情 ( a )【b ) 嘲1 - 8 ( a ) 旧式电视机中模拟电路呵络图( b ) 逻辑电路图 9 电子科技大学博士学位论文 s r n a d d oo 桊 p ；o - 卜p ；1 i n 露瞄蜘g 限饿溯嘲e s s 图1 9 小世界网络随重连概率p 演化的过程。p 的变化导致网络结构从规则向无序迁移【8 1 况。为克服w s 模型中存在的这个缺点，n e w m a n 和w a t t s 对小世界网络的生成模型 进行了修改【3 2 】，提出了n w d 世界模型。在n w + 世界模型中，不需要断开原来的 边，而是以一定概率p 在随机选取的一对节点间增加一条新的边，并排除自连接 以及重复连接的情况。由此一来，当p = 0 时，n w 网络模型就是原来的规则网络； 当p = 1 时则为全耦合网络。研究表明，在p 较小时，n w 模型具有和w s 模型类似 的特性。更加详细的小世界网络特性分析可参见【3 3 】【3 4 】【3 5 】3 5 。在本文后面章节中所讨 论的小世界网络采用了n w 模型算法。 图1 1 0 网络的聚类系数c ( p ) 与平均路径长度l 扫) 随重连概率p 的变化情况【8 】 1 0 第一章绪论 图1 1 l 一个n w t j , w ：界网络模型，由= 3 ，n = 2 4 的规则环产生，长程边数j 勾4 f 4 1 2 2 3无标度网络 随机网络和小世界网络的共同特点是，节点的度都在分布平均度附近，因此也 称为均匀网络。而实验表明，现实世界中的大多数网络并非均匀网络，他们的度分 布服从幂指数分布。而且网络总是在不断演化的。实际网络的生长可从图1 1 2 一 个合作网络图的变化看出来。 为了解释幂指数分布的形成机理，b a r a b 矗s i 和a l b e r t 提出了无标度网络模 型【1 7 1 】，简称b a 模型。b a 模型的生成演化由两个机制决定：增长( g r o w t h ) 和择优 连接( p r e f e r e n t i a la t t a c h m e n t ) 。b a r a b 缸i 等认为，网络不是封闭的静态的，而是一 个不断演化的动态过程。在这个过程中，不断有新的节点加入进来。例如，论文引 用网络中不断有新的文章发表出来，w w w 网络中不断有新的网页添加上去。而 随机网络和小世界网络是静态的模型，网络中节点个数始终是固定的。择优连接 意味着节点之间的连接是有偏好的，新加入的节点更倾向于选择度大的节点连接。 例如已经有高引用率的文章被后来发表的文章再引用的概率总是高于那些引用率 低的文章，而新产生的网页更愿意连接到那些点击率高的网站上等等。这就是所 谓的“富者越富”效应。而在随机网络和小世界网络中，边的连接是等概率的。在 增长和择优连接的双重作用下，无标度网络就产生了。 b a 模型的网络生成算法如下【1 7 1 】： 1 增长：初始时，网络中有m o 个种子节点，每一步新加入的节点都连接到网络 中的m 个节点上，m m o 。 电子科技大学博士学位论文 1 9 8 8 嗨。麓二 岣k 。整镰。 w 唧酝p舡：飘 q n q c m 图1 1 2 生物技术公司、科研实验室以及金融机构之问的联系网络随时问增长示意图 2 择优连接：新加入的点r x - - 定的概率从网络中已有的点中选取m 个点进行 连接，节点。被选中的概率用以下公式计算： ( 护轰( i - 7 ) 其中b 即是点 的度。 由上式可以看出，节点的度。越大，这个点被选中的概率就越大，从而这个点的度 增加的概率也越大。经过t 个时间步之后。算法就生成了一个具有t + m o 个节点、m e 条边的网络，其平均度为 ：2 m 。网络中少数的点具有很高的度，而其他大 多数节点的度很低。这和实际网络的情景比较类似。例如，消费者在购买某类商 第一章绪论 图l 一1 3b a 算法产生的无标度网络其度分布情况f 3 j 3 。( a ) 中各参数分别是：o lm o = m = 1 ； 口：m o = m = 3 ；：m o = m = 5 ；网络规模均为n = 3 0 0 0 0 0 。：m o = m = 7 ，( b ) 中参数 为：o ：n = 1 0 0 0 0 0 ；口：n = 1 5 0 0 0 0 ；0 ：n = 2 0 0 0 0 0 ，对所有，m o = m = 5 。 品时总是倾向于购买销售量好的同类商品。b a 算法的数值模拟( 图1 1 3 所示) 表 明，这种网络模型具有度分布为幂指数分布的特性，且，y = 3 。从图中可以看出，对 于平均度不同的网络，其度分布都服从幂指数分布，在对数一对数坐标系中为一条 斜线。而图1 1 3 ( b ) 显示了相同的平均度下，不同规模的网络其度分布几乎是一 样的。文献 9 1 作者运用平均场理论证明了b a 模型产生的网络度分布呈幂指数分布， 并给出了指数的理论值公式。 1 3 复杂网络的研究内容 继二十世纪末小世界效应和无标度特性的发现之后，有关复杂网络的各种研 究方兴未艾。不同领域的研究者们在不同方向上开展了研究工作【1 1 】，开辟了一些 研究方向。目前，一方面各种新的理论模型和分析方法正不断涌现，另一方面人们 希望用复杂网络理论来理解和解决具体领域的问题。就目前来看，主要的研究工 作包括以下几方面： 一、广泛深入的网络特性分析 复杂网络研究中首要且最基本的问题是结构问题，复杂网络研究正是以寻找 1 3 电子科技大学博士学位论文 和定义能够反映真实网络结构特征的度量开始的。经过科学家们的共同努力，已 经发现了一系列存在于真实网络结构上的普遍特征和共同特性。对更多的、规模 更大的实际网络数据分析可以进一步验证已有的结论、发现新的网络共性，从而 有助于构建更加符合实际的网络模型。事实上，由于获得完整的关于具体复杂系 统的结构数据信息是非常困难的事情，往往能够用于分析的数据只是其中很小一 部分，因此有必要论证局部网络特征是否能够正确反映整个网络的拓扑性质，这 需要未来进一步的实证工作。 二、复杂网络建模 网络特性的经验发现使网络建模复兴起来。因为图论中提出的经典模型已 经被证明与实际网络相差甚远，必须发展新的网络模型以模拟网络的生长过 程以及重现那些在实际网络中观察到的结构属性。除了最初的w a t t s s t r o g a t z t j 、 世界网络模型和b a r a b 五s i a l b e r t ( b a ) 无标度网络模型，研究工作者又相继提 出了其他一些模型。例如，在【z2 】【1 3 】中作者提出并研究了确定性的小世界网络； 文献【1 4 】 1 5 】【16 】【1 7 】【3 】对b a 无标度网络模型进行了改进和推广，提出了各种各样的 无标度网络模型；文献【1 9 】【2 0 】【2 l 】 2 2 】【2 3 】【2 4 j 2 5 】提出了具有社团结构的网络模型；文 献【3 7 1 1 3 s 】【4 0 】【4 1 】依据实际网络的增长机制提出了各种权重网络模型，这些网络模型能 够较好的刻画实际网络中的三种典型幂律分布。以b a 模型为典型代表的一类演化 模型较好的反映了无标度的形成机制，也能在现实世界的网络中印证其模型在一 定程度上的合理性。但它们对于真实网络来说仍然过于简化。真实网络的拓扑结 构总是一组外力持续作用于系统的结果，这种拓扑结构的形成也同时会影响到系 统的功能。因此建立合理的网络模型能够促进人们更好的了解网络的进化机制， 从而更好的理解网络的动态和功能行为。 三、复杂网络上的动力学行为 每个复杂网络都是一个复杂的动力系统，由节点所代表的动力学单元相互作 用构成。复杂网络研究的一个主要课题就是研究网络的动态行为，尤其是对网络 的结构如何影响其动态属性的研究【4 2 4 3 。例如对复杂网络集体同步动力学的研究， 就是将拓扑结构与耦合的动态系统局部特性之间的相互影响与网络的同步联系在 一起。事实上，在许多情况下这种集体行为表现了某些至关重要的特征。如有证据 表明一些大脑疾病是大量神经元反常、有时突然同步引起的结果，因此研究癫痫 的产生、持续和传播的网络机理是当今神经科学的前沿课题。同样，在社会科学领 域，较好的理解社会