（应用数学专业论文）复杂网络与同步控制.pdf

江苏大学硕士学位论文 摘要 1 9 9 8 年w a t t s 和s 廿0 9a _ t z 在n a t u r e 上发表一篇关于小世界网络模型的文章，越来越 多的国内外的学者集中到复杂网络的研究上。复杂网络成为图论、统计物理学、计算机 网络、生态学、社会学以及经济学等各个不同领域的研究焦点。1 9 9 9 年b a r a b h s i 和a l b e r t 在s c i e n c e 上提出无标度( s c a l e f r e e ) 网络模型( 蜊) 。复杂网络诸多特征中最重要的是小世 界( s m a l l - w o r l d ) 效应和无标度( s c a l e - f r e e ) 特性，这两个方面构建了复杂网络研究的基石。 本文主要包括以下几个方面。第二章介绍了经典的复杂网络模型及其动力学性质。 第三章对于前一章中的经典的复杂网络模型的特性进行分析，利用平均场理论得出在保 证网络持续增长与优先连接条件下无标度模型的，值的大小成因。发现了此类无标度网 络具有的标度共同点：新增节点具有固定度时，系统韵a k 。b t 决定了y 的大小，即 ，= b a + l ，从而简化分析过程有利于构造模型。通过一个简单的无标度模型来证实我 们的结论。第四章研究网络中的同步能力与网络结构的关系。从最简单的串联耦合网络 加一条边，利用的遍历的方式，对每一种网络结构计算其矩阵的特征值，观察系统同步能 力变化情况找出同步能力最强的结构。进而得到对于同步能力优化的网络结构。第五章 研究了产品人际间传播特征，并对于传播产生的后果进行了预测。对于均匀随机状态下 证明新产品在一定范围内使用者与非使用者趋于平铸状态。利用最新的复杂网络研究成 果构造模型将传播范围最大限度的扩大。有利于企业的产品广告投入效果与成本进行计 算，优化投入产出理论分析表明，对于产品人际传播进行策略行为，可以带来有效后果。 同时也表明网络的拓扑结构对于产品传播有着重要的影响。由此说明，对于传统的产品 营销方式改革的必要性。 关键词：复杂网络；无标度；小世界；混沌；同步；耦合系统 江苏大学硕士学位论文 a b s t r a c t i n l 9 9 8 ，a na r t i c l ea b o u ts m a l l w o r l dn e t w o r km o d e l sw a sp u b l i s h e di nn a t u r e f r o mt h e no nm a n y r e s e a r c h e r sh a v eb e e nw o r k i n go nc o m p l e xn e t w o r k s c o m p l e xn e t w o r kb e c a m eaf o c u si nm a n yf i e l d s ， s u c ha sg r a p ht h e o r y 、s t a t i s t i cp h y s i c s 、c o m p u t e rn e t w o r k s 、b i o n o m i c s 、s o c i o l o g ya n de c o n o m i c se t c i n1 9 9 9 ，b a r a b l i s ia n da l b e r tp r o f o u n ds c a l e - f r e en e t w o r km o d e li ns c i e n c e a m o n ga l lt h ec h a r a c t e r i s t i c s s m a l l w o r l da n ds c a l e f r e ea r et h em o s t i m p o r t a n t t h e ya r et h ef o u n d a t i o n so f c o m p l e xn e t w o r k s t h i sp a p e ri so r g a n i z e da sf o l l o w s ：ag e n e r a li n t r o d u c t i o na b o u tc l a s s i c a lc o p l e xn e t w o r km o d e l s a n dt h ed y n a m i c a lb e h a v i o ri sp r e s e n t e di nc h a p t e r2 i nc h a p t e r3 ，t h ef a c t o ro f d e t e r m i n i u gt h ev a l u eo f ，i sf o u n db ya n a l y z i n ga n dd e d u c t i o nt h o s ec l a s s i c a lc o m p l e xn e t w o r k s f o u n dac o m m o ns c a l e c h a r a c t e rf o rs o m ek i n d so f s c a l e f r e en e t w o r k sw h i c hn e e dl i n e a rg r o w t ha n dp r e f e r e n t i a la t t a c h m e n t i n t h ec a s eo fa d d i n gn e wv e r t i c e sw i t haf i x e dd e g r e e ，t h ev a l u e so fya r ed e t e r m i n e db yt h es y s t e m s 口t b t ，。b l a + i a n do t h e r m o d e l sc a nb ec o n s t r u c t e de a s i l y , s i m p l i f y t h ep r o c e s so f a n a l y s i s b y i n t r o d u c i n gas i m p l es c a l e - f r e em o d e l ，p r o v e do u rc o n c l u s i o n sr i g h t i nc h a p t e r4 ，r e l s t i o n sb e t w e e n s y n c h r o n i z a t i o na n dt h et o p o l o g yo fc o u p l e dn e t w o r k si si n v e s t i g a t e d a tf i r s tan e we d g ei sa d d e dt oa s i g n a ln e t w o r ki ns e r i e s ，a n dc h a n g e st h es y n c h r o n i z i n ga b i l i t yo fc o u p l e dn e t w o r k sa c c o r d i n g l y t h e s t r u c t u r ew i t ht h eb e s ts y n c h r o n i z i n ga b i l i t yi sf o u n d t h u st h eo p t i m a ls t r u c t u r eo fc o u p l e dn e t w o r ki s o b t a i n e d i nc h a p t e r5 , t h ec h a r a c t e r i s t i co f am o d e lo f p r o d u c t ss p r e a d i n ga m o n gp e o p l ei ss t u d i e da n dt h e r e s u l ti sp r e d i c t e d ，t h ed e r i v a t i o no fe p i d e m i cs p r e a d i n gi nh o m o g e n e o u sn e t w o r k sh a v eab a l a n c e b e t w e e nt h ep e o p l ew h oh a v ep u r c h a s e da n dt h ep e o p l ew h oh a v e n tp u r c h a s e di ti nt h ee n d ，b yu s i n g t h er e c e n t a d v a n c e so f c o m p l e x n e t w o r k s , a n e w m o d e l i s b u i l t t oe n l a r g e t h ed e g r e eo f s p r e a d i n g a s b r o a d a sp o s s i b l e i t su s e f u lt oc a l c u l a t et h ec o s to fa d v e r t i s e m e n ta n do p t i m i z et h ei n o u t t h e r ei sag o o d e f f e c tt oh a v eat a c t i cf o rp r o d u c t ss p r e a d i n ga m o n gp e o p l e a n da l s o ，t h et o p o l o g i cs t r u c t u r eo f n e t w o r k s h a sa ni m p o r t a n ti m p a c tt ot h es p r e a d i n go fp r o d u c t s i t sn e c e s s a r yt or e f o r mt h et r a d i t i o n a lm e a n so f s a l e s k e y w o r d s ：c o m p l e xn e t w o r k s ；s c a l e - f r e e ；s m a l l - w o r l d ；c h a o s ；s y n c h r o n i z a t i o n ；c o u p l e ds y s t e m i i 独创性声明 本人郑重声明：所里交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已注明引用的内容以外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年 月日 江苏大学硕士学位论文 第一章引言 1 1 本课题的研究背景和现状 自然界中存在的大量复杂系统都可以通过各种各样的网络加以描述。一个典型的网 络是由许多节点与连接节点的边组成的。其中节点用来代表真实系统中不同的个体，而 边则代表个体之间的关系，有边相连的两个节点被看作是相邻的。例如，神经系统可以 看作由大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工 作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络；类似的还 有电力网络、社会关系网络、交通网络等等。 对网络最早进行研究的是数学家，基本理论是图论。经典的图论是倾向于用某种规 则的拓朴结构模拟真实网络，到了上世纪五十年代末期，e r o d 6 s 和r d n y i l l 】建立了随机网 络模型，将概率方式引入图论的研究，认为现实的网络连接是等概率的，即两点之间的 连接是随机连接。近半个世纪中随机图一直是科学家研究真实网络最有力的武器。直到 最近，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量的真实网络既不 是规则网络也不是随机网络丽是介于两者之间的网络。这样一些网络被称为复杂网络， 其中最重要的统计特性是小世界( s m a l l - w o r l d ) 效应和无标度( s c a l e f r e e ) 特性。 1 9 9 8 年w a t t s 和s t r o g a t z f 2 j 提出基于人类社会网络的小世界( s m a l i w o r l d ) 模型( w s ) ， 它通过调节一个参数可以从规则网络向随机网络过渡( 图1 1 ) ，主要利用断链重连改变原 有网络的结构，加入随机性的连接得到一个随机网络。发现一种被忽视视的网络结构。 1 9 9 9 年b a r a b f i s i 和a l b e r t b4 j 提出了无标度( s c a l e f r e e ) g 目络模型( 占a ) 。它的形成必须具备 两个条件：增长和择优连接，所生成的复杂网络度概率分布是幂律形式e ( k ) = k - r ( 图1 2 ) 并具体利用平均场方法推导出，= 3 。这两项工作揭开了复杂网络新的研究序幕。 小世界模型的研究中，n e w m a n 与w a t t s 通过对于规则网络直接添加新的捷径也能得 到小世界网络k l e i n b e r g 嘲提出基于两维方格的w s 模型的一般化形式；o z i k ，h u n ta n d o t t v j 引入一个简单的小世界成长演化模型，它上面所有的连接由点附近的位置所决定； a n d r a d e 与h e r r m a n n 【剐，中科大复杂网络研究小组【9 j 研究了阿波罗网，证实它具有许多 小世界性质。 1 9 9 9 年，b a r a b f i s i 和a l b c n l 3 t 4 ( b a ) 发现许多真实网络具有幂律型度分布，即 江苏大学硕士学位论文 尸( 七) k - ，其中1 0 与两个常数 d 0 a 对于所有d d ，使得【矿( s ( f ) ) + d r 】d + d 【犷( s ( f ) ) + d r 】一r l n ，这里 江苏大学硕士学位论文 le r 一是单位矩阵。如果c 五：s j ，即c 导i 那么定义( 2 1 ) 下的同步是指数稳定的，其 i ，l 中孑是由孤立结点的动力学和内部结构矩阵所决定的常数( 由网络的l y a p u n o v 指数所刻 划) 。如的值越小，i 如i 的值越大，这表明网络( 2 1 ) 可以在一个很小的耦合系数下实现同步。 因此，在特定的耦合方式下，耦合矩阵一的第二大特征值表征了网络( 2 1 ) 的同步能力。w u 和c h u a 口1 1 的工作表明：通常情况下，只要耦合强度c 足够大，都会使耦合振子系统进入同 步状态。 引理2 2 中的判据如果不满足( 2 1 ) 的形式可能就不成立了，同时引理2 2 也说明了对于网 络的结构它的耦合矩阵的第二特征值对于同步能力的影响是很大的。汪小帆和陈关荣在 【2 2 】中进一步研究了动力学网络的同步条件。不失一般性，令r = d i a g ( 1 , o ，o ，0 ) 那么( 2 1 ) 式写成： _ 南= ( 而) + c 嘞工门 - l j ，2 = 以( x 。)i = l 2 ，n( 2 ，2 ) 圣。= ( x 。) 引理2 3 如果如- t c 那么( 2 2 ) 式定义的同步态是渐近稳定的，其中t 0 是使单 个节点的自反馈系统 f 矗= 一( x ) 一t x ， 量2 = 厶( x )( 2 3 ) l 童。= ( x ) 的原点指数稳定所需的反馈强度的最小值，即c i 暑i 中的l 孑i 或( 4 8 ) 式中的一。 b a r a h o n a 与p e c o r a l 2 3 1 得到结果，扎如是独立于其它因素之外测量网络结构同步能力的 条件，其中是耦合造成矩阵的最小特征值，即是绝对值最大的特征值。 2 2 经典复杂网络模型 现实世界中许多系统都可以用复杂网络来描述f 2 4 ，2 5 0 6 ，2 7 1 ，网络节点为系统元素，边为元 素间的互相作用和相互联系( 即关系) ，如社会网络中的合作网、信息网络中的万维网、 技术网络的i n t e r a c t 网和运输网、生物网络的代谢网络等等。由于现实网络规模一般很大， 江苏大学硕士学位论文 节点间的相互作用多而复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描 述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系 统因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网；从2 0 世纪5 0 年代末到9 0 年代末，无明确设计原则的大规模网络主要用简单丽易于被多数人接 受的随机网络来描述1 1 1 ，随机图的思想主宰复杂网络研究达四十年之久；直到最近几年， 科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不 同的统计特征的网络，其中最有影响的是小世界网络肛j 年口无尺度网络1 3 】。 无尺度网络指节点度服从幂律分布的网络。b a 模型是第一个无尺度网络演化模型， 它捕捉到了无尺度网络形成的两个必不可少的机制增长和择优连接是( 3 4 1 ，说明了大 规模复杂网络自组织成为无尺度状态的原因。b a 开创性论文的发表，掀起了无尺度网络 和b a 模型研究的高潮，在新世纪初的最近几年里，科学家们就提出了许多产生无尺度 网络的模型1 2 8 , 2 9 , 3 0 ，并对b a 模型的主要性质进行了深入研究【3 1 翔1 。 b a 模型同e r 随机网络和w s 模型一道，对网络科学的发展起着重要的作用。众所 周知，e r 随机网络有一个等价模型，它们有着完全相同的性质，对其中一个模型的研究 结论都可以推广到另一模型，因此，人们往往根据方便，选择使用e r 随机网络或其等 价模型。章忠志【3 3 1 提出了b a 网络的一个完全等价的演化模型，模型的演化机制比b a 的简单，在系统增长的演化过程中，新节点总是与网络中随机选择的边所关联的节点进 行连接。利用平均场方法，解析计算了节点的增长动态性、节点度分布和平均集聚系数， 计算结果与b a 网络完全相同。 2 2 ie r 模型及其等价模型 随机网络理论由匈牙利数学家e r d 6 s 和r 6 n y i 提出【5 ，他们提出的模型称为经典的 e r 模型。e r 模型的定义为：由个顶点构成的图中，随机连接g 条边形成一随机网络， 记为g 。，由这样的n 个节点g 条边组成的网络共有c 膏( 1 ) 2 种，构成一个概率空间， 每一个网络出现的概率是相等的。 另一种与e r 模型等价的随机网络模型是二项式模型，其定义如下：给定的节点数目 固定不变，假定任意节点对之间有条边连接的概率为p ，形成的网络记为g 。这样， 整个网络中边的数目是一个随机变量，其期望值为i ( | 一i ) 2 。设g 0 是由节点为v l ， v 2 ，v n 且有g 条边连接组成的一个随机网络，则按上述构造过程，得到g 0 的概率 江苏大学硕士学位论文 为p ( g o ) ：p 。( i 一，) w 一m 。如果令g 。夕，则两个模型g 。g u ，互相等价，由任一 模型得出的结果可以非常容易的推广到另一模型。 2 2 2b a 模型 b a 模型是第一个增长的网络模型【4 1 ，其描述如下： ( 1 ) 增长：在初始时刻，假定系统有m o 个孤立节点，在以后的每个时间间隔中，新增 一个度为m 的点( m m o ) ，并将这m 条边连接到网络中已经存在的m 个不同的节点上。 ( 2 ) 择优连接；当在网络中选择节点与新增节点连接时，假定被选择的节点v 与新节点 连接的概率兀( 乜) 和节点v 的度成正比一日i - i ( ”2 轰。 设节点i 的度k i 满足动态方程： o 良k _ a - = 彳兀c 置，= 一蠢 c ：4 ， 分母求和是对系统中除新进入系统的节点外的所有节点进行的，则 ，k ，= 2 r o t - m 。每个时间步度的变化为a k = ，l ，因此4 = 聊，得到a 七。o t = k 。2 t ，此 方程满足初始条件k 。( r 。) = m 解得 毒( f ) = m ( t t , ) ”( 2 5 ) 由( 2 5 ) 一个点的度t ( f ) 小于k 的概率可以写成： p ( k ) _ p ( f 等) ( 2 6 ) 假定以等时间间隔向系统添加点，那么r 。的概率密度是： ：( ，) = 1 ( m o + t )( 2 7 ) 代入( 2 4 ) 得： p ( ，。 掰2 k 2 ) = 1 - p ( t ，s m 2 k 2 ) = 1 - m 2 t k 2 0 + m 。) 由此可以得到关于k 的概率分布： p ( k ) = a p ( k , i t ) r 。( 2 1 0 ) ( 2 1 0 ) 式表示所有节点的度按同一方式演化，即都服从幂律，与b a 网络中的节点度 的演化完全致。由( 2 9 ) 、( 2 1 0 ) 两式可得，随机选择的两节点i , u 歹是直接邻居的概率 p r o b ( i j ) = m ( t 。，) 4 5 。 假设时问f 服从均匀分布，根据( 2 9 ) 、( 2 1 0 ) 两式可计算节点的度分布函数p ( ) 为 眦) = 掣= 磊2 m 2 t 可1 当f 斗时，有：p ( 七) 2 m 2 k f 2 1 1 ) 可见，与b a 网络一样，该模型最终演化成标度不变状态，其节点的度分布也与b a 网络完全相同，都服从度指数y 23 的幂律分布( 图2 1 ) 。 图2 i ：网络的节点度分布。 网络节点数为1 0 0 0 0 ，m = 3 。实线表示( 4 ) 式计算的理论结果，其斜率为3 。 十字符表示b a 模型的模拟结果，实心点为等价模型的模拟结果。 ( 2 ) 集聚系数 由于本模型中，只在新节点与老节点之间才建立连接，因此，仅当新节点连接到节 点i 且与f 的栉( 聆2 0 ，肌一1 ) 个邻居进行连接时，k i 和蜀的值才改变，从而改变c f 的 值。c f 满足下面的动态方程： 鲁= 一n - 一o p i n “i n ( 2 a 2 ) 其中，巴表示新节点连接到节点，和它的胛个邻居时集聚系数的变化值，则表 示这一变化的概率。巳满足下式 江苏大学硬士学位论文 玲粼一志一磊+ 志 ， 蜘由两部分的乘积构成，第一鄙分是甭一条款边恁搔刽币点1 册撒率，逐一儆翠由 ( 2 9 ) 式给出；第二部分部分指的是其余( 所一1 ) 条新边连接到节点i 的订个邻居的概率， 它等价于每次成功概率为n e i g h b o r ( i ) ( 2 m t ) 的( m 1 ) 重贝努利里试验中，成功玎次的概 率。n e i g h b o r ( i ) 表示节点i 的邻居数目，其值可通过下面的积分获得。 ”e 动) = f k ，p r o b ( i x ) d t r2 争l n f 叫) 综上可得的关系式为：驴弘k ic ( k 4 l r n t 九l 一半广( 2 1 5 ) 由( 2 1 5 ) 式知疗 1 时，p m 很小，可以忽略低阶项，得： 百d c , = 施巳w c j o w c n ：一而m c j + 面m ( m 丽- 1 ) 得吣赫赫卜卜4r 再一瓢渊s f 亿 ( 2 1 7 ) 式中c o n s t 为积分常数，可通过初始条件c j ( ) 的值决定。c j ( f ，) 指节点f 刚进入 系统时的集聚系数，其表达式为 驯= f 孝f 撕6 ( i j ) p r o 啪删( 觥2 拈面半 将2 代入( 2 1 7 ) 式，并与( 2 1 8 ) 式比较， ! 釉j c o n s t 的值，忽略修正项，再代入( 2 1 7 ) 式，得到c 随时间的演化公式 晰雨南矗( 妒+ ：鲁咿 利用第一积分中值定理，对( 2 1 9 ) 式进行积分，就可得到整个网络的平均集聚系数c 。 c ：丛 = 筹离州炯一蒜叫店枷，毕k ， ( 2 2 0 ) 式中的掌【1 ，f ，当f 很大时，( 2 2 0 ) 式中的手与肌以比较起来可以忽略不计。 江苏大学硕士学位论文 因此，网络的平均集聚系数c 可以写成 一c = 筹 n 掣卜捌半 眨：。， 可见，该演化模型的平均集聚系数与b a 网络完全一样，它随着网络规模的增大而 迅速下降( 图2 2 ) 。 图2 2 ：网络的平均集聚系数随着网络大小的变化。 图中所有网络中的m = 3 。实线表示是由( 2 2 1 ) 式给出的理论结果，十字符表示b a 模 型的模拟结果，实心点为等价模型的模拟结果。 综上所述，该模型与b a 网络的度分布和集聚系数两个参数完全相同。遗憾的是， 我们没能给出演化模型的平均路径长度( a p l ) 的解析表达式，但是数值模拟表明( 因 篇幅限制，模拟结果这里未给出) ，该模型与b a 网络的a p l 也相同。因此，新模型与 b a 网络有着相同的拓扑结构和性质，它与b a 网络完全等价，这一等价性通过直觉和模 型的演化机制都很容易看出：由( 2 1 0 ) 式知，新模型与b a 网络的节点增长动态性完全相 同，这就充分说明了两个网络的等价性。 2 2 4 章忠志、荣莉莉，周涛合作演化模型 合作网络是现实世界中广泛存在的一类网络。章忠志、荣莉莉，周涛p 1 提出了针对 一类特殊的无标度合作网络的演化模型，并利用平均场方法解析计算了节点的增长动态 性，证明了该网络是节点度分布符合幂律分布的无标度网络，其幂指数为 ，。( 2 m 一1 ) ( m 1 ) ，其中聊是不小于2 的正整数，通过调节参数聊可以得到属于区间( 2 ，3 ) 的不同的，值。 合作网络是现实世界普遍存在且目前研究较多的一种网络，包括电影演员合作网、 江苏大学硕士学位论文 科研合作网等等。这类网络具有与其他类型网络截然不同的独特之处，即它是由许多完 全图组合而成的。例如在电影演员合作网中，参加演出同一部电影的演员构成一个完全 图；在桥牌选手合作网络中，同场比赛的四名队员构成一个完全图；科学家合作网中， 同一篇文章署名的作者构成个完全图。根据合作网络的特殊性，建立演化模型是很有 意义的工作。 章忠志、荣莉莉，周涛考虑了一类特殊的合作网络，即合作人数固定的合作网络， 建立了相应的演化模型。并利用平均场方法解析计算了节点的增长动态性，证明了该网 络是节点度分布符合幂律分布的无标度网络，其幂指数为y = ( 2 m 一1 ) ( m 一1 ) ，其中m 是 不小于2 的正整数，通过调节参数聊可以得到属于区间( 2 ，3 ) 的不同的y 值。数值模拟结 果与解析计算结果相吻合。 现实世界中有一类最简单的合作网络，在这类网络中，完成一次合作的人数是固定 的，如桥牌网中每次合作总是由4 个人完成。下面我们将给出一个针对该类特殊合作网 络的个演化模型。 2 t = 1 4j4： 爪肃6 l ? l 、， i oj i 。| f 、 ， f 。r 、j ， ， 3 t 毒一卜3i 髟：一一 _ j 3 j f 、j f ，+ 、卜7、。 l l、i 0蕾 2 2 t = 2t = 3 图2 3m = 3 时的网络增长示意图。 在初始时刻，网络为相互连接的三个节点组成的三角形。然后在每个时间步，增加一个新节 点，新顶点与随机选择的一个三角形的三个顶点各连一条边。 在本模型中，网络初始状态为由m ( 脚2 ) 个节点和m ( m 一1 ) 2 条边组成的完全图 ( m - 完全图) ，尔后在每一个时间步内，网络新增一个节点，该节点从网络中随机选择 一个辨完全图，并与此m 个节点分别连一条边，表示一次+ 1 ) 个人的合作。易知每一 个时问步网络增加1 个节点，m 条边，m 个m 完全图和1 个枷+ 1 ) 完全图( 如图2 3 所示) 。本模型虽然只是一个租糙的模型，却抓住了合作网络最主要的特征，即网络由完 全图构成。例如桥牌网络即可看作本模型在m = 3 时的情形。 现在来求节点的增长动态性与度分布，模型中任一节点v 的度乜随时间的演化关系 娜 一 ， o 、 卜 江苏大学硕士学位论文 可通过平均场近似的方法求得。由于新节点进入系统时，总是与一个随机选择的m 一完 全图的各顶点建立连接，而且，度越大的节点会在越多的m 一完全图中出现。节点度每 增加1 ，由其作为组成部分的m 完全图的数目就增加肼，因此，在每一个时间步，新节 点与其连接的概率也越大。在每一时间步，新节点进入系统并连接到节点v 时，氐将增 加1 。假设氐为连续实变量，它满足下面的动态方程： 堡：( m - 1 ) k ，- m ( m - 2 ) f 2 2 2 ) o tm t4 - 1 ( 2 ，2 2 ) 式中的分母表示在新节点引入之前，系统所具有的m 一完全图的数目，分子表 示组成成分包含节点v 的m 一完全图的数目。 ( 2 2 2 ) 式的初始条件是：节点v 在时刻进入系统，此时其度为砖纯) = 嬲。于是满足 这一初始条件的方程( 2 2 2 ) 的解为： 啪) = 等旱+ 盎( 筹) 4 ( 2 2 孔 其中口：兰兰 ( 2 2 3 ) 式表示所有节点的度按同一方式演化，即都服从幂律。利用( 2 2 3 ) 式，可写出连 通度t ，( r ) 小于七的概率表达式； 删北廿即忑事m 两t + l 一 仁2 4 ) 由于每一个时间步都有且仅有一个节点加入到原网络中，因此0 服从均匀分布，其概 率密度为： 聃v ) 。焘 ( 2 2 5 ) 将( 2 2 5 ) 式代入( 2 2 4 ) 式，得： 地 焉甄m t + l 爿1 _ l - 藕再话m t + 巧l 一1 m，竹一l 一翌、 m + t ( 2 2 6 ) ? | 砉 江苏大学硕士学位论文 聊，= 掣= 基2 m - i 川胁一焉亍) 4 ( 2 2 7 ) 盎m ) 等( j j 一警m1 ) 寸“= ( 砉芦 巫m 竽1 厂 ( 2 2 8 ) 一i 一fl f 2 2 8 y ：土+ 】：2 m - 1 。卢 m 一1 r 2 2 9 ) 卢3 1 2 ；当m - - - - o o ，斗l ，因此，卢( i 2 ，1 ) 。由( 2 2 9 ) 式失1 1 ，卢和y 满足下面的关 图2 4 模型的度分布。 图( a ) 和( b ) 分别为m = 2 ，3 两种情况，网络节点数均为1 0 0 0 0 。实线表示理论计算 - 1 6 江苏大学硕士学位论文 的结果，其斜率分别为- 3 ( a ) 和2 5 ( b ) 。 图2 4 中的数值结果出现胖尾现象，即许多度数很大的节点出现的概率相同。发生这 一情况的主要原因是，数值模拟中网络节点的数目有限，而预测值则是t 斗时的统计 结果。网络规模越大，模拟结果与理论计算值也将越吻合。 在本模型中，网络初始状态为由m ( m 2 ) 个节点和m ( m 一1 ) 2 条边组成的完全图( m 一 完全图) ，尔后在每一个时间步内，网络新增一个节点，该节点从网络中随机选择一个m 一 完全图，并与此m 个节点分别连一条边，表示一次m + 1 个人的合作。易知每一个时间步网 络增加1 个节点，m 条边，m 个m 一完全图和1 个( 肌+ 1 ) 一完全图。它满足下面的动态方 程： a k ：! 竺二1 2 生二竺! 竺：型 o tm t + 1 ( 2 3 1 ) 同样满足初值条件七，( f 。) = m ，得到 y 2 m - t 旦+ 1 ( 2 3 2 ) m 一1m l 、 2 2 5 陈庆华、史定华模型 1 ) 模型a 开始时有系统有个孤立节点【3 6 】，每个时间间隔中进行下面操作： ( 1 ) 在已经存在的节点中添加，条新连接：随机选择一个节点作为新连接的起始点， 点f 被选择作为新连接的另一个节点满足偏好概率兀( t ，口) = ( 砖+ 口) ，( k j + 口) ，重复 操作，次，所有的节点具有一个初始的吸引度口0 参数a 的引入保证了新的节点能够得 到新连接 ( 2 ) 新增一个度为m 的点：新增的节点连接到现有系统的节点i 满足 兀( t ，口) = ( t + 口) ，( k j + 口) ( 3 ) 重新连接系统已经存在的n 条连接：随机选择一个点i 与连接i 的边，然后断开 点i 宅f i 。与，重连这条边得到0 其中i 以概率兀( 七f ，口) = ( t + 口) ，( k j + 口) 选择得到动 力学方程： 鲁邓训知”，东南州州专东南 江苏大学硕士学位论文 化简得， o 西k _ _ l = 与+ 面l 了+ m 磊+ nt k f + o t ( 2 3 3 ) 同时满足初值条件k 。( f ) = m ，这里经过计算得出： y ：3 l + 3 m + n + o t ；2 1 + 2 m + o t + 1 。f + _ m + n，+ m + n 得出，值大于2 的结果 2 ) 模型b 开始时有系统有m o 个孤立节点，每个时间i 司隔中进行f 面操作： ( 1 ) 、( 2 ) 步骤同b a 模型的两个步骤 ( 3 ) c 条旧连接被删除：点f 以反偏好概率兀( 七) 2 丙高j ( 1 一丌( t ) ) 被选择- 得到演 化方程： 鲁= 珊兀( 龟m 【n ) x 1 + 丢兀( 1 ) 兀( t 肛c 兀( t ) l + 善丌( 1 ) 丌( 恕) 】 化简得：o a k _ l = 一芋+ 面i m 而+ 2 n 七， ( 2 3 4 ) 同时满足初值条件七( f ，) = m ，这里 v= ，”+ 2 n 得出，值在2 与3 之间。 2 3 复杂网络的动力学性质 2 3 1 网络同步 m + 行一c 、 ，”+ 2 n + l 如果在网络的每个节点上加上一个动力学系统，这个动力学系统既可以是极限环也 可以是混沌的吸引子；而让有边相连的两个节点的动力学系统之间存在相互的耦合作用， 就形成了一个动力学网络。严格地说，设网络有个节点，第i 个节点在n 时刻的m 维状 态变量是工( 玎) ，单个节点在不考虑耦合作用的时候满足的状态方程是 x 0 + 1 ) = f ( x 。( 聍) ) 。h ：r 4 寸r ”是每个节点状态变量的函数，用于对其它节点进行耦 合。这样在存在耦合作用的情况下，第i 个节点所满足的状态方程是 江苏大学硕士学位论文 x 。( n + 1 ) = f ( x 1 ( ) ) + 莎，g f h ( x 坳” ( 2 3 5 ) 对于连续系统 膏= y ( x ) + 口，g , j n ( x 7 ) ( 2 3 6 ) 其中盯是耦合强度，g 。表示耦合矩阵g 的矩阵元，定义如下： i kf _ f ， 嘭= 1 _ ，a( 2 3 7 ) 【0 其它 其中七是节点i 的度a ，是节点f 相邻的节点的集合。耦合矩阵g 包含了网络结构的全 部信息。在耦合的作用，经过段时间的演化，使得_ ( f ) = x ：o ) = = x n ( f ) = s o ) 0 o o ) 网络就进入了同步状态。但是，并不是所有的网络在任意耦合强度或藕合方式下都能实 现同步。 2 3 2 复杂网络同步的稳定性分析 p e c o r a 和c a r r o l l 研究了线性耦合网络同步的稳定性问题，给出了主稳定函数判据【3 7 】。 首先假设：( 1 ) 所有的耦合振子都是完全相同的。( 2 ) 从每个振子提取的用于耦合其它 振子的函数也是完全相同的，( 3 ) 同步流形是不变流形，( 4 ) 节点的耦合方式使在同步流形 附近系统可以线性化。( 1 ) 和( 3 ) 是为了保证相空间同步超平面的存在，假设( 2 ) 是为了使 动力学系统和网络结构的稳定性图象更加清晰具体，假设( 4 ) 是为了更好地应用线性近似 这一研究耦合系统最常用的方法。在此基础上，p e c o r a 和c a r r o l l 逐步完成了当网络上的耦 合振子系统的同步混沌态存在短波分岔对的同步稳定性分析，提出用主稳定性函数方法 确定动力学网络同步的稳定性。 首先对动力学网络的同步流形进行线性稳定性分析，当存在藕合作用时第f 个节点所 满足的状态方程是( 2 3 6 ) 在同步状态s 附近对其线性化，得到： j = d f ( s ) z + 口，g # d h ( s ) z ( 2 - 3 8 ) 其中z 是节点i 在同步流形j 上的变分d 联) 和d 五* ) 分别是函数，和h 的t 7 1 i n 阶 j a c o b i a n 矩阵。利用m n 阶矩阵z = ( z 1 ，z 2 ，z “) 重写( 2 3 8 ) ： 2 = d f ( s ) z + a d h ( s ) z g 。f 2 3 9 ) 根据约当规范型理论，上式的稳定性是由g 的特征值，决定的，设其对应特征值为口， 并且令u = = - p r ，将8 右乘( 2 3 9 ) 式得到： 江苏大学硕士学位论文 = o f ( s ) + o g d h ( s ) - “( 2 4 0 ) 这样原来讨论的m x n 维空问的稳定性问题简单化到埘m 维空间，并且通常情况下 m n 。离散系统可给出( 2 4 0 ) 式类似的结论。利用( 2 4 0 ) 式计算单个系统的l y a p u n o v 指 数，设这些指数分别为 = k 五：以。由于：，g f - - 0 ，= o 总是g 的一个特 征值，相应的特征向量是( 11 1 ) 7 它对应同步流形模式。其它一1 个特征向量所张 成的子空间横截于同步流形，如果所有这些横截l y a p u n o v 指数都小于o ，系统稳定。设 0 7 = 口+ 妒，作为耦合矩阵g 如果是非对称耦合则它的特征值可能有复数。代x ( 2 4 0 ) 中： 吱= d f ( s ) + + i p ) o h ( s ) 越( 2 4 t ) 计算最大五 印甜雄d v 指数五h 随着口与的变化关系，这就是p e c o r a , 和c a r r o l l 定义的 主稳定性函数( m a s t e rs t a b i l i t y f u n c t i o n ) ，图2 5 给出了耦合振子系统的同步混沌态存在短波 分岔时它们的关系图，五。 奠 ( 2 4 2 ) 【d y h 眦 口2 血 鱼s ( 2 4 3 ) 图2 5r 6 s s l e r 振子通过变量x 进行耦合的主稳定函数 江苏大学硕士学位论文 图2 6 对称耦合时r 6 s s l e r 振子的主稳定性函数 汪小帆和陈关荣f 挖1 研究了耦合振子是连续系统的复杂网络的同步稳定性问题，并对 b a 网络的同步现象作了研究，发现无标度网络的同步状态在随机去掉节点时表现出很强 的鲁棒性。 前面提出的分析网络同步稳定性的方法都需要计算耦台矩阵的特征值，复杂网络节 点数目巨大，计算其耦合矩阵的特征值只能采用近似方法，c h e r t t 4 0 1 等人将主稳定性函数 方法与g e r s h 9 6 r i n 圆盘理论结合，为网络结构对混沌耦合振子系统稳定性的影响给出了 更精确的分析方法。 引理2 4g e r s h 9 6 r i n 圆盘定理：一个胛h 阶矩阵a = 吼】的所有特征值处于n 个圆盘 的并集中( 称为g e r s h g o r i n 圆盘) ，这些圆盘定义是： z c ：i z - a 。l 萎口。 ，z = ，z ，行 ( 2 4 4 ) 若存在可逆阵p 使得p g ，p 与g 有相同的特征谱，那么：d 1 = g 一e n - l ，7 。通 过变换令e 的不同元素为i ，可以得到个不同的约化矩阵，用d 。( 女= 1 , 2 ，) 表示。 将上述方法用于耦合矩阵g 中，令三= o ，e = ( 11 1 ) 7 ，得到d = 钟】，其中 = q 一。根据g e r s h g i j r i n 圆盘定理动力学网络同步稳定性条件表达如下： g e r s h g i j r i n 圆盘d 的中心位于稳定区域q ，即( 瓯一g “，0 )