（凝聚态物理专业论文）加反馈机制的复杂网络动力学.pdf

摘要 在欧氏空间中复杂网络可以是有形物体。如电力网、互联网、高速公路或地 铁系统、甚至神经网络等等。近年来，复杂网络的分析和建模、网络动力学系统 都成了交叉学科中的一个重要研究课题，并且在工程物理、数学、计算机科学、 生物学，经济学、和社会学领域取得了非常重大的进展。其中，复杂网络动力学 对复杂网络的研究起着关键性的作用。 在这篇学位论文里，首先，我们通过解析方法和大量的数值模拟来研究指数 网络中引进了反馈机制的流行病动力学。我们发现引进反馈机制后，疾病能波及 的范围有所减少，另外，加反馈机制并不改变流行病传播阚值。这些结果能帮助 我们很好的理解社区中流行病传播现象以及制定有效的免疫策略来控制流行病 的传播。然后，基于i s i n g 旋子系统和s z n a j d 模型，我们提出了一种新的舆论 演化模型，同时将新的模型应用到平方格子里并进行了大量的数值模拟。为了更 加符合实际情况，我们考虑了两种影响，即最近邻的意见和整个社区的平均意见， 发现我们的模型得出了很多有趣而又有用的统计结果。 论文的结构是这样安排的：第一章，我们给出了复杂网络研究的背景，然后 介绍了我们这篇论文的只要内容；第二章，介绍了图的基本概念以及复杂网络的 一些基本参数。另外我们简要回顾了前人所提出了几种典型的网络模型，它们分 别是：随即网络，小世界网络，无标度网络和等级( 层次) 网络。最后我们还考虑 了复杂网络中的动力学与复杂网络的同步；第三章，介绍了两种经典的流行病传 播模型和三种免疫策略，然后考虑了指数网络中引进反馈机制的流行病传播动力 学行为；第四章，在更复杂的社会影响下规则网络( 平方格子) 中的舆论传播及其 演化；第五章，总结了在硕士期间我们所做的主要工作，对复杂网络研究工作做 出了展望。 关键词：复杂网络，小世界，无标度，流行病动力学，反馈机制，s z n a j d 模 型，舆论演化，规则格子 a b s t r a c t c o m p l e xn e t w o r kc a nb et a n g i b l eo b j e c t si nt h ee u c l i d e a ns p a c e ，s u c ha se l e c t r i c p o w e r 蛳d s ，t h ei n t e r n e t , h i g h w a y so r 锄b w a ys y s t e m s ，a n dt h en e u r a ln e t w o r k i n r e c e n ty e a r s ，t h ea n a l y s i sa n dm o d e l i n go fn e t w o r k s , a n da l s on e t w o r k e dd y n a m i c a l s y s t e m s ，h a v eb e e nt h es u b j e c to fc o n s i d e r a b l ei n t e r d i s c i p l i n a r yi n t e r e s t , y i e l d i n g s e v e r a ls i g n i f i c a n tw o r k si np h y s i c s ，m a t h e m a t i c s ，c o m p u t e rs c i e n c e ，b i o l o g y ， e c o n o m i c s , a n ds o c i o l o g y i ti sn o wk n o w nt h a tt h ed y n a m i c so fc o m p l e xn e t w o r ki s v e r yc r u c i a lt ot h er e s e a r c ho f i t i nt h i sd i s s e r t a t i o n , f i r s t l y , w ci n t r n d u c eaf e e d b a c km e c h a n i s mt os t u d yt h e s p r e a d i n go fa ne p i d e m i cb ya n a l y t i c a lm e t h o d sa n dl a r g es c a l es i m u l a t i o n si n e x p o n e n t i a ln e t w o r k s i ti sf o u n dt h a ti n 灯n d n e i n gt h ef e e d b a c km e c h a n i s mc a nr e d n c e t h ed e n s i t yo fi n f e c t e di n d i v i d u a l s f u r t h e r m o r e , i td o e sn o tc h a n g et h ee p i d e m i c t h r e s h o l d t h e s er e s u l t sc a nh e l p 璐t ou n d e r s t a n de p i d e m i cs p r e a d i n gp h e n o m e n a0 1 1 s o c i a ln e t w o r k sm o r ep r a c t i c a l l ya n dd e s i g na p p r o p r i a t es t r a t e g i e st oc o n 订o ls o c i a l i n f e c t i o n s s e c o n d l y , b a s e d0 1 1t h ei s i n gs p 缸s y s t e ma n dt h es z n a j dm o d e l ( s m ) ，w e i n t r o d u c ean e wm o d e lt os t u d yt h eo p i n i o ne v o l v i n gi ns m0 1 1s q u a r eh t t i c e sb yl a r g e s c a l en u m e r i c a ls i m u l a t i o n s t ob em o r er e a l i s t i c t w ob a s i ci m p a c t sa r ec o n s i d e r e di n t h ep r o c e s so ft h ee i g h ti n d i v i d u a l s ? d e c i s i o n - m a l t i n g , i e ，t h ei n f o r m a t i o ng o v e r n e d b yt h en e i g h b e ma n dt h ea v e r a g eo p i n i o no f t h ew h o l ec o m m u n i t y i ti sf o u n dt h a to u r m o d e ls h o wm a n yu s e f u la n di n t e r e s t i n gs t a t i s t i c a lr e s u l t s t h et h e s i si so r g a n i z e da sf o l l o w s ： j i nc t l a p t e r1 ，w eg i v eab r i e fr e v i e wt ot h es t u d yo fc o m p l e xn e t w o r k s ，i n c l u d i n g i f sb a c k g r o u n d 、m a i nc o n t e n t sa n ds i g n i f i c a n c e c h a p t e r2 i sa b o u tt h eb a s i cc o n c e p to ft h eg r a p ha n dp a r a m e t e r so ft h ec o m p l e x n e t w o r k s w et h e nb r i e f l yr c 、r i e wt h em a i nm o d e l st h a th a v eb e e np r o p o s e do v e rt h e y e a r s , f o c u s i n g0 1 1r a n d o mg r a p h s ，s m a l l w o r l dm o d e l s ，s c a l e f l e en e t w o r k sa n d h i e r a r c h i c a ln e t w o r k s f i n a l l y ，w eg i v eas p e c i a le m p h a s i st ot h es t u d yo fd y n a m i c s a n ds y n c h r o n i z a t i o ni nc o m p l e xn e t w o r k s i nc h a p t e r3 ，w er e v i e wt w oc l a s s i c a lm o d e l so fs p r e a d i n go fe p i d e m i c sa n dt h r e e i m p o r t a n ts t r a t e g i e so fi m m u n i t y t h e nw ec o n s i d e rt h ee p i d e m i cd y n a m i c sw i t h f e e d b a c km e c h a n i s mi ne x p o n e n t i a ln e t w o r k s i nc h a p t e r4 ，w ea n a l y z et h eo p i n i o nf o r m a t i o ni ns z n a j dm o d e lw i t hm o r ec o m p l e x s o c i a li m p a c t f i n a l l y , c h a p t e r5s u m m a r i z e so u rm a i nw o r kd u r i n gt h em a s t e ra n dp r e s e n t s o u t l o o k so f f u t u r ew o r k si nt h i sf i e l d 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 d , s c a l e - f r e e , e p i d e m i cd y n a m i c s ， f e e d b a c km e c h a n i s m ，s z n a j dm o d e l ，o p i n i o nf o r m a t i o n , r e g u l a rl a t t i c e m 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：洲百丝幽1 。7 年g 月j 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密硒。 ( 请在以上相应方框内打“”) 作者签名：主 面丝日期：如。7 年6 月心日 锄擀：苏蒙互 魄知严肌日 加反馈机制的复杂网络动力学 第一章绪论 复杂性科学已经成为最受关注的新兴交叉学科之一，许多科学家为复杂科学 的发展进行了不懈的努力。然而，迄今为止，复杂性科学还没有取突破性的进展， 对它所做的研究还只是冰山一角。著名数学家f a d o f i a 教授表达了对多年从 事复杂性科学研究的科学家们的共同感受，他说：eg of r o mc o m p l e x i t yt o p e r p l e x i t y ( 我们从复杂到了困惑) ”。使科学家们感到困惑的一个重要原因是，复 杂性科学的研究正在探索阶段，一些基础问题亟待解决，如：是否存在从简单到 复杂的自然法则的问题? 什么是复杂性的根源? 等等，这些极大的阻碍着复杂性 科学的发展，如果不从理论上得到解决，复杂性科学就难以建立起坚实的理论基 础，从而影响和制约复杂性科学的发展。但与此同时，这也给很多科学家带来了 一个难得的机遇，为一些科学家提供了一个施展才华的舞台。其中复杂网络 ( c o m p l e xn e t w o r k s ) 1 ，2 】就是最近才兴起的- - 1 7 交叉学科。 2 0 世纪9 0 9 代以来，随着以i n t e r a c t 为代表的信息技术的迅猛发展，人类社会 大步迈入了网络时代。从生物体中的大脑到各种新陈代谢网络，从大型电力网络 到全球交通网络，从i n t 锄c t 到w w w ，从科学家协作网络到各种政治、经济、社 会关系网络等，可以说，人们已经生活在一个充满着各种各样的复杂网络的世界 中。它既给人类社会生产和生活带来了极大的便利，大大地提高了人类生产效率 和生活质量，但同时它对人类社会的负面冲击也随之而来，如在计算机网络中的 计算机病毒和社会网络中的流行病等的快速传播以及电力网络中的大面积停电 事故等。因此，人类社会的日益网络化需要人们对各种人工和自然的复杂网络的 结构和功能有更好的认知。长期以来，社会网络、生物网络和通信网络等分别是 社会科学、生命科学和通信科学等不同学科的研究对象，而物理学家所建立的复 杂网络理论所要研究的则是这些看上去互不相关的复杂网络之间的共性和处理 它们的普适方法，从这些复杂的系统中找出简单的物理规律，或者说，用相对简 单的物理原理去解释复杂系统的结构、功能和形态。2 0 世纪末，复杂网络理论迅 速渗透到数理学科、生命学科和工程学科等众多不同的领域，成为当前科学研究 中众多学科共同关注的一个全新的研究领域，被誉为“网络新科学( n e ws c i e n c eo f n e t w o r k s ) 3 ”。近年来，作为对物理( 自然) 系统、生物系统、社会系统等诸多复 杂系统研究的一个重要切入点，复杂网络结构和动力学的定量和定性特征的研究 已经成为一个极具挑战性的课题。 1 1 复杂网络研究的背景 复杂网络的研究可追溯到1 8 世纪最伟大的数学家欧拉对哥尼斯堡 硕士学位论文 ( k o n i g s b e r g ) 七桥问题的探讨。k o n i g s b e r g 是现俄罗斯的一个城镇，城中有一条 贯穿城区的河流和两个小岛，两岸和两岛之间有七座桥，如图1 1 所示。相传有 这样一个有趣的问题：一个人能否在一次散步中走过所有的七座桥，而且每座桥 只经过一次最后返回原地? 这个问题看起来似乎相当简单，但长期以来没有一个 人能走出这样一条路径。1 9 3 6 年，欧拉( e f i l e r ) 利用数学抽象法，将被河流分隔开 的四块陆地抽象为四个点，而将连接这四块陆地的七座桥看成连接四个点的七条 线。这样就得到了由四个点和七条线构成的一个图，如图1 1 所示。于是七桥问 题转化为如下的数学问题：从图l 中任意一点出发，经过每条边一次而后返回原 点的回路是否存在? 欧拉给出了存在这样一条回路的充要条件，并由此推得上述 七桥问题是没有解的。 。 f 口 图1 1 哥尼斯堡七桥问题示意图 欧拉对七桥问题的抽象和论证思想，开创了 数学中的一个重要分支一图论。因此，欧拉被 称为图论之父，而图1 1 也被称为欧拉图。事实 上，今天的人们对于复杂网络的研究与当年欧拉 关于七桥问题的探讨在某种意义上是一脉相承 的，即网络结构与网络性质密切相关。 在欧拉解决七桥问题后的相当长的一段时 间里，图论并没有取得长足的进展。直到1 9 3 6 年关于图论的第一本专著出版，它才进入飞速发 展的阶段。2 0 世纪6 0 年代，由匈牙利数学家 e r d 6 s 和r 6 n y i 建立的随机图理论【4 】被公认为是开创复杂网络理论的系统性研 究。由他们所建立的随机图模型( e r 模型) 成为了当时研究复杂系统的基本模型。 在e r 模型中，任意两个节点之间有一条边相连接的概率为p 。因此，一个含有 n 个节点的随机图中边的总数是一个期望值p n ( n 一1 ) 2 的随机变量。e r d 6 s 和 r 6 n y i 系统地研究了当寸o o 时e r 随机图的性质( 如连通性等) 与p 的关系。该 模型提出以来在网络研究中一直扮演着重要的角色，被广泛地应用于社会学和生 态学的研究之中。同时，随机图理论在随后近4 0 年的时间里一直是研究复杂网 络结构的基本理论。 实验上的突破是科学不断向前推进的原动力。在随机图占据主导地位的期 间，人们也做了试图揭示社会网络特征的一些实验。其中最著名的是m i l g r a m 的 小世界实验【5 】和k e v i n b a c o n 游戏( g a m e o f k e v i n b a c o n ) 1 。这些实验预示着网络 研究将出现一场新的革命。下面我们来看看m i l g r a m 的实验是怎么做的。首先， 他选定了两个目标对象：一个是美国马萨诸塞州的一位神学院研究生的妻子，另 一位是波士顿的一个证券经纪人。然后他在遥远的堪萨斯州和内布拉斯加州招募 1 h t t p ：w w w c s v i r g i n i & e d u o r a c l e 2 加反馈机制的复杂网络动力学 了一批志愿者。m i l g r a m 要求这些志愿者通过自己所认识的人，用自己认为尽可 能少的传递次数，设法把一封信最终转交到他所给定的两个目标对象的一个的手 中。m i l g r a m 根据最终到达目标者手中的信件的统计分析发现，从一个志愿者到 目标对象的平均距离为6 。因此，m i l g r a m 推断，地球上任意两个人之间的平均 距离为6 。也就是说，平均中间只要经过5 个人，你就能与地球上任何一个角落 的任何一个人发生联系。这就是著名的“六度分离推断。实验结果在某种程度上 反映了人际关系的叫、世界，特征。然而在此实验中，只有少量信件送到了目标对 象手中，实验的完成率很低，并且m i l g r a m 总共只送出了3 0 0 封信，用如此少的 数据来统计而获得人际关系网络的性质，其可信度显然是非常低的。为了检验哕i 度分离”推断的正确性，随后人们又做了一个有趣的实验：k v v i nb a c o n 游戏。游 戏的主角是美国电影演员b a c o n ，游戏目的是去调查b a c o n 和其他演员的联系。 在游戏里每个演员定义了一个b a c o n 数：如果一个演员和b a c o n 演过电影，那么 他( 她) 的b a c o n 数为1 ：如果一个演员没有和b a c o n 演过电影，但他( 她) 和b a c o n 数为1 的演员演过电影，那么该演员的b a c o n 数为2 ，以此类推。这个游戏就是 通过是否共同演出一部电影为纽带建立演员之间的关系网。而b a c o n 数就描述了 这个网络中任意一个演员到b a c o n 的最短路径。通过调查6 0 万左右个世界各地 的演员和近3 0 万部电影，人们发现最大的b a c o n 数为8 ，而演员的平均b a c o n 数为2 9 4 4 。 2 0 世纪后4 0 年里，许多关于小世界现象的实验不断被报道。例如，科学家 协作网络的e r d o s 游戏2 ，i n t e r n v t 的小世界实验3 等。这些实验的涌现使得人们 对复杂网络的科学探索发生了重要的转变，复杂网络理论也不再局限于数学领 域。人们开始考虑节点数量众多、连接结构复杂的实际网络的整体特性，在从物 理学到生物学的众多学科中掀起了研究复杂网络的热潮。世纪之末，两篇开创性 的文章标志着网络研究新纪元的开始：一篇是美国康奈尔( c o m d 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 杂志上发 表的题为“小世界”网络的集体动力学( c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s ) 的文章【1 】；另一篇是美国n o t r ed a m e 大学物理系的b a r a b 缸i 教授及其 博士生a l b e r t 于1 9 9 9 年l o 月在s c i e n c e 杂志上发表的题为随机网络中标度的 涌现( e m g x g e n c eo fs c a l i n gi nr a n d o mn e t w o r k s ) 的文【2 】。这两篇文章分别揭示 了复杂网络小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产 生机理。 1 2 复杂网络研究的主要内容 复杂网络的研究尚处于起步阶段，不同领域的研究者们都在不同的方向展开 了研究工作，开辟了一些复杂网络的研究方向，相信随着今后研究的进一步展开， 3 硕士学位论文 在该领域会有更多重要的研究方向被开辟出来。就目前而言，复杂网络的研究至 少包括了一下几个方向： 1 对实际网络进行统计分析 这一个课题可视为复杂网络研究中最基础、最初始的一步。事实上，正是通 过分析现实世界中网络数据得出它们的共性，才有了小世界网络和无标度网络的 提出。对更多的实际复杂网络数据分析可能发现其它新的共性，借此来构建新的 更符合实际网络特性的网络模型。很多研究者相继对各个不同领域的网络数据进 行了研究和分析如，文章 6 】中研究了电影演员合作网络数据，【7 9 】中研究了 科学家合作网络，【1 0 ，1 1 】研究了e m a i l 网络，【1 2 1 4 】研究了w d r l d - w i d e w e b “1 5 】 研究了论文引用网络，【1 6 】研究了语言学中单词一起出现所组成的网络，【1 7 1 研 究了生物系统的新陈代谢网络，【1 8 】研究了生物神经网络，【1 9 】研究t i n t e m e t ， 【2 0 ，2 1 研究了软件中的网络， 2 2 研究了电路网络，【2 3 】研究了巴西流行音乐网 络， 2 4 , 2 5 研究了网络的群落结构， 2 6 , 2 7 研究了网络的谱特征等等，现实网络的 研究还有很多，在此不一一列举。 2 复杂网络的建模研究 根据各种实际复杂网络数据的分析结果，可概括出它们的共同特征，以此为 基础，再结合研究者对实际网络形成机理的理解和解释，就可以构建具有和实际 网络有相同或类似性质的网络模型。除了最初的w a t t s - s t r o g a t z 小世界网络模型 和b a r a b a s i a l b e r t 无标度网络模型，研究者相继提出了很多网络模型。如，一 些研究者提出并研究了高维的小世界网络模型1 2 8 3 0 ，在 3 1 , 3 2 d p 作者提出并研 究了确定的小世界模型，在 3 3 - 3 6 1 d p 作者对b a 无标度网络模型进行了改进和推 广，提出了各种各样的无标度网络模型，如在 3 7 。3 8 1 d p 提出了节点带有适应度的 无标度网络模型，在【3 9 】中作者提出了种局部世界演化网络模型。【4 0 - 4 4 综述 了今年来文献中提出的各种复杂网络模型。 3 复杂网络动力学研究 通过把复杂网络看成动力学系统或在复杂网络中引入动力学单元，很多研究 者对复杂网络的动力学行为展开了研究。如，在文献 4 5 - 4 8 中作者研究了复杂动 态网络的同步和网络的鲁棒性问题，在 4 9 ，5 0 中作者分别研究了一个时延小世界 网络模型的混沌和分行动力学，在【5 1 】中作者研究了小世界中自组织临界现象， 在 5 2 】研究t d , 世界网络中的湍流，在 5 3 1 0 e 作者研究t d , 世界振荡器网络中的 振荡消失现象，在 5 4 1 中作者研究了小世界网络中的随机共振，在 5 5 ，5 6 d e 研究 了复杂网络的控制问题等等。在复杂网络动力学性质的研究中，网络的拓扑结构 如何影响网络的动力学性质是一个非常有意义的问题，也是一个研究热点问题。 4 复杂网络中发生的事件 还有一些科学家研究了复杂网络中发生的动态过程。在前面我们提到很多大 规模的复杂网络都具有小世界效应，也即是很多大规模的复杂网络在任意两点间 4 加反镄机制的复杂河络动力学 一般都存在一条相对网络规模来说很短的路径，但是能否很快找到这条路径和如 何找到是一个关键的问题。文献1 5 7 5 9 1 研究了复杂网络的搜索与导航问题。另外， 文献 6 0 6 7 研究了复杂网络中的病毒传播，在【6 6 】中作者研究了计算机病毒在网 络中的传播问题，在文献 6 8 1 q ，作者研究了复杂网络中的扩散过程。 5 复杂网络的应用问题 总体来说，由于复杂网络的研究尚处于起步阶段，对复杂网络理论应用的研 究相对来说还比较少，但是迄今为止，科学家们发现了很多复杂网络潜在的有意 义的应用。如前面提到过的，复杂网络的鲁棒性的研究成果可以应用到网络拓扑 设计中去，对网络的同步的研究有望在通信领域中发挥作用，对网络的搜索和导 航问题的研究可能在通信及计算机网络等的路由问题中有应用前景的同时对设 计更加有效的搜索引擎也有可能起到关键性的作用，对病毒传播网的研究对预防 和控制传染病及计算机病毒有重要的指导意义 6 9 】。此外，最近在文献 7 0 1 q b 作 者提出了把无标度网络模型应用到纠错编码中去，这也是一项十分有意义的应 用。可以预见，随着复杂网络领域研究成果的不断涌现，对这些成果的应用的研 究也将成为一个主要的方向。 1 3 复杂网络的研究意义 复杂网络的研究渗透到非常广泛的交叉学科，包括非线性科学、电路与系统、 计算机科学、控制理论、理论物理、数学、生物学、经济学、生态学等各个学科 领域。复杂网络的研究无论在理论上还是应用中都有重要的意义，一方面，对复 杂网络的深入研究可以使我们更好的了解和解释现实世界的复杂系统，从而了解 自然、了解我们所生存的现实世界是科学研究的最主要的目的之一；另一方面随 着对复杂网络研究的深入，我们可以应用理论研究成果到具体问题中去，如可以 设计出具有更好特征的实际网络或使网络处于对我们有利的状态，以及应用到其 它在上面提到的应用问题中，使得网络理论可以为我们所用。如今，复杂网络理 论不仅在电力网、通讯网、运输网、计算机网等技术性网络和基因网络、蛋白质 网络等生物网络的分析和设计中得以应用，而且也渗透到电路布图、模式识别、 统筹管理、场所选址等涉及网络优化问题中。值得注意的是，复杂网络理论不仅 被应用到自然科学，而且也被应用到社会科学中。例如：通过构建社会人与人的 关系网络模型去研究传染病在人群中的流行、谣言在社会中的扩散等等，以及深 一步去描述这种传播行为，揭示它的特性，寻找出对该行为进行有效控制的方法 等。所以复杂网络的研究有着非常重要的意义。 5 硕士学位论文 1 4 复杂网络研究面临的挑战 复杂网络是一个快速发展的新兴学科，虽然在这个领域已经取得了一些很好 的成果，但是复杂网络研究的各个方向上都还存在着许多很重要的但没有被研究 或者没有深入研究的问题，在这个领域做出新的重大的成果或者有重大的发现的 概率是比较高的。综合前人的研究，在复杂网络研究领域还有以下几个有挑战但 是非常重要的问题： 1 是否存在其它重要的统计分布特性，能让我们进一步洞察复杂网络? 这个问题答案几乎是必然的，目前发现的几个复杂网络的特征只是其中 的一个部分，可以预见，随着对实际网络数据的进一步统计分析，会发现更多的 复杂网络所具有的共性。 2 复杂网络动力学以及复杂网络中发生的动态过程 对于复杂网络动力学已经有了一些研究，但是还远远不够，目前研究的都是 一些理想化的简单情况，所使用的网络模型也很简单，对于一些复杂的情况的研 究还开展的不够。如网络信息传输中具有时延的情况、网络是时变的情况、同一 网络中不同节点具有不同动力学的情况和网络节点具有年龄效应的情况等等。 3 生物网络的演化规律 在技术网络等实际网络中，我们可以比较方便地研究网络形成的机制和演化 规律，但在生物网络中由于测量的难度、生物系统本身的极度复杂，使得对生物 网络的研究十分困难。如何设法定性、定量的研究生物网络的演化特征，并对其 有效建模是一个重要的问题。 4 复杂网络的理论框架 到目前为止，对复杂网络的研究方法和工具都是从其他学科中拿来的，比如 从统计物理、图论、计算机科学、动力系统等等学科方向，还没有其自己的一套 理论框架和研究方法。只有发展出属于复杂网络的自己的理论框架才能对网络的 研究更加深入、透彻、细致和系统。当然这也是最具挑战的一项工作。 6 加反馈机制的复杂网络动力学 2 1 1 图的概念 第二章复杂网络概述 2 1 图的基本概念 所谓j i l l ( g r a p h ) j 7 1 是指有序- - 元组( v ，e ，咖，其中v 非空称为顶点集( v e r t e x s e t ) ，e 称为边集( e d g es e t ) ，而妒是e 到v 中元素有序对或无序对簇v x v 的函数， 成为关联函数( i n c i d e n c ef u n c t i o n ) 。v 中元素成为顶点( v e r t e x x 或者点( p o i n t ) ) ，层中 元素称为边( e o g e ) ，伊刻画了边与顶点之问的关联关系。若v x v 中元素全是有序 对，则( y ，层，力成为有向 ( d i g r a p h ) ，记为d = ( d ) ，e c d ) ，) 。设p e ) ， 则存在x , y y ( d ) 和有序对工，y v x v 使得( 口) = o ，y ) 。口称为从x 到y 的有向 ( d i r e c t e de d g ef r o m x t o y ) 。x 称为口的起, 点( o r i g i n ) ，y 称为a 的终点 ( t e r m i n u s ) ，起点和终点统称为端点( e n d - v e r t i c e s ) 。设e e e ( g ) ，则存在毛y 矿( g ) 和无序对协力v x v 使( p ) = 力。由于无序对缸，力和o ，砖表示同一个元 素，所以通常简记( 力= x y 或y x ，p 称为连接x 和y i 的边( e d g ec o n n e c t i n g xa n d y ) 。 图2 1 图a 是l o 阶有向图，顶点集为 l ，2 ，3 4 ，5 ，6 , 7 ，8 , 9 ，1 0 ，边集为 l 一2 ，1 _ 3 ，1 叫2 _ 5 2 6 2 7 3 - + 6 争_ 7 争一8 ，“+ 9 ，7 9 ，8 - 1 0 ：图b 是6 阶无向图。顶点集为 l 2 , 3 , 4 ，5 ，6 ，边集为 1 3 ，1 4 ， 5 2 3 ，2 4 , 2 6 ，3 6 5 6 7 硕士学位论文 2 1 2 图的图示 通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表 示( 直线或曲线) 。这样画出的平面图形称为图的表示，如图2 1 所示。由于表示 顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示，比如 图2 2 和图2 1 的另一个等效图示： 屹警1 0 ，h 辫 图2 2 图的图形表示a图2 3 图的图形表示b 图的图示直观易懂，因此以后一般说到图，总是画出它的一个图示来表示。 2 1 3 图的表示 无论是对图进行数学运算还是用计算机对图进行处理，都需要一种形式化 的方法来表示。不同的系统抽象出来的图具有不同的特征，如有的图边的数量较 少，称为稀疏图；有的图边比较稠密，称为稠密图。为了运算的方便或者是节约 存储空间，不同的图可以用不同的形式来表示。主要介绍两种方式，即邻接矩阵 和关联矩阵。 图的邻接矩阵表示如下，嘞表示顶点哆与 ，之间的边的数量，如果是节点之间不 允许重边，则的取值为。或1 如果4 ( g ) 是无向图，则a ( g ) f f i 4 ( g ) 7 。邻接矩阵需要的 存储空间复杂度为o ( n 2 1 ，n 为节点数量。邻接矩阵适合表示稠密图，但是不适合表示稀 疏图。 么( g ) = a 1 1 a 2 1 a y l 8 a 1 2 1 2 2 引 加反馈机制的复杂网络动力学 图的关联矩阵表示如下，其中表示顶点咋在边勺中出现。在节点数量一 定的条件下，关联矩阵的表示占用的存储空间还与边的数量有关，其空间复杂度 为o ( n m ) ，其中为节点数量，m 为边的数量。关联矩阵表示稀疏图，但是不 适合表示稠密图。 m ( g ) = 2 2 1 直径与平均距离 2 2 基本参数 对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数 的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进 行的，因此有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将 有助于我们更好地理解当前复杂网络研究的物理意义。 在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大 传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与 平均距离。图g ( v ，e ) 的直径与平均距离可分别表为： d ( g ) = m 峰 如y ) ( 2 1 ) ( 6 32 志互姒五力 为了叙述方便，后文中使用盯( g ) 来代替有关( g ) 的讨论，其中 盯( g ) = v ( v 一1 ) 4 g ) 。 关于图直径和平均距离的研究可以追溯到半个世纪前，o r e 给出了无向图直 径一个漂亮的紧界【7 2 】，e n t r i n g c r , j a c k s o n , s l a t e r 和n g , t e h 分别就无向图和有向 图的情形给出了图平均距离粗糙但具有开创意义的下界1 7 3 ，之后p l e s n i k 给出了 平均距离只依赖于阶数和直径的下界【7 4 】。e n t r i n g c r 等人的结果可以作为该定理 的一个自然的推论给出。结合此定理与o r e 定理，可以得到只依赖于阶数和直径 9 硕士学位论文 的平均距离下界，该下界是目前已知的最好的下界。 o r e 通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图， 其证明手法是优美而繁复的。由于其构造中隐含了叱“力= 如0 ，工) 的条件，因 此无法直接推广到有向图的形式。显然，任何v 阶图都可以看作从完全无向图或 完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给 出o r e 定理的简单证明。 定理2 1 ：对任意无向( v , k ) 图g ，有： 1 c ( g ) k + 去( v k + 4 x v k 一1 ) ( 2 3 ) 二 其中似七) 图是指阶数为1 ，直径为k 的简单有限图。 证明：用q ( v , k ) 表示要得到无向( v ，k ) 图至少需要从完全图k 中移走的边的 数目，则对任意无向n 七) 图g ，有： 占( g ) ss ( 鼠) - , k v ，k ) ( 2 4 ) 令p = x o ， ，屯， 为g 中长为i 的最短路，由p 的最短性易知p 中两点而， 1 不相邻，名i l i - j i 1 。这就意味着至少有去七( 七一1 ) 条边必须从墨中移走以得到 二 图g 。同样由p 的最短性知，对于不在p 中的顶点工，若p 中两点耳，工，满足 i i - j i 2 ，n x 不能同时与薯，工，相邻，e p x 最多与p 中形如五，铂，氟：的三个顶 点相邻。换句话说，p 中至少有仲一2 ) 个点不与x 相邻。由于g 中不在p 上的顶 点数为( v k - i ) ，即有至少( v k 一1 ) 一2 ) 条边必须从k 中移去以得到g 。综 上可知： 1 r t ( v ，七) 七( 七一1 ) + ( ，一七一1 x 七一2 ) ( 2 5 ) 结合( 2 3 ) ( 2 4 ) l i p 得( 2 5 ) 式。 利用同样的分析方法，可以得到o r e 定理的有向图形式，证明略。 定理2 2 ：对任意强连通有向( v ，k ) 图g ，有： 占( g ) v ( 1 ，一七+ 1 ) + 妻( 七2 一七一4 ) ( 2 6 ) 下面两个定理将给出平均距离的下界，由于证明比较复杂，此处省略。 定理2 3 ：设g 为无向( v , k ) 图( 七2 ) ，若g 的规模为占，则有： 1 0 加反馈机制的复杂网络动力学 k 为偶 ( 2 7 ) 为奇 盯c62：2“v(，v一-1。，)-一：2七k+；lk。(k。一-，1，x。k七-一2：)，+1善(。，v-一七k一-1。xx七k：z一-。4k。-一：2，v)+。，竺：czs， 图的簇系数是衡量图的成团特性的参数。对于无向图g ( 矿，e ) ，记某顶点j 的邻点集合为4 ( 工) ，显然d ( 工) = i 彳( 工) i ，】页点工的簇系数被定义为它所有相邻节 点之间连边的数目占可能的最大连边数目的比傍j ，即： 啪) = 2 文q 钺砷x 赢) - 1 ) ( 2 9 ) 图g 的簇系数则被定义为所有顶点簇系数的平均值： c ( g ) 。志；c g ( 力 ( 2 1 0 ) 对于无向图g ( y ，e ) ，记度为忌的顶点数目为p ( 七) ，则p ( 七) = 簧若给出了图 g 的顶点度分布。 2 2 3 度关联( d e g r e ec o r r e l a t i o n ) 度关联是包括i n t e r n e t 在内的许多真实异质网络的一个重要特征 7 5 7 6 。它 描述了网络中任何一个节点的度与它的相连的节点的度之间的关联性质。研究发 现，在诸如i n t e m e t 和w w w 等的技术性网络中，度值大的节点倾向于与度小的 节点连接。这种性质被称为协调性度关联。相反，在演员网络等的社会网络中， 度值相同的节点有相对较大的连接趋势，这被视作非协调性度关联。 度关联属性通常采用p e r s o n 系数来定量地描述。在复杂网络中，p e r s o n 系数 的定义式为： 一i 项 妒 一 一 胎 耻 一 一 女 七 一 一 o l 一2 l 一2 + + 动 萄 一 一 耻 j 薹： 一 一 似 t 七 l 一3 1 3 狲 计 一 一 一 一 咖 咖 2 2 ，l_lj、-【 i 回 盯 硕士学位论文 ，- 差m 黔糕m 一 ， 。， ( z 2 + 皇2 ) 一i。 ( z + 毛) l 。 其中，矗和岛分别表示第i 边所连接的两个节点的度，m 是网络中的总边数。如 果r 0 ，表明网络具有正的度关联或协调度关联；而r 0 ，则表明网络具有负 的度关联或非协调度关联；如果，= 0 ，我们则可以称网络为中性网络。此外， 我们也可以通过直接观测“邻居节点平均度”的分布来定性地了解网络的度关联 性质。如果邻居平均度的值随节点度的增加而增长，此时可以认为网络具有协调 性度关联；如果邻居平均度的值随节点度的增加而降低，则可以说该网络是非协 调的；如果邻居平均度不依赖于节点的度，表明网络为中性的。 2 2 4 模块( m o d u l e ) 与模体( m o t i d 一般而言，模块是指物理上或功能上连接在一起的、共同完成一个相对独立 功能的一组节点 7 7 s o 。许多真实网络中都包含模块，例如社会网络中的一群朋 友或w w w 上主题相近的一组网站等。在工程系统中，高度模块化是一个基本的 设计要求。生物系统中更是突现模块性。例如，相对固定的蛋白质一蛋白质和蛋 白质- r n a 联合体( 物理模块) 就是许多基本生物功能的核心。 近期的研究表明，模体可能是复杂网络的基本模块。我们知道，与具有相同 规模和度分布的随机网络相比，许多真实网络的聚类系数要高得多。网络的高聚 类性表明网络在局部上可能包含各种具有高度连同性的模体( 或称子图 ( s u b g r a p h ) ) 设网络节点集合，是啪真子集，即，圪a ，屹a ，且匕c v ，k c v ； 若匕n = a ，则有厶= 吩) ，f ，k ，且厶c 爿。记= ， i i l i l 因此当p g 时，9 如i = 嘞，a u g a 为子集v p 、k 之间的关系数量，而p = g 时，i k 0 = 嘞，勺e 爿为子集内部的关系数量。对于一个有价社