（应用数学专业论文）一类新型网络上的混沌同步研究.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 网络是能够较好的反映客观世界的一种数学模型，现在 人们逐渐认识到许多现实中的复杂网络既不是完全规则的， 也不是完全随机的。人们已经利用计算机获取大量得资料，通 过数据分析和高性能计算机的应用来研究复杂网络的拓扑性 质，是一个引起人们兴趣的新的研究领域。 本文在第一章引言中首先介绍了人们对混沌的认识及其 混沌控制和同步的有关概念，接着介绍了混沌同步的发展和判 别方法。然后介绍了小世界网络的前景、发展和在研究中经常 用到的几个基本拓扑度量一一平均步数、串接数和分布度。对 完全规则网络、完全随机网络和几个具体典型的常见的的大 型网络象万维网、因特网等的拓扑结构量做比较，表明了小世 界网络的优越性。在第二章中我们根据大型真实网络的性质提 出了一种新的复杂网络模型，通过对这种模型的拓扑度量的分 析，我们看出这种网络更加接近上述几个大型真实网络，其本 质是一种小世界网络。接着我们解析给出了这种网络上的动力 系统实现混沌同步的条件，并和人们常研究的建立在规则网络 上的c m l 做比较，发现前者比后者更容易实现混沌同步。最 后，我们用数值方法验证了我们得出的结论。 关键词：小世界网络，混沌同步，格点耦合映射( c m l ) 2 0 0 4 年上海大学硕士学位论文 i i a b s t r a c t n e t w o r ki st h o u g h ta 8as o r to fm a t h e m a t i c a lm o d e la n di t c a nr e f l e c to u rw o r l dw e l l m a n yr e a ln e t w o r k sa r eg r a d u a l l yt h o u g h t a sn e i t h e re n t i r e l yr e g u l a rn o re n t i r e l yr a n d o mm o d e l s o b t a i n i n g m u c hd a t u mb yc o m p u t e ra n da p p l y i n gp o w e r f u lc o m p u t e r ，w ec a n r e s e a r c h l o t so ft o p o l o g i c a lc h a r a c t e r so ft h ec o m p l e xn e t w o r k s i nt h e p a p e r ，t h ef i r s tp a r to f t h ei n t r o d u c ef i r s t l ys h o w ss o n ec o g n i z a n c ea s t oc h a o sa n ds o m ec o n c e p t s ，t h e ni n t r o d u c e sc o m m e nr e s e a r c hm e a n s s u c ha sc h a o t i cc o n t r 0 1a n dc h a o t i cs v n c h r o n i z a t i o n ，a t1 a s tt e l la b o u t d e v e l o p p m e n ta n dc r i t i z a t i o no fc h a o s t h es e c o n dp a r ti n t r o d u c e s t h ef u t u r ea n dd e v e l o p p m e n to fs m a l l w o r l dn e t w o r k ，t h e np a y sm o r e a t t e n t i o nt oi n t r o d u c i n gs e v e r a ln e c e s s a r yb a s i ct o p o l o g i cc o n c e p t s a b o u tn e t w o r k ss u c ha st h ea v e r a g ep a t h ，t h ec l u s t e r i n ga n dt h ed e g r e ed i s t r i b u t i o n b yc o m p a r i n gt h et o p o l o g i cc o n c e p t si ne n t i r e l y r e g u l a rn e t w o r k sa n de n t i r e l yr a n d o m n e t w o r k st ot h o s ei nt h et y p i c a l l a r g e s c a r e en e t w o r k s w es h o w t h es u p e r i o r i t yo fs m a l l w o r l dn e t w o r k b a s e do nt h ec h a r a c t e ro fs o m eb i gr e a ln e t w o r k ，t h ea u t h o rp r o p o s e s an e w c o m p l e x n e t w o r k o u ra n a l y z i n gt h es e v e r a lt o p o l o g i cc o n c e p t s c a ns h o wt h a tt h es o r to fn e wn e t w o r k w h i c hi sa t y p eo fs m a l l w o r l d n e t w o r ki ne s s e n c ei sc l o s e rt ot h ea b o v er e a ln e t w o r k s ，t h e na n a l y t i c a lp r o p e r t ya n dn u m e r i c a le m u l a t i o na b o u ti t ss v n c h r o n a z a t i o na r e g i v e n a tl a , s tw e t e s t i 知o u rr e s u l ta b o u tt h es t a rn e w o r k b yn m n e r i c a l n e t h o d k e yw o r d s ：s m a l l w o r l dn e t w o r k ，c h a o t i cs y n c h r o n a z a t i o n ，c o u p l e dm a p l a t t i c e 上海大学 y 6 7 8 0 7 9 本论文经答辩委员会全体委员审查，确认符合上海大学 硕士学位论文质量要求 答辩委员会签名： 主任：淞毛 委员： 阉雅 瞅， ( 纠团财传1 ( 彦粥) 导师：劾m 俐心 答辩日期：硼中2 ，伽 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：塑庄造日期丝! 2 ：鲨 本论文使用授权说明 衣人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有；殴保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：丝焘旌导师签名：曼选墨二_ 日期： 2 0 0 4 年上海大学硕士学位论文 第一章引言 第一节混沌同步的理论知识 混沌现象是2 0 世纪最重要的科学发现之一，它揭示了自然界及人类社会中普 遍存在的复杂行为，如有序与无序的统一，确定性与随机性的统一，这大大拓广 了人们的视野，加深了人们对客观世界的认识。它的研究涉及到自然科学和社会 科学等各个领域，覆盖面之大、跨学科之广、综合性之强，发展前景及影响之深远 都是空前的。国际上誉称混沌的发现，许多人称为继2 0 世纪相对论与量子力学问 世以来的第三次物理学大革命，这场革命正在冲击和改变着几乎所有科学和技术 领域，向我们提出了巨大的挑战。 混沌的发现已有3 0 多年，由于混沌的奇异特性，特别是对初始条件的高度敏 感性，使得有段时间人们总觉得混沌是不可控的，因而在实际上很难达到应用目 的。但2 0 世纪9 0 年代以来，国际上关于混沌控制及混沌同步的研究取得了突破 性进展，使混沌的可能应用出现了契机。混沌同步原理及混沌控制方法在1 9 9 0 年 先后提出，前者是由美国的海军实验室的学者p e c o r a 和c a r r o l l 1 1 提出，他们在电 子线路上实现了混沌同步；后者是由美国马里兰大学的物理学家o t t ，g r e b o g i 和 y o r k e 提出，称为o g y 方法。同年该校的d i t t o 等人利用该法首次在一个物理学系 统上，即磁弹性体上实现了对周期一的稳定控制。随后，混沌控制方法及其实验 的研究迅速发展，取得了很大成就，同时发现混沌控制在众多领域中，诸如在电 子学、保密通讯、密码学、激光、化学生物、脑科学、神经网络及系统工程都有很 大的应用潜力目前，混沌大致可以分为四类f 2 1 ：第一类只产生时间混沌，第二 类只产生空间混沌，第三类同时产生时间与空间混沌，第四类产生功能混沌。跟 丰富多彩的混沌行为相比，目前的混沌控制方法及其应用的研究，只不过刚刚开 始，目前还只是较多地集中在第一类混沌的控制与应用上，时空混沌地控制问题 刚引起了注意，其它类型的混沌控制肖未展开，这是一个大有可为的广阔研究领 域。目前，混沌控制的目标有两种：一个是基于在混沌吸引子中嵌入有无穷多的不 稳定周期轨道，控制的目标是对其中某个不稳定周期轨道进行有效的稳定控制， 另一个是控制目标不要求必须为原系统中的周期轨道，而只要求通过可能的控制 策略、方法和途径，得到我们所需要的目标周期轨道或抑制掉原系统中的混沌行 2 0 0 4 年上海大学硕士学位论文 2 为。现在人们已经提出许多不同的 昆沌控制方法，从非线性系统的类型上说，有 些方法适于离散非线性系统，有些适合连续非线性系统。从控制原理上来说可分 为控制信号反馈控制方法与无反馈控制法，前者反馈的对象可以是系统参数、系 统变量、外部参数( 强度、相位等) 等等。对不同对象的微扰反馈，则产生不同的 控制方法，它们的共同特点都是利用与时间有关的连续小微扰作为控制信号，用 它来实现对特定所需的周期轨道或非周期轨道的稳定控制，在这种控制时，一旦 目标轨道达到，反馈控制往往就失去作用。无反馈控制法，常用来抑制混沌，控 制信号与特定的轨道无关，因而当实现系统控制时，受控输入信号并不等于零， 并且受控后的反映动力学行为轨道可能并不是嵌入在原系统的混沌吸引子中，即 产生了新的反映动力学行为轨道。 混沌同步是一个极其诱人的课题，由于具有巨大的应用潜力，引起了国内外 的极大关注与兴趣。在自然界及实验中存在大量的同步现象，但是发现混沌同步 现象，却是2 0 世纪9 0 年代初的事情，首先由美国学者p e c a r a 和c a r r o l 在电子线路 的专门设计的实验中实现两个系统的混沌同步。这是既令人吃惊，又引人入胜的 现象，因为混沌行为的最大特点就是，运行轨线对初始条件具有高度的敏感依赖 性，所以以前认为在实验室内重构相同的完全同步的混沌系统简直是不可能的。 但是，混沌同步的发展打开了新天地，呈现出诱人的应用发展新前景。混沌同步， 从总体上来说，属于混沌控制的范畴。至今，混沌同步方法分为以下几种类型：第 一种就是p e e o r a 和c a r o l l 提出的同步方案，驱动与被驱动( 响应) 关系来实现， 他们把驱动的混沌系统分成稳定部分与不稳定部分，把具有负的李雅谱诺夫指数 的稳定部分复制成一个响应系统的一部分，然后把响应系统一部分状态变量用驱 动系统中的驱动信号加以驱动，由此可达到响应系统与驱动系统的同步。近年来 该类型同步已经拓广到非混沌同步( 即周期、准周期同步等) 以及高阶同步。第 二种类型的混沌同步则是两个混沌系统相互耦合，由g a p o n o v g r e k h o v 及其合作 者在研究流体湍流时提出的。后来r a h m a n 等从理论上研究了半导体激光阵列系 统中的混沌同步的可能性，1 9 9 4 年美国的r o yt h o r n b u r y 及日本的s r g a w a r a 、 t a c h i k a w a 、t s u k a m o t o 等人各自独立的从实验上观察到两个混沌的激光系统达到 完全同步，他们就是利用激光光强相互耦合的结果，前者用两个n d ：y a g 混沌激 光系统，后者用两个p q s 混沌激光系统耦合，达到同样的效果。l i u 和l e i t i 从数 2 0 0 4 年上海大学硕士学位论文 3 值上研究了两个c 0 2 激光系统耦合，也达到了混沌同步。第三种类型的混沌同步 是通过与时间有关的小微扰的连续反馈方法，该方法首先由p y r u g n s 提出，他又 与t a m a s e r c i u s 一起从实验上验证此方法的有效性，p u 等人用电子线路也进一步 加以证实第四类混沌同步是由m a r i t a n 和b a n a v a r 发展的用噪声感应导致同步的 技术。他们证明了两个混沌系统在相同的噪声作用下，只要噪声强度足够大，就 可能导致两个系统实现混沌同步。 现在我们回顾一下同步的概念和渐近稳定性的知识，这里我们说明h e 和 v a i d y a 有关同步论述来进行讨论。 定义：考虑两个系统，一个驱动系统为： x = r ( t x )( 1 1 ) 其中： x = 。l ( t ) z 2 ( t ) ，。( t ) ) 7 是n 维状态矢量， f = ( t ，x ) ，厶( t ，x ) ) r 是n 维矢量函数。 设以x 为驱动变量时，( 这儿要指出驱动变量不一定要1 维，可以是k 维， n ) ， 则响应系统为： x = f ( t ，x )( 1 2 ) 其中用带撇的表示响应系统的变量： x = z l ( t ) ，。；( t ) ，z ：( ) ) 丁， f = ，l ( tx ) ( ，x ，) t 这里t 为时间，矢量x ，x7 r “令x ( t ；t o 凰) 和x ；t o 弼) 分别为( 11 ) 和( 1 2 ) 的解。存在一个r ”的子集d ( t o ) ，当初值凰，x 6 9 ( t o ) 时，在t _ o 。时，有： = ix ( t ：t o x o ) 一x m ；t o ，x j ) | | 叶0 ( 1 3 ) 则称响应系统( 1 2 ) 与驱动系统( 1 1 ) 达到同步。 倘若d ( t o ) 支撑着整个空间，即d ( t o ) = r “，则该同步定义为全局( 完全) 同 步；倘若d ( t o ) 是r “一个子集，则该同步定义为局部( 部分) 同步，称d ( t o ) 为 同步区域。 2 0 0 4 年上海大学硕士学位论文 4 以上同步的定义不仅适用于混沌同步，也适用于非混沌( 即周期等) 同步。 同时这个定义既适用于自治系统的同步，也适用于非自治系统的同步。 我们把上述定义用到p e c a r a 和c a r r o l 关于驱动响应系统的同步的类型，可以 假设把驱动( 主) 系统可以分成两部分： 吐= g ( t ，“，w )( 1 4 ) 曲= h ( t ， )( 1 5 ) 其中( 1 4 ) 为不稳定部分，( 1 5 ) 为稳定部分，则响应系统应为： 茜，= h ( t ，u ，”)( 1 6 ) 在混沌同步中，响应系统初始条件的选择是很重要的，必须落入同步区域内， 才能达到与驱动系统同步。后来，p e c o r a - c a r r o l l 为了阐明实验上观察到的混沌同 步现象，对响应系统的稳定性及同步原理进行了分析，这里简单说一下他们的结 果。在驱动响应关系的 昆沌同步类型中，由驱动系统与响应系统通过驱动变量构 成总体动力学系统，其特点是，响应系统的行为取决于驱动系统，而驱动系统的 行为与响应系统无关。p e c a r a - c a r r o l 方法的关键在于主系统能够分拆，即能够分 拆为两个子系统，然后构造驱动的稳定部分与响应系统之差构成的误差系统： a w = h ( t ，u ，w 7 ) 一h ( t u ， )( 1 7 ) 。通过讨论这个误差系统零解的渐近稳定性f 3 1 ， p e c o r a 与c a r r o l l 发现了混沌同步的条件李雅谱诺夫指数稳定性判据( 或同步) 定理。考虑到在所有的时刻t ，具有o ( o ，t ) 的非线性非稳恒系统= 4 ( t ) z 十o ( z ，t ) 的零解将是渐近稳定的f 3 1 ，只要该系统满足下列条件； ( 1 ) 对于t ，l i m 。o “；鲁产= 0 都成立； ( 2 ) 对于所有的t ，a ( t ) 都是有界的； ( 3 ) 线性系统i = a ( t ) x 的零解是渐近稳定的。 上述判据( 1 ) 和( 2 ) 对于多数的误差系统都是成立的。但是，判据( 3 ) 只有在李雅 谱诺夫指数都是负的时候才确保成立。因此p e c o r a - c a r r o l l 的混沌同步原理归结为 一句话就是：响应系统的所有的李雅谱诺夫指数都为负值时，响应系统才能达到 与驱动系统的混沌同步。 2 0 0 4 年上海大学硕士学位论文 5 实际上，却只有少数混沌系统能够这样分拆为两个子系统。下面我们以l o r e n z 系统为例【2 ，来说明同步原理的应用。 口( 可一z ) x z + r x y ( 1 8 ) x y d z 当参数为f = 1 6 ，b = 4 ，y = 4 5 9 2 时，系统处于混沌，为了考察能否用该系统实现 驱动一响应混沌同步，则必须计算由l o r e n z 系统所构造的各种总体驱动一响应系 统的李雅谱诺夫指数。于是，构造两种总体系统可以分别描述如下： 第一种，由x 做驱动变量时，响应系统为： ! = 一。十r z 一( 1 9 ) i 2 k x y l b z 第二种，由y 做驱动变量时，响应系统为： jj k “圹一)( 1 l 。) 【一= x t y b z 7 用带撇来表示响应系统的变量，不带撇的变量为驱动系统响应的变量。为了定量表 示同步过程，人们通常简单地采用驱动系统与响应系统地相应变量之间地差值， 或它们差值的绝对值或其总和来判断同步的情况。例如本例的第一种情况，可以 用下面的量： ly y 7i _ 0 ，当t o 。 iz z 7 - 0 ，当t - 。 或iy y i + fz 一| _ 0 ，当t _ 。 倘若只有某个变量上满足差值趋近于0 ，则称系统为部分同步，当各分量的差值 的绝对值的和趋近于0 时，称系统为完全同步。 第二节小世界网络的背景知识 2 1 复杂网络的发展 2 0 0 4 年上海大学硕士学位论文 6 现在，从物理学到生物学甚至是社会学等多个领域对网络都有广泛的研究。 总起来说，一个网络可以简单地用相互连接的结点来表示，每个结点上都可以赋 予一个基本动力学元素，用结点之间的连接表示基本元素之间的相互作用，这个 网络就是一个赋予了特殊含义的动力系统。比如，根据研究需要，一个结点可以 代表因特网的子网络，可以是万维网中的一个网页，也可以是酶代谢过程中的酶 解物和酶类以及在科学领域中进行合作研究的一个科学家，甚至是建立联系的个 人组织或国家等f 4 , 5 ，6 7 1 。这些连接在网络中称为连线。 数学上，网络是图论所研究的对象，经典的网络研究集中在正则图( 在网络研 究中称规则网络) 和随机图两大类上，其中研究最为广泛的随机图模型是由e r d o s 和r e n y i ( e r ) 8 】提出的。尽管我们的直觉认为许多现实世界中的复杂网络既不是 完全规则的，也不是完全随机的，但因为缺乏大型真实网络的拓扑信息，导致人 们在网络上的研究只能在e r 随机图上徘徊近四十年f 9 1 。近来，通过计算机获得 资料使得许多关于现实世界真实网络的拓扑结构的大型数据库的出现，人们得以 研究网络的拓扑性质，发现现实中的网络大多具有小世界性( s m a l l w o r l de f f e c t ) 和 无标度特征( s c a l e f r e ef e a t u r e ) j 1 0 ，1 1 ，1 2 。可见真实网络既不是完全规则的，也不是 完全随机的，现在通常称具有小世界性和无标度特征的网络为复杂网络。 在1 9 9 8 年，为了表述正则图到随机图的过渡，w a t t s 和s t r o g a t z ( w s ) 1 3 1 引入 了小世界网络的概念。事实上，小世界现象是非常普遍的，其中最为著名是六十 年代社会心理学家m i l g r a m 揭示的“六人模型” 1 4 ，他通过调查提出，在美国要 认识一个人，平均需要六个人就可以达到目的。在近年中，小世界性在许多网络 中都得到了证实，例如前面提到的几个模型以及食物链构成的网络f 1 5 1 ，人类语 言形成的网络等都具有小世界性质。 e r 随机图和部分w s 小世界网络模型的一个共同的特征就是网络的连接分 布度在平均值处取得极值，并且以后是指数衰减的。这种网络叫做“指数型”网 络，其共性是：每个结点都有大约相同数目的连接。近年来发现的另一种复杂网 络特征是无标度的( s c a l e f r e en e t w o r k ) ，即它的连接度分布服从幂法则f 1 6 ，1 7 1 的， 即：p ( ) 一7 ( 表示结点的连接数目，1 表示对应于每个网络都是常数) 。它 的特点是：大多数结点有很少的连接，只有几个结点有许多连接。因而这种网络 最重要的拓扑特征是连接度的不均匀性。 2 0 0 4 年上海大学硕士学位论文 7 耦合动力系统在非线性科学中引起了x f f 的许多注意，在上世纪九十年代， 这方面提出了许多有趣的现象，也得到了充足地发展 1 8 1 9 ，2 0 ，2 1 。但这些系统从 网络角度来看都是集中在规则网络上的，比如c m l 2 2 是建立在最邻近耦合的规 则网络上的，g c m 建立在全局耦合网络上的，耦合振子系统则是建立在最邻近 耦合或全局耦合网络上的。如果我们将复杂网络中的格点赋予动力系统，则整个 网络就构成一个巨型动力系统。这种动力系统行为与以前c m l ，g m l 以及耦合振 子系统是否一样呢? 换句话说，我们要讨论网络拓扑结构对其上动力系统行为的 影响。事实上，网络的拓扑结构对其动力学特征起着十分重要的作用。例如，尽管 有证据表明足够耗散的耦合系统可以达到同步，但是这个不能解释即使有很弱的 耦合时，许多真实的网络在仍能以更快的速度达到同步。因而研究复杂网络的拓 扑结构对其动力系统行为的影响必将受到越来越多重视 2 3 ，2 4 ，2 5 ，2 6 ，2 7 而成为一 个重要研究方向。 2 2 网络的拓扑结构中的一些基本概念 研究复杂网络的性质和量化方式涉及到如下三个概念，平均步长( t h ea v e r a g e p a t hl e n g t h ) 、串接数( t h ec l u s t e r i n g ) 和分布度( t h ed e g r e ed i s t r i b u t i o n ) 。实际上， w a t t s 和s t r o g a t z 在小世界网络方面的最初尝试是构建一些象随机图一样有很小 的平均步长、象规则网格一样有很大的串接数的网络模型。另外，无标度网络是 在观察到许多真实网络分布度服从幂法则的基础上发现的，因此，这三个量格外 重要。现在，我们介绍一下这三个概念。 1 ，平均步数 我们考虑一个共有n 个结点的网络，把网络中的两个结点i 和j 的距离d 。定义 为：连接这两个点的最短路径的连线段的条数。网络的直径d 就是网络中所有结 点对之间距离的最大值，即d = m a x d 。，) 。网络中共有型；丑个结点对，则这个 网络的平均步数l 定义为：l = 每舞学。这里l 决定着网络有效性的大小。例 如，在有一个朋友关系连接的网络 2 8 里，如果两个人互相认识，赢接用两个人的 朋友关系就可以建立联系，没必要通过别人来认识，这时d ，= 1 ；如果两个人通 过第三个人认识的，就经历了两人都和第三个人的朋友关系，即通过两个朋友关 系即可建立联系，因此这里南= 2 ，也就是说，我们定义在朋友关系的网络里， l 就是连接两个人的平均朋友关系数。 2 0 0 4 年上海大学硕士学位论文8 显然，缶茎1 ，当且仅当这个网络是全局耦合时寺= 1 ，也就是说全局耦合 网络中的任意两个点都是直接相连的。复杂网络里的一个最重要的发现就是：在 相同的结点个数情况下大多数实际网络的连接线数目比全局网络的少一个量级， 但是它的平均步数相对却很小，这种性质叫做小世界性。为了更好的理解，我们 考虑下面这个结构简单的网络，见图1 1 ： 图1j 这是一个含有5 各结点和5 条连接的简单网络 从图1 1 中可以看出，各结点间的最大步数要数最右边的两个点之间的步数 3 ，即为网络的直径。网络中共有5 r x 4 = 1 0 个不同的结点对，各对结点之间的步数 和为1 6 ；所以这个网络的平均步数为16 。 2 ，串接数 在你的朋友网络里，很可能你朋友的朋友就是你的朋友；或着说，换一种说法， 你的两个朋友彼此都是朋友。这种性质叫做网络的串接数。更准确地说，我们能 把结点的串接数定义为一个结点的邻近点之间的连接线段条数在所有可能连接条 数中所占比例。设结点i 有凰个其它的结点和它直接相连，这些k 。点称为i 的邻 近点，显然这些邻近点之间最多有丝： 出条线段，设网络中实际上有蜀条，则 点i 的串接数g 为真实存在的连接数目与总共可能存在的连接数目的比，也即： g = 耵譬币。那么整个网络的串接数就是所有结点串接数a 的平均值例如在 2 0 0 4 年上海大学硕士学位论文 9 上面的图形中，对于最上面的结点，有三个点和它相连接，最多有3 条连接线， 而实际上有l 条连接线，所以这个结点的串按数为：；在朋友网络里， a 反映 了i 这个人的朋友之间熟悉程度。c 表明一个人群中人们的朋友关系所占的比例 情况。显然，cs1 ，当且仅当这个网络是全局耦合时c = 1 ，即朋友网络中每个 人都认识其它的人。在一个完全随机的网络里，c 一_ 1 与许多大型真实网络相 比，这个值是非常小。人们发现，大多数无标度真实网络都有聚合趋势，即它们的 串接数尽管明显比1 小，但都比o ( n 。) 大的多，这也是小世界网络的性质。 3 ，分布度 对于一个结点的特征研究最容易也最多的是它的度，也就是这个结点的连接数， 所有结点的度的平均值叫做这个网络的度，记为( k ) 。结点和其它点连接的情况 用分布函数p ( k ) 表示，它代表从网络中随机选择的一个结点恰好有k 条连接的概 率。一个规则网络有一个简单的度数列，所有结点有相同的连接数目，因此度的分 布图包含一个简单的6 函数。网络中连接的任何随机性都将增加这种峰的宽度。 在一个有限维的完全随机网络里，度数列服从普哇松分布，即有：p ( k ) “e - 。) i 喾 普哇松分布的形状是从峰值开始指数递减的。由于指数递减的性质，发现一个结 点有女( ( ) ) 条边的可能性变得很渺茫。 过去几年里：许多试验结果表明许多数真实网络的分布度明显偏离普哇松分 布。特别是包括万维网、因特网和代谢网在内的许多网络的分布度更是准确服从 幂法则：p ( k ) 一一看这样一个例子 2 8 ，一个有n = 1 0 0 0 0 0 个结点的网络， 服从指数为2 的幂法则分布度，则有 的结点，也就是大约i i i i i 个结点恰有三 个连接；其中万分之一的点也就是1 0 个结点有i 0 0 个连接。由于幂法则和特征标 度( c h a r a c t e r i s t i cs c a l e ) 无关，因此习惯上称服及幂法则的网络口q 做无标度网络。 2 3 网络的种类 从现在发展来看，网络有经典和复杂两种。经典网络主要包括规则网络和随 机网络，复杂网络主要是指有小世界性和无标度性的网络。下面我们分别给出介 绍。 第一是完全规则网络。所谓完全规则网络是指网络中的结点的连接是按照指 定规则建立的。这儿我们介绍两种常见的规则网络，首先我们考虑一种规则网络 为全局耦合网络模型( g l o b a l l yc o u p l e dn e t w o r k ) ，网络中任何两个结点都相连接，这 2 0 0 4 年上海大学硕士学位论文 1 0 样两个结点之间步数都为1 ，所以它的平均步长l = l ，是所有网络中最小的。此 外全局耦合网络的串接数c = l ，是所有网络中最大的。这种网络符合小世界的性 质，但仍与实际网络不吻合。这是因为：许多大型真实网络中边的数目是o ( x ) ， 即真实网络都是稀疏的。而一个有n 个结点的全局耦合网络将有鱼1 笔生条边，即 连接线数目为o ( n 2 ) ( 这种网络是非稀疏的) ，而非o ( n ) 。另一种被广泛研究的， 稀疏的规则网络模型是有最邻近耦合网络，每个结点只和几个相邻的结点连接， 所以它的结构是个一个规则图。一个有周期边界条件的最近临域耦合的网格模型 是有n 个点排在一个圆环上，每个结点i 都和相邻的结点i 土l ，i 土2 ，i 土等，k 是个偶数。这样的网络的串接数为：c = 型4 ( 堡k - 望1 ) 一；显然串接数比较大，可这种最 邻近耦合网络不是小世界网络，因为它的平均步数太大：l 一嘉一o 。，( n 斗o 。) 它的分布度为： 耶，= ：篡 第二种是完全随机网络。先举个例子说明一下，你有许多纽扣散乱地掉在了 地上，你用同样的机率p ，把每两个纽扣用一根线串起来，结果是一个e r 随机 网络，有n 个结点和大约坐必2 条边。由此可见，所谓随机网络就是以随机方 式把结点联系起来所形成的网络。随机网络图的主要目的是研究多大的连接概率 使网络性质最可能增加。e 7 d s s 和r d n y i 的最大发现就是许多随机网络的重要性 质出现临界现象。e r d s s 和r d n y i 说明了如果概率p 大于某个临界值：p 。塑铲， 则几乎随机网络每个结点都是直接或间接相连的，也就是网络中存在很大的串接 数。在我们的例子中，这就意睬着你要拾起所有的纽扣，只需要随便拾起一个纽 扣即可。随机网络的平均步数为：l 一兰芋等随着网络规模的增加，它的平均步 数成对数增加，正是小世界性的一种特征。由于l n ( n ) 随着增加的很慢，它允 许在一个比较大的网络里存在一个很小的平均步数。另一方面，在一个完全随机 网络里，一个人的两个朋友也是别人的朋友的概率不会比人群中任意选两个人的 可能性大。因此，e r 随机模型的串接数c 远远小于l ，即c = p = 堪l 这说明 在一个大型的随机网络里，不会有较大的串接数。这不符合小世界性所要求的。 对于一个比较大的n ，一个e r 数会产生一个均匀网络，它的连接分布度大约服 从一个普哇松分布。然而，大多数真实网络的分布度明显偏离于随机网络的普哇 2 0 0 4 年上海大学硕士学位论文 11 松分布。为了满足真实网络的分布度，人们可以用给定的分布度构造e r 随机网 络，这类模型叫做g e n e r a l i z e dr a n d o mg r a p h s 2 9 ，n e w m a n 已经发展了根据给定的 分布度构造随机网络的方法 3 0 第三，小世界网络，规则网络的簇和性较好，可是没有显示很好的小世界性。 另一方面，随机网络显示了较好的小世界性，却没有理想的串接性。它们没有产 生六人模型和万维网等真实网络的性质。因为这些真实网络毕竟既不是完全规则 的，也不是完全随机的。一个人认识他的邻居们，然而他的朋友并不仅限于象规 则网络描述的那样仅限于住在隔壁的那些人。此外，万维网中的网页相互连接也 非e r 网络需要的那样随机产生的。为了描述规则网络到随机网络的过渡状态， w a t t s 和s t r o g a t z 介绍了一种有意义的小世界网络，现在人们成为w s 小世界模型 ( w s s m a l l - w o r l dn e t w o r km o d e l ) ，最初的w s 模型这样描述的： ( 1 ) 1 按顺序连接。设一个网络有n 个结点，排在一个圆环上，从最近的邻点开始耦 合，每个点i 都和它的临点i 土1 ，i 土2 ，i 士k 这里是整数。为了满足稀疏性， 而不是网络所有结点的都相互直接相连，我们考虑1 n ( 2 ) 随机性。网络的每条边以概率p 重新连接。这里的重新连接意思是从一个连接 的末端点转移到从网络中随机选取的一个结点上，当然不能出现两个结点被连接 两次的情况，即两个点之间最多连接一次，并且结点不能和它自身连接。 这个结果将产生2 学条非连接邻近结点的边，即它们所连接的结点以前是经过多 步才建立连接的。在0 到l 之间改变p ，我们可以控制网络的结构。发现这样产生 的很大部分网络具有l 小、c 大的特点，即有小世界性质。自w a t t s 和s t r o g a t z 开 创了小世界网络模型以来，对模型及其性质的研究普天盖地而来。一个研究的很 多的模型是n e w n l a n 和w a t t s 提出的近来称作的n w 小世界模型，这个模型里， 一个结点既不和它的两个最邻近结点的任何一个中断连接，同时以概率p 增加在 连接网络中的结点对。当然，同样要求两个结点至多连接一次，且每个结点不和 它自身相连。如果p = 0 ，则n w 模型就是原始的最邻近耦合网络，若p = 1 ，就成 了全局耦合网络。由于n w 模型不会出现w s 模型的孤立的串接现象，在某种程 度上研究起来比w s 模型更为方便；在n w 模型中当p 很小且很大时，就成为 w s 模型了。人们常提起的小世界网络的典型模型就是这两个。 第四，无标度模型。e r 随机网络的分布度特征兢是网络的连接分布集中在 2 0 0 4 年上海大学硕士学位论文 1 2 平均值处，且按指数减小的，这样的网络称为指数型网络。而许多真实网络研究 中很有意义地发现许多复杂网络的分布度是无标度的，即它们的连接分布服从幂 法则。为了解释幂法则，b a r a b d s i 和a l b e r t 在1 9 9 9 年提出了一种新的网络模型， 他们认为一个无标度网络形成的两个重要因素是增长性和连接偏好性 1 6 。这是 指网络通过增加新的结点而连续增长的，还有新产生的结点与已有结点之间连接 的机率是与结点已经存在的连接数目成正比的( 即富者越富) 。他们提出的b a 无 标度模型是这样构造的： ( 1 ) 增长性。开始有m o 个结点的网络，每一步演化都产生一个新的结点，并且和 m ( m 0 我们进一步分析c 的导数在c = 垃两旁的取 值，得到2 为c 得极大值点，所以，从理论上看，为确保c 取得更大的值，女取 z 附近的值较好，但由于。zn 一 ，这样的话要引起连接线的增加。从现实情 况考虑，为了构造符合有o ( n ) 条连接线的小世界网络，只能放弃k 取k 2 附近的 值。而在 0 。选 择适当的耦合常数，满足关系：l e l + l n 0 选择适当的 耦合参数e ，满足关系式：l e l 十l n 0 ( 4 1 0 ) ( 2 ) 耦合参数e 要满足： l e l + i n 侧 0 。分两种情况分析： ( 1 ) 当至祭吨1 一箍0 并且有1 一格1 一尚，所以i = 1 一船 ( 2 ) 当 争日寸，l 尚 o 也就是箍一1 1 一格 即k 曼n 一2 。这样当n 一2 时，就有j = 1 一尚综上所述，当0 1 且 女n 一2 时， k 1 。高 ( 4 - 1 2 ) 我们将( 4 1 2 ) 代入( 4 1 1 ) 分两种不同情况分别讨论： 第一，当l e l 和固定时，我们得到： l e 1 ) ) e 0 ，所以e x p ( 一l e t ) 0 因此命题成立只需要： l f ：j 玉也就是： c o s 努1 一b 令f ( n ) = c o s 簪+ 丙与一1 ，则，( ) = s i n 可2 r r 带2 r r + r i 若砰 0 因为，( 1 8 ) 0 ，所以 当n 1 9 时，( ) 0 。( 57 ) 左边的值随着女的增大而减小，所以有当k 2 时，( 57 ) 显然成立。即命题得证。 命题5 说明小世界网络上的动力系统