（理论物理专业论文）加权网络及其复杂网络动力学.pdf

摘要 近年来，国内外掀起了研究复杂网络的热潮，许多来自物理、 数学、计算机领域的研究者都开始致力于复杂网络的研究。复杂网络 的研究以系统学的观点来看待真实系统，如i n t e m e t 网络、电力网、 新陈代谢网络等。本论文对加权复杂网络和复杂网络的动力学性质两 个方面进行了研究。这两方面的研究无论在理论上还是在实际应用中 都具有重要意义。现实世界中很多网络都是各个连接间具有不同权值 的加权网络，过去比较多研究的无权网络模型只是对复杂网络的一种 近似简化描述，加权网络模型则能够对实际复杂网络的动力学演化特 性提供更加真实的细致和全面的描述。因此，对加权网络建模研究的 重要意义是显而易见的。另外通过对复杂网络动力学性质的研究，一 方面可以使我们更好地了解和解释现实世界中复杂网络所呈现出来 的各种动力学现象，如网络中的疾病传播，网络的同步、振荡等；另 一方面我们可以将对复杂网络动力学性质研究的理论成果应用到具 体问题当中去，如可以设计出具有更好特性的实际网络或使网络处于 对我们有利的状态，使得网络理论可以为我们所用。 本文共分为四章。在第一章中，我们简单的介绍了研究复杂网 络的基本知识，其中包括复杂网络的基本模型以及描述复杂网络的几 个基本特征量。在第二章，我们主要研究了加权复杂网络，首先我们 介绍了加权网络的研究概况，以及前人的几个加权网络演化模型，并 在他们的基础上提出了一个新的加权演化模型。第三章中，我们介绍 了网络上的几个动力学过程，包括网络中的疾病传播，网络的同步和 网络的鲁棒性。第四章是对本文工作的总结以及复杂网络领域研究的 展望。 关键词：复杂网络、无标度网络、加权网络模型、幂律分布、 时延 a b s t r a c t t h er e c e n td e c a d eh a sw i t n e s s e dt h eb i r t ho fan e wm o v e m e n to f i n t e r e s ta n dr e s e a r c hc o m p l e xn e t w o r k t h er e s e a r c h e r si n p h y s i c s ， m a t h e m a t i c sa n dc o m p u t e ra l ld e d i c a t et ot h es t u d yo fc o m p l e xn e t w o r k i t sf r o mt h ep o i n to fs y s t e m a t i cv i e wt os t u d yr e a ls y s t e m s ，s u c ha st h e i n t e r a c t ，p o w e rg r i dn e t w o r k sa n dt e l e p h o n ec a l ln e t w o r k s ，e t c i nt h i s d i s s e r t a t i o nw es t u d yt h em o d e l i n go fw e i g h t e dc o m p l e xn e t w o r k sa sw e l l a st h ed y n a m i cp r o p e r t i e so fc o m p l e xn e t w o r k s t h e s es t u d i e sa r ev e r y i m p o r t a n tb o t hi nt h e o r ya n di np r a c t i c a la p p l i c a t i o n s m a n yr e a l - w o r l d n e t w o r k sa r ew e i g h t e dn e t w o r k sw i t hd i f f e r e n tw e i g h t si n d i f f e r e n t c o n n e c t i o n s t h eu n w e i g h t e dn e t w o r km o d e l ss t u d i e di nm a n ye x i s t i n g l i t e r a t u r e sa r es i m p l i f i e dm o d e l i n go fr e a ln e t w o r k s ，w h i l ew e i g h t e d n e t w o r km o d e l sc a n p r o v i d e m o r er e a l i s t i ca n dc o m p r e h e n s i v e d e s c r i p t i o n so fr e a ln e t w o r k s s o ，t h ei m p o r t a n c eo ft h em o d e l l i n go f w e i g h t e dn e t w o r k si sc l e a r l ys e l f - e v i d e n t b ys t u d y i n g t h ed y n a m i c p r o p e r t i e so fc o m p l e xn e t w o r k s ，o nt h eo n eh a n d ，w ec a n u n d e r s t a n da n d e x p l a i nt h ed y n a m i cp r o p e r t i e sp r e s e n t e di nr e a l w o r l dn e t w o r k s ，s u c ha s ， e p i d e m i cs p r e a di nn e t w o r k , s y n c h r o n i z a t i o na n do s c i l l a t i o np h e n i m e n a ； a n do nt h eo t h e rh a n d ，w ec a na p p l yt h e s et h e o r e t i c a lr e s u l t st os o m e p r a c t i c a la p p l i c a t i o n s f o re x a m p l e ，w ec a na p p l y t h e s er e s u l t st ot h e d e s i g no f r e a ln e t w o r k st oa c h i e v eg o o dp e r f o r m a n c eo rt ot h ec o n t r o lo f r e a ln e t w o r k st oa c h i e v es o m ed e s i r a b l en e t w o r kb e h a v i o r st h a tb e n e f i t t h en e 扛v o r k s 。 t h et h e s i sc o n s i s t so ff o u rc h a p t e r s i nc h a p t e ro n e ，w ei n t r o d u c e d s o m ek n o w l e d g ea b o u tn e t w o r ki n c l u d i n gt h et y p i c a lm o d e l so fn e t w o r k a n dt h ep a r a m e t e rt od e s c r i b ec o m p l e xn e t w o r k i nc h a p t e rt w o ，w es t u d y t h ew e i g h t e dn e t w o r k , a tf i r s tw eg i v eab r i e f l yr e v i e wt ot h ew e i g h t e d n e t 、】l ，o r ka n ds o m eb a s i cm o d e l so fi t t h e nw ep u tf o r w a r dan e wm o d e l t o g e n e r a t ew e i g h t e d n e t w o r k a n dw ei n t r o d u c e s o m ed y n a m i c a l p r o c e s s e s o i ln e t w o r ki n c h a p t e r t h r e e t h e na tl a s t 职p r e s e n t sa c o n c l u s i o nf o ro u rw o r ka n ds o m ep r o s p e c t sf o rf u t u r ew o r k s i nt h i sf i e l d k e yw o r d s ：c o m p l e xn e t w o r k ，s c a l e f r e en e t w o r k , w e i g h t e d n e t w o r k m o d e l ，p o w e r - l a wd i s t r i b u t i o n ，t i m e - d e l a y v 硕士学位论文 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中己经注明引用的内容外，本论文不含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人 和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 、。 一 学位论文作者签名： 己b 逸氓川年6 月，中日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 、。( 请在以上相应方框内打“”) 作者签名：、7 每甚1 矾日期：讥诃年6 月f 牛日 导师签名：方员缸 日期：力叮年彭月争日“ 加权网络及其复杂网络动力学 第一章复杂网络研究概述 1 1 复杂网络及其发展 1 1 1 引言 复杂网络的研究近年来受到科学和工程各个领域研究人员的广 泛关注，己经成为近年来的一个研究热点【1 4 】。网络由一些基本单元 ( 通常我们称之为节点或顶点) 和它们之间的连接( 通常我们称之为边 或连接) 所组成。网络的复杂性来自于网络的结构复杂性、连接复杂 性、演化复杂性、时空复杂性等各个方面。毫无疑问，现实世界中很 多系统都可以用复杂网络模型来表示【5 6 】。例如，i n t e r a c t 是路由器或 域组成的网络；万维网( w w w ) 是由网页组成的网络；大脑是由神经元 组成的网络：一个社会组织是由人组成的网络。此外常见的复杂网络 还有通信网络、电网、蛋白质问交互组成的网络、大规模电路与系统 ( 节点是电子元件，边是它们之间的连线) 、公路网、铁路网、航空网， 科研合作网( 节点是研究者，边是研究者合作的论文) 等。图1 - 1 一图 1 3 是一些典型的复杂网络图。 图1 1i n t e r n e t 和w w w 网络结构示意图 硕士学位论文 由于复杂网络的无处不在性，所以我们有必要对复杂网络的各种 特性进行广泛而深入研究，主要的课题有：网络的连接结构、各 种网络是否存在某些共性、网络模型、网络结构对网络动力学的 影响、网络的鲁棒性以及网络的设计等【7 】。传统上对网络的研究 一般采用数学上的图论的方法。但经典图论所考虑的一般是规则 图，在上个世纪5 0 年代末6 0 年代初，两位匈牙利数学家p a u l e r d o s 和a l f r e d r e n y i ( e r ) 在图论领域做出了一个重要突破，即在文献中 提出的随机图理论 8 】。他们用随机图来描述网络的拓扑结构，这 为复杂网络的研究奠定了一个数学理论基础。用随机图理论对复 杂网络的研究持续了4 0 年，直到今天仍有人在做这方面的研究。 但随机图理论是否能准确地描述现实世界中的网络呢? 大量的观 察结果告诉我们：现实世界中的网络既非完全规则亦非完全随 机。e r 随机图理论虽然不能准确地描述现实世界中的网络，但 却能统治这个领域这么多年，主要还是由于过去我们缺乏对现实 世界中网络数据的分析能力和对现实世界网络拓扑结构的准确 认识。 图1 - 2 一个清水湖中各个种群间捕杀猎食网络 加权网络及其复杂网络动力学 图i - 3 电路连线网络 但近年来事情发生了变化，由于科学技术领域，特别是r r 领域 的高速发展，使我们得的可供我们刻画现实世界网络特征的数据 越来越多，加之超级计算机的发展为我们提供了强大的计算和数 据分析能力，以及学科之间的相互交叉和融合趋势在不断加强， 使得人们有能力在对各种不同类型网络的数据分析的基础上，揭 示复杂动力网络的一些共有的特征和性质，从而激发起了人们以 理论、仿真和实际数据验证三种手段研究复杂网络的浓厚兴趣。 以此为契机，经过在这一研究方向上不懈的探索和努力，最近在 复杂网络研究领域中取得了两项重要的发现：大多数复杂网络都具 有小世界( s m a l l - w o r l d ) 效应和标度无关( s c a l e f r e e ) 特性。 小世界的概念从字面上的意思是说尽管网络很大，但通常在网 络的任意两个节点间都有一条相对于网络规模来讲是很短的路 径。我们可能经常遇到这样的情形，当你遇到一个陌生人的时候， 经过交谈你却发现你们有共同的好朋友( 他是你朋友的朋友) ，于是 双方都会发出这样的惊叹“世界真小”。小世界的另_ 个代名词是 所谓的“六度分离”( s i xd e g r e eo f s e p a r a t i o n ) 【9 】。1 9 6 7 年社会心理 硕士学位论文 学家s t a n l e y m i l g r a m 断言在大多数情况下两个美国人之间一般存在 一条不超过6 的“认识”路长( a l j 通过一个人与另一个人之间互相 认识来构成的路径，在任意两个美国人之间该路径长度一般不超 过6 。1 9 9 8 年，为了描述从规则格子到随机图之间的转变，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 率先发现在很多大规模的复杂网络中节 点的度呈现一种幂律( p o w e r l a w ) 分布【9 】，该类网络被称为标度无 关( s c a l e f r e e ) 网络。 小世界效应和标度无关特性的发现是复杂网络研究领域的重 要进展。之后，在上述两项重要发现的推动下人们又相继提出了 多种复杂网络模型，并研究了其相关性质，从而掀起了一股研究 复杂网络的热潮。 1 1 2 复杂网络中的一些基本概念 尽管近年来提出了许多刻画和度量网络的概念。但其中有三 个概念发挥了重要作用，它们是：平均路长、聚类系数和度分布。 事实上最初w a t t s 和s t r o g a t z 就是试图构造一种具有小的平均路长 ( 与随机网络类似) 和较大的聚类系数( 与规则网络类似) 的网络，循 此途径最后得到了小世界网络模型。标度无关网络的提出是由于 观察到许多大规模网络的节点的度呈现一种幂律分布。所以说这 三个概念在复杂网络的奠基性研究中起到了至关重要的作用。并 且在后来的复杂网络研究中它们也扮演了重要的角色。因此我们 下面先介绍一下这些概念。 加权网络及其复杂网络动力学 l 、平均路长( a v e r a g ep a t hl e n g t h ) 在一个网络中，两个节点j 和_ ，之间的距离d ：定义为连接i 和 _ ，的最短路径所包含的边的数目。网络中任意两个节点间的距离的 最大值称为网络的真径d 。一个网络的平均路尽工定义为网络中任 意两个点间距离的平均值。一个有趣的发现是在很多大规模复杂 网络中，平均路长相对都很小，即使在节点间连接很稀疏的网络 中情况也是如此。这个“小”也就是所谓的小世界效应，也就是 小世界网络名称的来源。 2 、聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 在朋友网络中，经常会遇到这样的现象，你朋友的朋友还是你 的朋友，或者换句话说，你的两个朋友，他们之问也是朋友。这 种特性被称为聚类特性，而聚类系数就是用来衡量大家的朋友之 间互相还是朋友的比率有多大的。更确切地说，聚类系数可以由 下面的方式定义。假设节点f 连接着t 条边，并通过他们连接到t 个 其它的节点。这些节点都是节点f 的邻接节点。易知最多可能存在 有t ( 七f d 2 条边在这些邻接节点之间，此时这些邻接节点之间是 全部互相连接的。而实际在这些节点之间存在的边的数目 置s 七j ( 毛一d 2 ，节点f 的聚类系数c ，就定义为互毛( 毛一1 ) 2 的比值 整个网络的聚类系数c 定义为网络中所有节点的聚类系数的均值， 即： c = 丢军c ( 1 - 1 ) 在具有n 个节点连接概率为p 的随机网络中( 通常p 1 ， 硕士学位论文 p l n ) c p ，在全局耦合网络中c = i 。而在实际网络中c 通常远大 于1 n ，但却小于1 。所以从这个意义上讲，随机网络和全局耦合 网络都不能很好地描述现实世界的网络。 3 、度分布( d e g r e ed i s t r i b u t i o n ) p o h 隧o ad t t t i d b u t j o f l 籼w 翱嘞wd i t l “o 嚣 图i - 4 左图为美国高速公路网，其中节点为城市，边为连接它们的高速公路 节点的度服从p o i s s o n 分布。右图为航空线路网络，节点为机场，边为 航线。节点的度服从幂律分布。 刻画一个节点的特性的可能最简单同时也是最重要的概念就 是度。一个节点i 的度k ，定义为它的连接( 边) 的数目。也就是说， 一个节点的度越大，那么他在网络中的重要性越高。一个网络中 节点度的分布可以用一个分布函数p ( 七) 来刻画，p ( i ) 定义为一个随 机选择的节点恰好具有k 条边的概率。易知，全局耦合网络的度分 布很简单，就是一个d e l t a 函数，因为在全局耦合网络中所有节点 都和其它所有节点连接，每个节点所连接的边数都相等。随机网 加权网络及其复杂网络动力学 络和小世界网络的度为泊松分布。而通过对许多实际的大规模网 络的统计分析发现，大多数实际网络的度呈幂律分布，也就是分 布函数的形式为p ( i ) 一k - ，。服从这种分布的网络我们称之为无标 度网络。我们可以通过比较美国的高速公路网络和航空线路网络 来直观地感受度分布为p o i s a o n 分布和幂律分布的网络的差别，见 图1 - 4 。 1 1 3 复杂网络模型 对实际网络的上述特性的统计度量只是复杂网络研究的第一 步。下一步就是构造出具有在这些特性上和实际网络相近的网络 模型来，以便我们可以在这些网络模型的基础上进一步展开研究。 1 、随机图模型 如前所述，积随机图理论是4 0 多年前由e r d o s 和r e n y i 提出。 假设网络有n 个节点，我们以概率p 来连接一对随机选定的节点。 这样就生成了一个具有n 个节点和大约p n ( n 一1 ) 2 条边的随机图。 随机图网络的平均度是 = - p ( n 1 ) ，度的分布呈p o i s s o n 分布【1 0 】。 平均路长l i n n 较小，具有典型的小世界特性。但e r 随机图 的聚类系数c 1 ，而实际网络的聚类系数通常远大于这个数值。 2 、小世界网络模型 通过上面的分析我们看到在随机图网络中具有小的平均路 长，但却不具有实际网络的聚类特性，聚类系数过小。而实际 网络通常是既具有某种规则性，又有一些随机性 1 1 1 3 l 。例如， 人们通常都认识自己的邻居和住在附近的人，也有可能认识住 硕士学位论文 得很远处的某些人。为了描述从规则格子到随机网络之间的转 变，1 9 9 8 年w a r s 和s 仃o g a t z 引入了一种很有趣的所谓的小世界网 络模型，我们称之为w s 小世界模型。w s 小世界网络模型可以 通过如下的算法形成：” ( 1 ) 从规则开始：从一个具有n 个节点，每个节点具有k 个近 邻( k 为偶数，每边比个) 的最近邻网络开始。为了使网 络连接具有稀疏性，要满足n k 。 ( 2 ) 随机化：以概率p “重新连接”每条边，重新连接在这里 的意思是把一条边的一端从一个节点转移到在网络中 随机选取的另一个节点上，并保证节点没有自连接以及 两个节点间没有重复连接。这样网络中就产生了p n k 2 条“长距离连接”( 或称“非局部连接”、“捷径”) 。通 过变动p ，我们可以产生从规则格子( p = o ) 到随机网络 ( p = 1 ) 的转变。 图1 - 5 小世界网络中c ( p ) 和l ( p ) 随p 的变化 研究发现，对于一个较小的重新连接概率p ，聚类系数 改变很小，而平均路长却减小很快。图1 - 5 示出了c ( p y c ( o ) 和 加权网络及其复杂网络动力学 l ( p y l c o ) 随概率p 的变化曲线。这样通过一个小概率的重新连 接，我们就可以生成一个具有较大聚类系数和很小的平均路 长的小世界网络模型。小世界网络的度分布和e r 随机图一 样也是服从p o i s s o n 分布。 3 、无标度网络模型 上述网络模型中规则网络的度分布为d e l t a 函数，因为所有的 网络节点都有相同的连接数。e r 随机图网络和小世界网络的度分 布都是p o i s s o n 分布。该分布在度的均值处有一个峰值，在两侧呈 指数衰减，这样的网络也被叫做指数网络( e x p o n e n t i a l n e t w o r k s ) 。而 最近研究发现，实际的很多大规模复杂网络的度分布都服从幂律 分布。在图1 - 6 中我们给出了一个典型的具有幂律度分布的网络 模型。 图1 6 一个典型的具有幂律度分布的网络一蛋白质交互网络 为了解释这种幂律分布，b a r a b a s i 和a l b e r t a ) 提出了无标度网 络模型。毋a ) 无标度网络模型的演化生成主要有两个要点：增长 ( g r o w t h ) 和偏好性连接( p r e f e r e m i a l a t t a e h m e n 0 。他们认为其它大多数 9 硕士学位论文 复杂网络模型都忽略了这两点。首先，大多数网络都是开放的， 不断有新的节点加入的，例如，在w w w 中不断有新的网页加入， 在科研合作网络中不断的有新的研究者加入到某领域的研究中。 但规则网络、e r 随机图网络和小世界网络等网络模型却是静态的 网络模型，他们考虑的都是具有固定不变节点数目的网络。另外， e r 随机图网络和小世界网络模型中考虑加入连接和重新连接是 等概率一致分布的。但现实中很多网络却并非如此，例如，在 w w w 中，新加入的网页或网站更愿意连接到已经存在的点击率 高的著名站点上，在科研合作网中，新加入的研究者更愿意与己 经在该领域有影响力的已成名的研究者合作。这种偏好性会导致 所谓的“富有者会更富( r i c h g e t s r i c h e r ) ”的现象。b a 无标度网络模 型包含了增长和偏好性连接，在b a 网络模型当中，不断地有新的 节点加入，新加入的节点连接到具有连接数越大的节点的概率越 高。b a 无标度网络模型的生成算法为： ( 1 ) 增长：初始时为个节点，在每步增加一个新的节点，该节点 连接到网络中m m 。个已存在的节点上。 ( 2 ) 偏好性连接：当在网络中选择新增加的节点所要连接的m 个 节点时，我们根据概率n 来选择，假设第i 个节点此时的度 为七；，那么该节点被选中的概率定义为 l - i ( k , ) 2 轰 ( 1 - 2 ) 数据仿真发现该模型生成的网络的度分布确实为幂律分布，很好 的解释了现实复杂系统度幂律分布的微观生成机制。 加权网络及其复杂网络动力学 1 2 复杂网络的研究意义及其挑战 复杂网络的研究涉及广泛的交叉学科，其中包括复杂性科学、非 线性科学、电路与系统、计算机科学、控制理论、理论物理、数学、 生物学等各个学科领域。为什么对复杂网络的研究会引起各个学科领 域的广泛兴趣呢? 因为对复杂网络的研究无论在理论上还是在应用中 都有重要意义，一方面对复杂网络的深入研究可以使我们更好地了解 和解释现实世界的复杂网络，而了解自然、了解我们所生存的现实世 界是科学研究的最主要目的之一；另一方面随着对复杂网络研究的深 入，我们可以应用理论研究成果到具体问题当中去，如可以设计出具 有更好特性的实际网络或使网络处于对我们有利的状态，以及应用到 其它在上面所提到的应用问题中，使得网络理论可以为我们所用，所 以对复杂网络的研究是有重要意义的 1 4 1 6 1 。 如在i n t e m e t 这个高度复杂的实际网络中，应用复杂网络理论到其 研究中就具有重要意义。我们可以根据复杂网络理论对其性质进行研 究，解释发生在其中的一些重要现象和性质，如网络拓扑如何生成、 i n t e m e t 建模、网络的鲁棒性与脆弱性、网络中发生的振荡现象等等 1 7 ，1 8 】；也可以将一些复杂网络的理论研究成果应用到其中，如可以 根据复杂网络理论设计一具有更好性质的网络拓扑、可以根据复杂网 络理论进行拥塞控制、可以根据复杂网络理论对i n t e m e t 中计算机病毒 的传播进行控制、可以根据复杂网络理论设计路由算法等等。 复杂网络是一个快速发展的新兴学科，虽然在这个领域已经取得 了一些很好的成果，但在复杂网络研究的各个方向上都还存在着许多 l l 硕_ 上学位论文 很重要的但没有被研究或没有被很好地研究的问题，在这个领域有新 的重要发现和作出重要成果的几率是比较高的。在复杂网络领域至少 有以下几个还没有开展或还没有被充分研究但非常重要的问题： 1 、随着对实际网络数据的进一步统计分析，会发现更多的复杂网络 所具有的共性。所以，对实际网络的数据进行进一步分析是非常重要 的问题，也是随时都有可能有重要发现的方向。 2 、对于复杂网络动力学己经有了一些研究，但还远远不够，目前研 究的都还都是一些理想化的简单情况，所使用的网络模型也比较简 单。对于一些复杂的情况的研究还开展的不够，如网络信息传输中具 有时延的情况，网络是时变的情况、同一网络中不同节点具有不同动 力学的情况、网络节点具有年龄效应的情况等等 1 9 】。对于复杂网络 中发生的动态过程也是如此，一些复杂的情况，如在病毒传播中网络 时变对传播的影响、网络中具有多个病毒的情况、病毒传播以及发作 等存在时延的情况等都没有很好地开展研究2 0 2 2 。 3 、目前涉及网络动力学的研究大多都是对网络拓扑如何影响整个网 络动力学以及动态过程的研究。反过来，网络的拓扑如何受网络节点 动力学或动态过程的影响也同样是非常有趣的问题。在很多情况下网 络节点动力学会影响网络的拓扑结构，如在神经网络中，两个神经元 的状态会直接影响两个神经元之间的突触连接：同样网络中发生的动 态过程有时也会影响网络拓扑，如计算机病毒在计算机网络中传播会 使某些计算机( 节点) 瘫痪，生物病毒在种群中传播会造成某些宿主节 点死亡，这些都会影响网络的拓扑结构，并进而影响网络的性质，如 加权网络及其复杂网络动力学 稳定性，鲁棒性等。 4 、现有文献中的大多数研究都是针对无权、无向网络的，但现实世 界中很多网络都是各个连接间具有不同权值的加权网络或各个连接 具有方向的网络，过去比较多研究的无权网络只是对复杂网络的一种 近似简化描述，加权、有向网络则能够对实际复杂网络的动力学演化 特性提供更加真实的细致和全面的描述。因此，对加权和有向网络的 研究的重要意义是显而易见的。该方向上的有待解决的问题包括实际 加权和有向网络的统计特性分析，建模，以及进一步研究其动力学特 性等。 5 、具有不同特性的网络之间的交互问题 多个不同网络之间有时是存在交互连接的，也就构成了“网络的 网络” 2 3 1 。如在如t e r 嘣中，不同类型的网络彼此连接，通过共同的 协议进行通信；在生物系统中基因网络、蛋白质网络、代谢网络项目 连接并相互作用；在交通系统中，公路网、铁路网、航空网相互连接。 那么如何刻画这种网络的网络、以及进一步地如何建模、各个网络之 问如何相互影响都是需要解决的问题。 1 3 本文结构安排 本章针对本文工作的领域复杂网络作一概要性的背景及研究动 态的介绍。文章结构安排如下： 在第二章中分析了一些实际网络的权值的分布情况，介绍了几种 典型的加权演化复杂网络模型，并在前人的基础上我们提出了一种新 硕士学位论文 的加权演化复杂网络模型 在第三章中介绍了复杂网络的动力学性质，先研究了网络上的信 息和疾病传播问题，之后介绍了网络的同步问题。 望。 在第四章中将对全文进行总结，并提出一些今后进一步工作的展 加权网络及其复杂网络动力学 第二章加权网络模型 2 1 引言 自从w a t t s 和s t r o g a l z 关于小世界网络和b a r a b a s i 和a l b e r t 关于无标 度网络的开创性工作发表以来1 9 , 2 3 ，在科学与工程各个领域掀起了 关于复杂网络研究的热潮。但到目前为止，大多数研究工作都是关于 连接无加权值的网络的，在所考虑的网络模型中，只有两种可能：节 点问有连接或者无连接。如果有连接则连接强度都为固定值1 ，无连 接则为0 。但在很多实际网络中，网络各个节点之间是具有不同权值 的，或者说耦合的强度是不同的。如在神经网络中，不同神经元之间 通常具有不同的连接权值；在科研合作网络中，各个研究者( 节点) 之间 合作的论文数量( 连接权值) 是不同的；在i n t 皓m c t 或通信网络中，各个连 接的流量也是不同的；在航空、铁路、公路网络中，各个节点之间的 客流量是不同的；在朋友网络中，人与人之间的关系紧密程度也是不 同的 2 4 2 6 。显然，这些网络用各个连接间具有不同权值的加权网络 模型来描述更适合。而过去比较多研究的无权网络只是对复杂网络的 一种近似简化描述，加权网络则能够对实际复杂网络的动力学演化特 性提供更加真实的细致和全面的描述。 目前关于对加权复杂网络的研究还比较少。首先，根据事物发展 的规律，我们对任何问题的研究都是从简单到复杂逐步地进行的，对 复杂网络的研究也是如此，不加权的网络模型中只需关心网络的连接 拓扑，显然要比加权网络简单得多。复杂网络的研究当前还只处于起 步阶段，在研究才起步时只考虑网络的某些特性，考虑简化的模型对 硕士学位论文 研究工作的开展是有利的，这也是各个学科发展过程中通常所采用的 策略。此外，关于复杂网络权值的数据和信息的获得要比网络的连接 拓扑的数据和信息的获得困难一些，也是造成加权复杂网络研究相对 迟缓的一个原因。比如，人与人之间的关系紧密程度，并没有一个既 有的权重来衡量。一方面，缺乏给网络中边定义权重的一般方法，另 一方面考虑权重后，权重又是怎么影响网络的性质、结构和效率等问 题也没有合理科学的定义。因此，对这些问题进行更深一步的探讨具 有重要的意义。 科学家合作网和国际航空网络是研究加权网络性质的两个十分 重要的实例。科学家经过大量数据的分析，发现在很多复杂网络中权 值的分布也是服从幂律( p o w e r 1 a w ) 分布的【2 5 】。接着b a r r a t 等人又发现 在复杂网络中网络节点的强度也服从幂律分布。这样，在复杂网络领 域现在发现的关于网络拓扑结构和权值信息就至少有了三个幂律分 布。这些研究对于理解实际网络的性质非常重要，但是到目前为止， 人们对于复杂加权网络的结构性质及其形成机制的认识和理解可以 说还远远不够。 在本章中，我们开展了有关复杂加权网络的研究，并且提出了一 种新的加权网络演化模型，对加权网络的形成机制具有一定的指导意 义。 2 2 几种典型的加权网络演化模型 在本节，我们介绍了几种典型的加权网络演化模型，并在这些工 加权网络及其复杂网络动力学 作的基础上提出一种新的加权网络模型。 1 无标度加权网络模型 2 0 0 1 年y o o k 和b a r a b a s i 等人提出了一种类似于b a 模型的 加权网络生成模型其定义如t z 7 i ： ( 1 ) 初始网络中假设含有个孤立的点，在每一个时间步加 入一个新的点到网络中去。并使新加入的点与m 个已经 存在的点连接( 肘s m 0 ) 。 ( 2 ) 新加入的点与网络中已经存在的点的连接不是等概率 的，而是以一种择优的方式选择与自己连接的点。新节 点与节点i 连接的概率： n 。：= 生- 2 j 求和遍及网络中所以已经存在的节点。 ( 3 ) 新节点与已存在节点之间的每一条连接，h f 被赋予一 定的权重，权重的多少取决于被连接节点i 的度t 嘞2 隶 q 2 ) 求和遍及与新节点j 连接的m 个已存在节点，并且为了 简单考虑假设所有这些新建连接的权重之和为1 ，即 ， 5 l 无标度加权网络模型( w s f 模型) 的结构和b a 模型的结构是 一致的，展现出幂指数形式的度分布：p ( 七) = 矿。之后y o o k 等人 还研究了无择优连接机制的加权网络生成模型，即所谓的加权指 硕士学位论文 数型网络演化模型( w e 模型) ，在该模型中新加入的点已等概率的 方式与网络中已存在的点相连接，其网络度分布呈现出指数形式： 尸( 膏) = ( e m ) e 4 “。在二元网络中，节点的重要性主要取决于该节点 的度，所以在考虑加权网络时，节点的重要性可以通过节点的总 权重来衡量。节点的总权重定义为与该节点连接的所有边的权重 之和，即w t = b 。大量的数值模拟表明，在以上两个模型中都 展现出稳定的边权分布，如图2 - 1 所示，其边权分布都展示出一个 尖峰形状，并且其尾部都以指数形式衰减。 y o o k 等人还研究了k x t ) 和( f ) 之间的定量关系。他们发现， 对于w e 模型，置( f ) 和( f ) 近似的满足以下关系： w i g ) t ( f ) 一m l n i n t + c ( 2 3 ) 而对于w s f 模型，t p ) 和m ( ，) 则近似的满足以下关系： 咄m 一詈( m 剥2 + 争m m + 一 c 2 4 ， 芝 图2 1 加权网络的权重分布：( a ) w e 模型；( b ) w s f 模型，其中m = 2 ，不同符号对 应不同规模的网络：n = 1 0 3 ( o ) ，1 0 4 ( 口) ，1 0 5 ( o ) ，1 0 6 “) 。 加权网络及其复杂网络动力学 这些解析结果表明，虽然模拟结果显示t ( f ) 和m ( f ) 的斜率有所不 同，但是并不代表它们是两种截然不同的标度行为。它们之间存 在着一种关联。并且随着时间的演化k , ( t ) t f l l w , ( t ) 的标度行为将趋于 一致。如图2 2 ： i i 绷绷蝴蝴 f 图2 - 2 网络节点度t ( ，) 和节点权重嵋( f ) 之问的定量关系：( a ) w e 模型( b ) w s f 模型 在w s f 模型中，节点的度分布和节点的权重分布都显示出幂指数 的形式。这一性质在真实的加权网络的实验中得到了证实 2 8 ，2 9 。 因此w s f 模型已经成为我们理解和研究真实加权网络的宏观统计 性质及其演化规律的一个基本模型。 2 b b v 模型 前面的w s f 模型中边权和节点的总权重都取决于节点的度， 然而我们知道在加权网络中节点的权重更能反映节点的性质。而 且w s f 模型中网络的边权是静态的，也就是说网络中边的权重在 初始时刻已经给定，而且随着网络规模的增大，边权没有任何变 化。这与实际系统中的情况有很大的差异，比如在航空网络中随 着航空网络的增大，各条航线上的乘客量也会有相应的增加，在 1 9 硕士学位论文 加权网络中就应表现为边权的增加。因此2 0 0 4 年，b a r r a t 等人提出 了一个基于节点强度的优先连接机制的加权演化网络模型，其网 络模型如下 3 0 】： ( 1 ) 初始网络中假设含有m 0 个孤立的点，在每一个时间步加 入一个新的点到网络中去。并使新加入的点与m 个已经 存在的点连接( m m 0 ) 。 ( 2 ) 新节点以择优连接的方式与已存在的节点连接：新节点 选择与节点i 连接的概率取决于节点的i 的总权重+ 置，即 队2 参 q 5 其中岛= ，代表与节点i 的所有边的权重的总和。 j v i ) 上式中的求和遍及网络中已存在的所有节点。 ( 3 ) 假定没一条新连接的边的权重都为w o ，并且新边的加入 将使得与接受这条边的节点相连的每条边的权重都有所 变化。具体每条边增加的权重可由以下关系式确定： 一十d 蛳。j = 6 鉴 。 曼 ( 2 6 ) ( 2 7 ) 其中假设j 为常量。 在这个加权演化网络模型中，网络拓扑结构和网络中节点与 边的权重的演化都取决于节点的总权重( 即节点的强度) 。更为 重要的是，在该模型中网络中节点的权重并不是一成不变的，而 是随着网络规模的不断增大而增加的。其增加的量也与其本身的 2 0 加权网络及其复杂网络动力学 强度有关，这些演化规则非常符合实际网络的演化规律。同时通 过改变参数j 的值，可以改变网络权重的演化，最终导致网络的 不同宏观性质。 b a h a t 等人通过数值模拟和解析计算发现该模型生成的网 络节点总权重s , ( t ) 和边i r w e ( t ) 随时间的演化都服从幂律【3 l 】： 焉( f ) ，( f ) 广；其中口= ( 1 + 2 刃“2 + 2 回，b = 艿( 1 + 占) ，如图2 - 3 所 示。 另外，b 。r r a t 等人还研究了该网络节点总权重分布以s ) 和边权 分布p ( w ) ，发现它们也服从幂律分布：j p ( s ) s 一，p ( w ) - w 一； c o ) 图2 - 3 网络节点权重( a ) t ( f ) 和边权c o ) w o ( t ) 随时问的演化 2 l 硕j _ 学位论文 其中y = ( 4 j + 3 ) “2 j + 1 ) ，o r = 2 + ( z e r ) ，女口图2 4 所示。 图2 - 4 网络节点总权重分布p ( s ) 和边权分布p ( w ) ，插图分别显示了幂指数 ，与参数万的关系以及幂指数口与参数j 的关系。 值得一提的是，节点总权重置和节点度t 之间也存在着简单 的正比关联，如图2 5 所示。而且当参数万= 0 时，该模型实际上 与b a 模型是一致的。网络度分布肯定服从幂律分布。 图2 - 5 嘲络节点平均总权重s 和节点平均度度k 之间的线性关系 上面的分析表明，b b v 模型所生成的网络同时展现出具有幂 律分布的度分布，边权分布和节点总权重( 节点强度) 分布。这 加权网络及其复杂网络动力学 一模型为许多真实系统所呈现出的无标度的多样性提供了一个 非常合理的解释。同时通过调节参数j ，可以得到具有不同宏观 统计性质的加权网络。 3 相互选择加权网络模型 、 由前面的内容可知，b b v 模型所生成的加权网络同时展 现出具有幂律分布的度分布，边权分布和节点总权重( 节点 强度) 分布。在科学家合作网和其它的一些社会网络中，在 科学界影响大或者说社会上名声大的人很容易相互产生联 系( 比如两个著名科学家合作发表论文) 。然而在某些技术 网络和生物网络中情况却恰恰相反，在网络中影响大的节点 ( 度值大的节点) 更偏向于与连接一些度值很小的节点。一 前面的两个模型给我们的一个印象就是：网络中已经存 在的节点被动地被新加入的点选择并与之建立连接。然而在 实际的很多系统中网络中的老节点也有选择新节点的情况 存在。下面我们就介绍一种相互选择加权网络模型，其网络 模型如下【3 2 】： ( 1 ) 初始网络中有o 个相互孤立的节点( o = 朋) ，假设每 个节点的初始吸引子为a ； ( 2 ) 在每一个时问步，新节点一被加入到网络中来，随后网 络中的每个节点i ( 包括新加入的点) 以某一概率选择m 个其它的节点，i 节点选择_ ，节点的概率如下： 硕士学位论文 n 叫南 协s ， ( 3 ) 如果只有i 选择了，而，没有选择上i ，那么这两个节点之 间不建立连接或者它们之间已经有连接了其边权保持 不变。而如果两个节点i 和j 都互相选择上了，那么边 需要说明的是为了保证孤立的节点或新节点能被选择上，我 们令a 0 。另外如果两个节点i 和，原来没有连接我们可以视 前面的两个加权网络模型权重是静态的或者是局部变化 的，而在相互选择加权网络模型中在每个时间步整个网络中 的边权都是可以变化的，并且网络内部原来没有建立连接的 两个节点都可以重新建立连接，这些都与现实系统非常接近。 下面给出本模型的解析过程：采用连续近似我们得到： m 2 ( + 彳) ( j ，+ 彳) 瑟翥万滴( 2 - 9 ) 因此我们得到： 鲁2 莩誓耥2 篱 协 最后一项是这样得到的： 军州孚：f 鬻崭，协 赫精 争 加权网络及其复杂网络动力学 图2 - 6 节点总权重分布p ( s ) - s - 4 ，插图拟合了幂指数岱和参数m 之间的关系。 p 图2 - 7 节点总权重分布p ( w ) - w - 9 硕i 学位论文