（应用数学专业论文）一般拓扑结构复杂网络的时滞同步牵制控制.pdf

江苏大学硕士学位论文 摘要 近年来复杂网络已受到科学界和工程界等各个领域的广泛关 注，复杂网络己成为一个新的研究热点。尤其是研究复杂网络的动 态行为，如网络同步，对于人们深刻理解和应用复杂网络具有重要 的理论和实际意义。 本文分为三部分。第一部分给出了复杂网络的研究背景和其基本 理论。第二部分讨论了规则网络、随机网络、小世界网络和无标度 网络的特征及同步问题。第三部分主要讨论了一般复杂动态网络的 同步判据，尤其是具有时滞延迟的网络。我们提出了连续时间和离 散时间条件下具有混合时滞的一般复杂动态网络的牵制同步问题， 给出了反馈控制器，基于主稳定方程( m s f ) 应用矩阵线性不等式 ( l m i ) 得到了一般稳定原则。应用了m a t l a bl m it o o l b o x 软件进 行了数值模拟与仿真，其结果显示了方法的有效性。 关键词：复杂网络，同步，时滞，牵制控制 江苏大学硕士学位论文 a b s t r a c t c o m p l e xn e t w o r kb e c o m e san e wr e s e a r c h i n gf o c u s ，i tc a u s e sac o n s i d e r a b a l e i n t e r e s ti nm a n yf i e l d s ，s u c ha ss c i e n c ea n de n g i n e e r i n g t h es t u d yo ft h ed y n a m i c b e h a v i o ro fc o m p l e xn e t w o r k , s u c ha st h es y n c h r o n i z a t i o n ，h a si m p o r t a n tt h e o r e t i c a l a n d p r a c t i c a ls i g n i f i c a n c ef o ro n ep r o f o u n d l yu n d e r s t a n d i n ga n da p p l i c a t i o no fi t 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 e p r e s e n tt h e r e s e a r c hb a c k g r o u n da n df u n d a m e n t a lt h e o r i e so ft h e c o m p l e xn e t w o r k s i nt h e s e c o n dp a r t ，w ed i s c u s st h ep r o p e r t i e sa n dt h es y n c h r o n i z a t i o no ft h er e g u l a rn e t w o r k , r a n d o mn e t w o r k , s m a l l - w o r l dn e t w o r ka n ds c a l e f t e e n e t w o r k t h et h i r dp a r t ，m a i n l y d i s c u s st h e g e n e r a ls y n c h r o n i z a t i o nc r i t e r i o nf o rg e n e r a lt o p o l o g yn e t w o r k s ， e s p e c i a l l yt h o s ew i mh o m o g e n e o u st i m e d e l a y s w ep r e s e n tp i n n i n gc o n t r o lo f c o m p l e xn e t w o r kw i t hg e n e r a lt o p o l o g ya n dh e t e r o g e n e o u st i m e - d e l a yi nb o t h c o n t i n u o u s t i m ea n dd i s c r e t e - t i m ed o m a i n s m a i n l yc o n t r i b u t i o n sa r et h eg a v e no f s i m p l ef e e d b a c kc o n t r o l l e r sa n ds o m eg e n e r i cs t a b i l i t yc r i t e r i ab a s e do nt h ei d e a so f m s f ( m a s t e rs t a b i l i t yf u n c t i o n ) a n dt h el m i ( 1 i n e a rm a t r i xi n e q u a l i t i e s ) c r i t e r i o n i n t h ep a r to ft h en u m e r i c a ls i m u l a t i o n ，m a i n l ya p p l i e st h em a q l a bl m it o o l b o x s o f t w a r et h a ts h o w st h ee f f e c t i v e n e s so ft h em e t h o d k e yw o r d s ：c o m p l e xn e t w o r k ，s y n c h r o n i z a t i o n ，t i m e - d e l a y , p i n n i n gc o t r o l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 位保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 学位论文作者签名：靠彬曾勇 指导教师签 二呷年，2 月2 7 日 巧和明叫日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已注明引用的内容以外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要页献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：砷年1 , 2 - 月2 日 童彬普勇 江苏大学硕士学位论文 1 1 本课题的研究背景 第一章绪论 自2 0 世纪9 0 年代以来，以因特网为代表的信息技术的迅猛发展使人类社会 跨步迈进了网络时代，如今可以说，人们已经生活在一个充满着各种各样的复杂 网络的世界中，如因特网、万维网、通讯网络、经济网络、交通网络、神经网络、 生物网络、电力网络、社会网络、食物链网络等等，它们有些分属不同学科的研 究内容，而这些看上去各不相同的网络之间有着许多惊人的相似之处，复杂网络 理论所要研究的就是各种看上去互不相同的复杂网络之间的共性和处理它们的 普适方法。自上世纪末开始，复杂网络研究正渗透到数理科学、生命科学、工程 科学等众多不同学科领域，对复杂网络的定量与定性的科学分析，已经成为网络 时代科学研究中的一个具有挑战性的重要课题，甚至被称作为“网络的新科学” 【4 ，7 】 0 复杂网络中的同步的研究基础涉及到图论、统计物理学、非线性动力学和复 杂性科学等领域的科学研究。复杂网络受到各个学科领域的科研工作者的关注， 而不仅仅局限于数学和物理领域。复杂网络的研究具有深远的现实意义。它已经 渗透到管理学科、工程理论等众多学科，是一门综合了数学、物理、计算机、管 理等学科的跨学科研究课题。在我们生活中，很多问题都涉及到了复杂网络的研 究，如传染病在人类社会以及动物界中的传播，电力网络中局部小的故障引发的 大面积的停电事故，交通网络的优化等一些现实中急需解决的问题。在以物理学 家和数学家为代表的广大科研工作者的努力下，复杂网络理论得到了很大的发 展。 人们普遍关心的一个问题是复杂网络的生成过程和其形成机制，也就是网络 的来源和形成问题。网络本身的生长演化过程是一个非常有趣的问题。每一种类 型的网络的生长都有其自身的独特的性质，有其紧密联系在一起的一些特有现 象，这些都和网络其自身的演化和生长机制有关。建立在研究网络的生成机制基 础上，人们可以探索复杂网络上的动力学行为。例如传染病或者谣言在社会关系 江苏大学硕士学位论文 网络上的传播，病毒在互联网上传播和扩散，非线性振子组成的复杂网络的行为 预测和控制等。同时，也可以研究网络的同步稳定性和自身的稳定性等与网络拓 扑结构的关系。研究网络的形成机制、网络的几何性质、网络生长的规律、网络 上的动力学模型，以及网络的结构稳定性，并把它们与现实生活中的具体系统结 合起来，这是复杂网络研究的中心内容。可以期望，复杂网络的研究最终会揭示 各种不同的复杂系统中的普适性和各个系统的独特性，加深了我们对于广泛的实 际应用领域中根本规律的理解。 1 2 本课题的研究现状和发展前景 网络连接结构看上去错综复杂、极其混乱的，如图卜1 、卜2 分别是堪培拉 城市社会人际关系和某食物链中捕食与被捕食关系结构模拟示意图。而数学家和 物理学家在考虑网络时，往往只关心节点之间是否相连，至于节点的位置，边的 长短、是弯曲的还是平直的、有没有相交等等都是他们不在意的。在这里，我们 把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络 的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适 合用来描述真实的系统呢? 在丌始的一百多年里，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看 起来像是格子衬衫上的花纹；又或者如最近邻环网，它总是会让你想到一群手牵 着手围着篝火跳圆圈舞的姑娘。二十世纪五十年代末，数学家们想出了一种新的 构造网络的方法，在此方法下，两个节点之间是否有边相连不再是确定的事情， 而是由一个概率决定的。数学家把这样生成的网络叫做随机网络，它在接下来的 四十年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几年， 由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不 是规则的，也不是随机的，而是与前两者皆不相同的统计特征的网络。这样的一 些网络被科学家们叫做复杂网络( c o m p l e xn e t w o r k s ) 。 任何一个网络都可以看作是由一些节点按某种方式连接在一起而构成的一 个系统。具体网络的抽象表示，就是用点表示具体网络中的节点，并用节点之间 的连线来表示具体网络中节点之间的连接关系。 2 江苏太学硕士学位论文 曩 图1 - 1 社会州络 图1 - 2 食物链网络 f i 9 1 - 1s o c i a ln e t w o r k f 瑭1 - 2 f o o dc h a i n s n e t w o r k 实际网络的罔表示方法可以追溯到1 7 3 6 年伟大的数学家欧拉对著名的 “k o n i g s b c r g 七桥问题1 1 , 2 1 ”的研究，开创了数学中的一个分支图论 ( g r a p h 。f e h o r y ) 的研究。事实上，关于复杂网络的研究和欧拉当年对“七桥问题” 的研究扯某种程度上是一脉相承的及网络结构与网络性质密切相关。欧拉利用 数学抽象法，将被河流分开的四块陆地抽象的分为四个点，连接着四块陆地的七 座桥抽象为连接四个点的七条线，如图卜3 所示。 d b 图卜3k o n i g s b e r g 七桥问题图示 f k l - 3 d i a g r a m o f k o d i g s b c r g b r i d g e 欧拉将问题转化为研究一笔画成的图形，得出七桥问题足没有解的。在欧拉 解决七桥问题之后的相当长一段时间罩，图论并末获得足眵的发展，直到1 9 3 6 年出版了第一部图论专著才使图论开始进入发展与突破的快车道。2 0 世纪6 0 午代，由两似匈牙利数学家e r d o s 和r e n y i 建立的随机图 仑( r a n d o mg r a p h t h e o r y ) 【q 被公认为是在数学上，f 创了复杂网络理论的系统性研究。在此后的4 0 鬣 一一 江苏大学硕士学位论文 年内，随机图理论一直是研究复杂网络【6 1 的基本理论，在此期间，人们也做了试 图揭示社会网络的特征的一些实验，m i l g r a m 在1 9 6 7 年5 月发表于美国出版的 今同心理学杂志上的一篇论文中描述了社会网络的小世界特性。接下来，为 检验“六度分离”假设的j 下确性，人们又做了诸如著名的“k e v i nb a c o n 游戏 ， 又提出了e r d o s 数，2 0 0 3 年8 月在s c i e n c e 杂志上报道了i n t e r n e t 上的小世界 实验。g r a n o v e t t e r1 9 7 3 年在美国社会学上发表的题为弱连接的强度 ( s t r e n g t ho fw e a kt ie s ) 的论文现已被认为是有史以来最有影响的社会学论 文之一。2 0 世纪即将结束之际，也结束了长达4 0 年之久的单一应用随机图理论 研究复杂网络的年代。有两篇开创性的文章可以看作是复杂网络研究新纪元丌始 的标志：一篇是美国康奈尔( c o r n e l l ) 大学的w a t t s 及其导师s t r o g a t z 教授于 1 9 9 8 年6 月在n a t u r e 杂志上发表的题为“小世界”网络的集体动力学的文 章 9 1 ：另一篇是美国n o t r e d a m e 大学的b a r a b a s i 教授及其博士生a l b e r t 于1 9 9 9 年1 0 月在s c i e n e e 杂志上发表的题为随机网络中标度的涌现的文章【1 0 1 。这 两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型 以阐述这些特性的产生机理。 近年有关复杂网络的研究在节点数上达到几万甚至几百力 ，远远大于过去的 几十几百，网络规模上尺度的变化又促使网络分析方法作出相应的改变，甚至于 网络的提出方法的改变。就目前而言，复杂网络理论的主要研究内容可以归为以 下几点： 发现：揭示n , m i 网络系统结构的统计性质，以及度量这些性质的合适方法。 建模：建立合适的网络模型以帮助人们理解这些统计性质的意义与产生机 理。 分析：基于单个节点的特性和整个网络的结构性质分析与预测网络的行 为。 控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、 同步性和数据流通等方面。 4 江苏大学硕士学位论文 1 3 本文的研究内容 复杂网络很普遍的一个现象，就是网络中节点之间的同步化行为。事实上同 步现象是宇宙当中最朴实的现象。有关同步现象的科学研究，可以追溯到1 6 6 5 年荷兰物理学家惠更斯对于两个挂钟钟摆同步摆动的有趣现象的观察研究，两个 钟摆不管从什么不同的初始位置出发，经过一段时间以后它们总会趋向于同步摆 动。1 6 8 0 年，荷兰旅行家k e m p f e r 在泰国旅行，沿湄南河发现了成千上万只萤 火虫同步闪光的一种奇特的生物现象。2 0 0 0 年6 月1 0 同，成千上万的伦敦市民 和游客涌向用近7 0 0 吨钢铁铸成的伦敦千年桥时，人们杂乱无章的步伐引起了大 桥的振动，摆动偏差高达2 0 厘米。尽管在很长的一段时问里人们并不了解这些 自然现象的同步机理，人们却在物理、化学、生物、工程技术以及社会和经济等 领域内看到了或者实现了各种各样的同步现象。 耦合动力学系统( 复杂动态网络) 中同步现象的科学研究已有多年历史，但 过去大量的研究都集中在具有规则拓扑结构的网络上，如耦合映象格子和细胞神 经网络，对这些结构比较简单的网络的研究，重点在网络节点的动力学所产生的 复杂行为上，而忽略了网络结构复杂性对网络整体动力行为的影响，然而网络的 拓扑结构在决定网络动态特性方面有很重要的影响。最近几年中，各种复杂网络 共有的小世界和无标度特性的发现使得人们开始关注网络拓扑结构与网络同步 化行为之间的关系，另外，d h a m a l a 等人发现通过改变时滞可以提高系统的同步 能力，时滞并不总是破坏同步流行的稳定性，选取适当的参数时滞反而会镇定同 步流行。 本文在前两章主要给出了一些研究背景及基本概念理论，第三章给出了几种 特殊网络的同步，第四章给出了网络同步的判据，在研究中主要是利用网络中结 点之间的耦合状态以及节点可能存在的滞后特性，采用负反馈控制的方法，利用 线性矩阵不等式这个工具实现了网络的最终同步，这里主要运用l y a p u n o v 稳定 性、连接图理论。研究中既考虑到了连续时间网络又考虑到了离散时问网络，有 特殊网络又有一般网络。 5 江苏大学硕士学位论文 第二章基本概念和基本理论 2 1 常用基本概念 本节介绍复杂网络的有关基本概念，主要给出了平均路径长度、聚类系数、 度与度分布、介数【2 3 】。 2 1 1 平均路径长度 不失一般性可以认为网络为连通的，如果网络是不连通的话，仅把下面描述 略作修改即可。网络中任一对节点k 和巧之间的距离办定义为连接这一对节点的 最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径 ( d i a m e t e r ) ，记为 d = i 码蛏比 ( 2 1 ) 进一步可以定义网络的平均路径长度上，它是指任意两个节点之间的距离的平均 值，即 工2 丽1 一v z d , ，或三2 丽1 1 ) z 纠d 玎 ( 2 2 ) 前一个式中求和是对网络中所有节点对进行的。网络的平均路径长度也称为网络 的特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 。这个量在统计意义上反映了 网络中任意两个节点发生联系所要通过的平均节点数目，即网络中节点的分离程 度。 相似地，可以定义网络的效率( e f f i c i e n c y ) ： e ： ! y 上( 2 3 ) n ( n 一1 ) - 畋 式中求和是对网络中所有节点对进行的。 2 1 2 聚类系数 网络中的每一个节点都通过节点之间的连线与若干个其它节点相连接，现 假设网络中的一个节点m 与网络中其它毛个互不相同的节点直接连接，这屯个 6 江苏大学硕士学位论文 节点称为节点m 的邻居。如果此毛个节点完全相互连接，则应当有也( 屯- 1 ) 2 条 节点之间的连线，而在讨论的网络中事实上只有巨条节点之间连线，为此我们 可以定义这个节点的聚类系数为 c ：三乓 ( 2 4 ) 毛( 屯一1 ) 即恕个节点之间实际存在的边数和总的可能的边数之比。 进一步，从节点的聚类系数出发可以定义整个网络的聚类系数为所有节点的 聚类系数的平均值： c = 专车g ( 2 5 ) 其中求和是对网络中所有节点进行的。这个量从统计意义上反映了网络中节点的 平均聚集程度，即节点之间连接的紧密程度。 0 c 1 。且当c = 0 时所有的节点都是孤立的点，没有任何的连接；当c = 1 时表示网络中任意两个节点都直接连接，即节点是充分聚集的。 事实上，很多类型的网络( 如社会关系网络) 中，你的朋友的朋友同时也是 你的朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当一0 0 时， c = d ( 1 ) 。这就意味着这些实际网络并不是完全随机的，而是在某种程度上具有类似丁社 会关系网络中“物以类聚，人以群分”的特性。 2 1 3 度与度分布 在无向网络中，节点k 的度( d e g r e e ) 毛定义为与该节点直接连接的其他节 点的数目( 实际上也是此节点与其他节点连接的边数) 。而在有向网络中，一个 节点的度分为出度( o u t d e g r e e ) 和入度( i n d e g r e e ) 。出度是指从该节点指向 其他节点的边数，入度是指从其他节点指向此节点的边数。直观上来说，一个节 点的度表明此节点在网络中的重要性，度越大说明此节点在某种意义上就越重 要。 网络中所有节点的度的平均值称为网络的平均度，记为( 后) = l 包i n 。 ， r、 、i ：1 江苏大学硕士学位论文 反映网络结构的另一个重要参数是网络中节点的度分布函数 p ( 七) ( 七= 1 2 ，) ，这个量是指如果我们随机地从网络中取一个节点，它的度是 k 的概率为p ( k ) ，其中每个节点都是等可能地被选取。从数学上来看，它的表达 式可以写成： p ( 足) = 熹 ( 2 6 ) 其中表示网络中所有度为k 的节点总数。 全局耦合的规则网络的度分布是d e l t a 分布，它是单个尖峰。网络中的任何 随机化连接都会使得这个尖峰的形状变宽。完全随机的网络的度分布近似为泊松 ( p o i s s o n ) 分布。 近年来，人们还把聚类系数的概念推广到讨论度为k 的节点聚类系数，其表 达式为： c ( 七) _ 傀 - e ；c t ( 2 7 ) 其中求和是对所有度为k 的节点进行。 - k ( 矗) p o i s s o nd i s t r i t a t t i o n ( a ) ( b ) p o w e r - l a wd i s t r i b u t i o n ( 1 0 9 - l o gp l o t ) ( b ) 图2 - 1 两种分布的对比 ( a ) 泊松分布( b ) 幂率分布 ( a ) p o i s s o nd i s t r i b u t i o nc o ) p o w e r - l a wd i s t r i b u t i o n 从泊松分布的度分布图中可以看到，k 接近( k ) 时取到最大值，而当k 远离 ( k ) 时曲线指数衰减。和前面的d e l t a 分布相似，这说明了k 值太大或者太小， 具有这样的度的节点几乎不存在。换句话说，网络中的每个节点具有几乎相同的 度，这样的网络通常称为是均匀网络( h o m o g e n e o u sn e t w o r k ) 。 很容易证明( 数值上) 当网络的随机性减少，即越来越规则时，p o i s s o n 分 8 江苏大学硕士学位论文 布曲线会越米越窄趋向于d e l t a 分布。介tp o i s s o n 分布和d e l t a 分布之间的分 布可以用如下形式的幂律函数描述：p ( k ) k ，其l o g 函数曲线如图b 所示。 很明显幂律分布的l o g 函数曲线线性衰减，比p o i s s o n 分布的衰减慢得多。幂律 分布也称为无标度( s c a l e f r e e ) 分布，因为此分布具有如下无标度性质： 无标度条件：考虑一个概率分布函数厂( 功，如果对任意给定的常数a ，存在 常数b 使得函数，( 砷满足f ( a x ) = b f ( 力，则称它具有无标度性质。 定理：假设厂( 力具有无标度性质，且满足厂( 1 ) 0 ，则厂( 功由下式唯一确定： 厂( 功= 厂( 1 ) x ，y = 一f ( 1 ) 厂( 1 ) 。 在一个度分布具有适当幂指数( 通常为2 y 3 ) 的幂律形式的大规模无 标度网络中，绝大部分的节点的度相对很低，但存在少量的度相对高的节点。因 此这类网络也称为非均匀异质网络( i n h o m o g e n e o u s h e t e r o g e n e o u sn e t w o r k ) ， 而那些度相对很高的节点称为网络的集线器( h u b ) 。 另外一种表示度数据的方法是绘制累积度分布函数( c u m u l a t i v ed e g r e e d i s t r i b u t i o nf u n c t i o n ) 只= p ，) ，它表示的是度不小于七的节点的概率分 k = t 布。如果度分布为幂律分布，即p ( 七) k 一，那么累积度分布函数符合幂指数为 y - 1 的幂律，即最一( 后，) 一，一七啪川；如果度分布为指数分布，即 k = t p ( k ) p - k l x ( r 0 ) ，那么累积度分布函数也是指数型的，且具有相同的指数： 最一p 7 。一e t 肛。幂律分布在对数坐标系中对应于一条直线，而指数分布在 k = i 半对数坐标系中对应于一条直线，因此分别通过采用对数坐标系和半对数坐标系 就可以很容易识别幂律和指数分布。 2 1 4 介数 为了讨论网络上节点在信息传播中的不同作用，还可以引进节点的介数 ( b e t w e e n n e s s ) 概念。不失一般性，可以合理地假定信息传播是沿着两个节点 9 江苏大学硕士学位论文 之间的连线进行。现在我们考虑网络中一个节点h 的介数为： 包= ( f ) ( 2 8 ) j , k ( f ) 代表连接结点_ 和结点屹之间通过结点k 的最短路径的条数。很明显，这 个概念表明节点k 在网络信息传播中的重要性，它与信息的载量有关。进一步， 这个概念可以推广到连线的介数，即经过此边的最短路径的数目。 2 2 常见网络模型 研究网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需 要对实际网络的特征有所了解，并在此基础上建立合适的网络模型。人们已经对 存在于不同领域的大量实际网络的拓扑结构进行了广泛的实证性研究，人们在此 基础上有从不同的提出了各种各样的网络拓扑结构模型。2 0 0 3 年之i j 提出的主 要模型已有综述【1 1 , 1 2 。 2 2 1 规则网络 所谓规则网络是指一类网络中的结点之间连线是以固定规则建立的网络。一 般来说，当建立连线的规则为己知时，我们可以解析计算得到描述这个网络的数 字特征。下面就三种规则网络，即全局耦合网络、最近邻耦合网络和星形网络进 行说明。 ( 1 ) 全局耦合网络( f u l l yc o n n e c t e dn e t w o r k ) 由个节点构成的网络中，任意两个节点之间都有边直接相连。其邻接矩阵 为a = 01 10 1 1 1 1 。1 0 ；网络中任意两个节点之问的距离为略= 1 ，于是网络的直 径。= 1 ， 平均路径长度为工= ( 1 圭( r e 一1 ) ) 蔷略= 1 ； 聚类系数为 c = o n ) c ：f = 1 ，其中q = 2 e , 色( 也一1 ) = 1 ；每个节点都与其他n - 1 个节点 1 0 江苏大学硕士学位论文 相连，因此每个节点的度为一1 ，其度分布为p ( 一1 ) = 1 p ( 肌) = 0 ，m n 一1 即 为d e l t a 分布。这说明全局耦合网络具有最小的平均路径长度和最大的聚类系 数。此网络模型具有最多的边数，但是大多数的实际网络都是很稀疏的。 ( 2 ) 最近邻耦合网络( n e a r e s t n e i g h b o rc o u p l e dn e t w o r k ) 一个得到大量研究的稀疏的规则网络是最近邻耦合网络，其中每个节点只和 它周围的邻居点相连。模型如下建立：把一个圆周等分为份，在每个等分点 上安置一个节点，每个节点与其两边最邻近的k 个邻居相连，这里k 1 个最临近邻居节点外，所有到v 的距离都减少k 一1 ，因此总的减少量为( k 一1 ) ( m 一( k 一1 ) ) ，因此此时网络的平均路径长度为 l r = 一a ( 一1 ) q 彳一k + 1 ) m m ( m 一1 ) 丝= ! 专。 聚类系数：当k = 1 时，此网络就是一个环形网络( 无全三角形) ，这时为 = o 。当k = 2 时，此网络如图2 4 所示。 很明显，对于每一个节点都有6 个三元组和3 个全三角形，因此：要。应用 数学归纳法可以得出此网络的聚类系数为2 3 ( k 一1 ) 2 ( 2 k 一1 ) 马三。 由于每个节点都与其他2 k 个节点相连，因此每个节点的度为2 k ，其度分布 为p ( 2 k ) = 1 ，p ( m ) = 0 ，m 2 k ，也为d e l t a 分布。 ( 3 ) 星形网络( s t a rc o u p l e dn e t w o r k ) 江苏大学硕士学位论文 对于一个含有个节点的星形网络，每个节点都和中间的一个节点直接相 连。其邻接矩阵为a = 0l11 11 1000 00 10 o0 0o 平均路径长度：中间的节点含有n 1 条边，而每个其他的节点和中i 司节点有 条边相连，到其他节点的边数为2 ，因此总共有1 + 2 ( - 2 ) 条边，除了中间节 点之外共有 n 1个这样的节点，于是共有 一1 ) + 州- 1 ) ( 1 + 2 ( n 一2 ) ) = ( n - 1 ) + ( n 一1 ) ( 2 n 一3 ) 条边， 于是平均路径长度为 l = ( 1 n ( n - 1 ) ) 略= ( ( 一1 ) + ( 一1 ) ( 2 一3 ) ) ( 一1 ) = 2 - 2 n 。 聚类系数：由于此网络中没有全三角形，聚类系数e 栅= 0 。 度与度分布：此网络中中间节点的度为n - 1 ，而其他节点的度均为1 。于是 其度分布为：p ( 一1 ) = 1 p ( 1 ) = 一1 ，p ( m ) = 0 ，m 1 ，一1 么嬲愈 囊聒热么 飞落瓣藕歹 飞圈杉 钐 一彳 p 、 图2 2 全局耦合网络 图2 - 3 最近邻耦合网络图2 _ 4 星形网络 f i g2 2t h eg l o b a l l yc o u p l e dn e t w o r k f 塘2 - 3t h en e a r e s t n e i g h b o rc o u p l e dn e t w o r k f 噜2 _ 4t h es t a rc o u p l e dn e t w o r k 2 2 2 随机网络 和规则网络完全相反的是随机网络，典型的例子就是e r ( e r d 5 s 和r 6 n y i ) 随机图【8 】，具体形成过程如下：给个独立的节点，然后随机地拿起两个节点以 概率p ( 服从均匀分布) 将他们相连，然后将这两个节点放回继续此过程。这样 的过程莺复多次后停止，由此产生的网络图有州一1 ) 2 条边，称为是e r 随机 江苏大学硕士学位论文 图网络。 对于每个节点都有n - 1 个邻居会与之相连，而相连的概率为p ，因此这个 节点在整个形成随机网络的过程巾可能会有p ( 一1 ) 条边连接，因此网络的平均 度为( t ) 肼= p ( n 一1 ) * p n 。设e r 随机图的平均路径长度为。从直观上来看， 从睐随机图中任意取一点，网络中人概有( t ) 嚣个节点和该点的距离等于或者近 似等于，田此n * 女) ：，刘、f 均路径长度k * i n l l l ( ) 皿- 注意到每一 对节点小管他们有没有基刊的邻居，都以概率p 相连，因此网络的聚类系数为 c = p z ( t ) ，n 1 。若同定【讯随机图的平均度( t ) 不变，则对于充分大的， 由j + 每条边的出现都是随机的，啸随机圈的度分布可用泊松分布来表示 帅( 舻以l 刊“* ( # 。k o e ，其中为( 啪 闰25 随机网络 f i 9 2 - 5s t o e h a s l i en e t w o r k 注意：平均路径长度等于| 尚9 络生长速度的对数函数这特征是一典型的小世 界性质。凼为对数函数i n n 随v 增长得很慢，这也说明了这类大网络有相对较 小的平均路径长度。但是e r 随机州络并不是小世界网络，凼为它不具备小世界 网络的另外一个特征，即具有大的聚类系数。 223 小世界网络 从直觉上看，嘲络的平均路程k 度l 越小和聚集系数c 越大，应该越有利于 网络i i 信息的传播。町足最近邻网络只有工人和c 人的特点，而呲随机罔义只 江苏大学硕士学位论文 有小和c 小的特点，两者都不具有直觉上所希望的特点，那么由复杂系统实测 所构造的网络呢? 相关得资料表明许多由复杂系统实测所构造的网络都具有平 均路程长度三较小和聚类系数c 与相对应的随机图相比较大的特点，现在我们称 具有这样性质的网络为小世界网络。这是介于规则网络和随机网络之间的一类网 络。那么如何构造小世界网络呢? 作为从完全规则网络到完全随机网络的过渡，w a t t s 和s t r o g a t z 于1 9 9 8 年 在“n a t u r e ”杂志上首次发表构造小世界网络的文章。现在都把这个模型称为 w s 小世界模型1 9 】。这个模型的具体构造方法如下： ( 1 ) 先把一个圆周等分，在每一个等分点上放一节点，共有个节点，每 个节点与它两边2 七个邻近的节点用连线连结( 每一边的邻近节点为k 个) ，一般 要求n k i n ( ) 1 。 ( 2 ) 把上述规则网络中的每一条连线以概率p 进行重新连接，在重新连接 中要求不能产生结点连接自身的连线和两个节点之间不能产生两条或两条以上 连线。也就是说在这个过程中产生p k n 条长程连线。 由数值计算得到在很大的一段概率p 范围内所产生的网络具有小世界性质， 即平均路程长度比较小和聚类系数比较大。事实上，可以把小世界网络看成规则 网络( p = 0 ) 和e r 随机图( p = 1 ) 之| 、日j 随着随机性增加所产生的网络。 w s 小世界模型的构造中随机化过程可能会破坏网络的连通性。另外一个研 究最多的是n e w m a n n 和w a t t s 提出的n w 小世界模型1 1 】，构造方法如下： ( 1 ) 先把一个圆周等分，在每一个等分点上放一节点，共有个节点，每 个节点与它两边2 七个邻近的节点用连线连结( 每一边的邻近节点为k 个) ，一般 要求n k i n ( ) 1 。 ( 2 ) 在上述规则网络中随机加边，即以概率p 随机选取两个节点并加上一 条边，要求不能产生结点连接自身的连线和两个节点之问不能产生两条或两条以 上连线。 此网络当p = 0 时对应的是最近邻耦合网络，p = l 时对应的是全局耦合网络， 比w s 模型在理论分析上简单一些。 1 4 江苏大学硕士学位论文 一 吣 图2 - 6 小世界网络模型 a ) w s 小世界模型b ) n w 小世界模型 f i g 2 6s m a l ln e t w o r km o d e l a ) w ss m a l l 。w o r l d m o d e lb ) m vs m a l l 。_ w o d d m o d e l 下面介绍一些统计性质： c ( p ) 2 耥) 3 n w 小世界网络的为【1 5 】 c ( p ) 2 硒j 3 而( k - 丽2 ) 平均路径长度：w s 小世界网络的为【1 1 1 及p ) = 2 一n kf ( 2 n p k ) 其中厂( 力= a i n z 为二姜三( 一般地c = 1 4 ) 。 n w 小世界网络的为【1 7 1 m ，丽去一叫南 ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 4 苏大学硕士学位论文 度分布：w s 小世界网络的节点度分布为1 1 5 j 肿) = 专”p k - 型( kk ! - n ) s 。尚= 矾( 2 1 3 ) 当k k 时，p 忙) = 0 。 n w 小世界网络的度分布为 黔忆羔) 时5 0 一静“， 亿 l o k 置 2 24 无标度网络 从前面的介绍中我们己经知道规则网络和e r 随机图的度分布分别为d e l t a 函数和p o i s s o n 分布，于是一个自然的问题是由复杂系统实测所得网络的度分布 是怎么样的呢? 实测结果表明是满足于幂律分布，即有e ( k ) * k ，其中，被称 为幂律指数。在社会、生物、信息和技术领域内存在大量的实测网络的度分布满 足幂律分布，其中幂律指数满足2 y o ； y 似f ) 对时间t 的导数矿似t ) 负定且有界，即存在一个连续的非减标量函 数州h b ，其中7 ( o ) = o ，使对一切f 岛和一切x o 成立矿似f ) - - r ( xb - t o 。满足如下的条件： y ( 力为正定且有界；矿( x ，f ) 负半定且有界， 则系统原点平衡状态为q 域内一致稳定。 对于定常系统，有如下形式的判别定理： 结论5 对于定常系统( 2 2 0 ) 式，如果存在一个具有连续一阶偏导数的标量函 数v ( x ，t ) ，v ( o ，t ) = 0 ，和围绕原点的一个吸引区q ，使对一切工q 和一切f - - - t o 满足如下的条件： y ( 功为正定；矿( z ，f ) 为负半定， 则系统原点平衡状态为q 域内一致稳定。 1 9 江苏大学硕士学位论文 2 3 2 线性矩阵不等式( l ) 矩阵线性不等式是指具有如f 形式的表达式： f ( 砷= f o + 葺e + + x 。l 0 ( 2 2 1 ) 其中五，是m 个实数变量，称为线性矩阵不等式( 2 2 1 ) 的决策变量， x = ( 五，) r r ”是由决策变量构成的向量，称为决策向量，互= 互re r “”， i = 0 ，1 ，m 是一组给定的实对称矩阵，式2 2 1 中的不等号” ”指的是矩阵f ( 力 是负定的，即对所有非零的向量1 ，尺”，伊f ( 力 ， 0 ，或者f ( 功的最大特征值小 于零。 定理2 一对给定的对称矩阵s = ( 未乏 ，其中墨。，是，维的。以下三个 条件是等价的： s o ；墨1 o ，$ 2 2 一甜s 2 o ； o ，一s 2 - 2 1 墨2 0 是 滞后时间，f p ( t ) c 1 一d ，0 】是系统的初始条件。 定理2 - 2 对系统( 2 2 2 ) 式，如果存在对称正定矩阵p ，s r “4 ，使得 p p 竺 o ( 2 2 3 ) l鬈p- s 一 7 则系统2 2 2 式是渐近稳定的。 如果存在矩阵a 的一个分解a = b d ，b r n 。m ，de r “其中m = r a n k ( a ) ， 显然m , 。 定理2 - 3 对系统( 2 2 2 ) 式，如果存在对称正定矩阵p s r “，使得 江苏大学硕士学位论文 r p + p a ，+ d 忉朋 o l b r psj 一 则系统( 2 2 2 ) 式是渐近稳定的。 2 1 ( 2 2 4 ) 江苏大学硕士学位论文 第三章复杂动态网络完全同步 3 1 规则网络的完全同步 3 1 1 网络类型i 若对应的同步区域为墨= ( 一o o ，q ) ，哪 q 0 ，且有网络的耦合强度和外耦 合矩阵的特征值关系c 五 呸，即满足同步判掘 0 堕 c 五 ( 3 1 ) 那么同步流形是渐进稳定的。不难看出，属于类型i 的网络同步化能力由外耦合 矩阵的第二大特征值五确定，五越小其同步化能力越强。 对于节点数为偶数k 的最近邻耦合动态网络，其外耦合矩阵是一个特殊的 循环矩阵，如， 一21o 一21 12 ： o o o o 1 12 o12 g 2 第二大特征值为k ，：= _ 4 s i n 2 ( 弦) ，因为k 任意，故当网络规模j0 0 时， i = t ：单调增并趋于零，这意味着当网络规模很大时，最邻近网络几乎无法达到 同步。 全局耦合网络所对应的耦合矩阵