（热能工程专业论文）无标度网络上的信息交通流研究.pdf

摘要 复杂网络是研究复杂系统的一门新兴学科，近几年受到国内外学者的广泛关 注任何复杂系统都可以抽象成为由相互作用的个体组成的网络，因而网络无处 不在，遍及自然界和人类社会其中颇具代表性且受到广泛研究的网络有互联网， 万维网，铁路网，航空网，电力网，蛋白质相互作用网，新陈代谢网，基因调控网和 各种合作性的网络等研究这些网络不仅对人们的工作和生活至关重要，而且对 了解自然界奥秘有深远的科学意义 复杂网络研究关注个体之间的微观相互作用导致的系统的宏观现象这种将 系统行为作为一个整体的研究方式不受传统还原论方法的限制，从而能够预言复 杂系统的整体行为，包括自组织特性，涌现等这使得以网络的方式研究复杂系统 成为了必然趋势同时，复杂网络的研究热潮促进了学科之间界限的打破，推动了 统计物理，非线性动力学，应用数学，信息工程，社会学和生物学等多学科的交叉 和发展因此，复杂网络的研究具有重大的理论价值 另一方面，通讯网络，例如互联网、万维网、点对点网络在当今世界起着极 其重要的作用这些系统的动力学行为得到了很多领域学者的广泛关注这些通 讯网络同时也可以看作复杂网络加以研究，因此研究这些系统从而缓解日益严重 的信息拥堵问题，从而提高网络中信息传递的效率是具有积极意义的根据当前 国内外复杂网络的研究动态和发展趋势，结合实验室研究实际情况，我们在复杂 网络的交通动力学过程方面做了比较系统的工作本文的主要工作如下 第一章和第二章详细介绍了复杂网络研究的重要意义，复杂网络研究的基本 内容和基本方法以及复杂网络中信息交通的研究现状和研究背景在此基础之上， 第三章和第四章中系统地研究了无标度网络上的交通动力学在基于局部拓扑和 动态信息数据包路由规则以及全局路由规则下研究了系统中提高网络信息流通 讯能力的方法和手段包括使用断边和改变信息包发送顺序的方法，使得网络通 讯能力有了明显的增强并提高了对拥塞现象的容忍能力，网络效率得到显著提 高。我们的研究对新一代路由协议的设计有一定的指导意义最后一章给出全文 工作总结和对以后工作的展望。 上述研究成果分别整理为两篇学术论文，已正式或可能将在p h y s i c a l r e v i e we ，p h y s i c a ll e t t e ra 上发表 关键词：复杂网络；网络上的信息流； 无标度网络；断边；最短路径 a b s t r a c t c o m p l e xn e t w o r k si sar i s i n gd i s c i p l i n ew h i c hi sd e d i c a t e di nc o m p l e xs y s t e m a n dd o m e s t i ca n df o r e i g ns c h o l a r sp a ym u c ha t t e n t i o no ni t i nr e c e n ty e a r s a n y c o m p l e xs y s t e mc a nb ea b s t r a c t e da san e t w o r kw h i c hi sm a d eo fi n t e r a c t i o n a l i n d i v i d u a l s ， s on e t w o r k se x i s te v e r y 孵h e r e s u c ha si n t e r n e t ，w i 嘿n e t 孵r k s ，r a il w 8 y n e t w o r k s ，a i rn e t w o r k s ，p o w e rn e t w o r k s ，e t c t or e s e a r c ht h o s en e t w o r k sn o to n l yh a s s t r o n gr e l a t i o n s h i pw i t ho u rw o r ka n dl i f e ，i ta l s oh a sp r o f o u n ds c i e n t i f i cm e a n i n g s f o ru n d e r s t a n d i n gn a t u r e c o m p l e xn e t w o r k s r e s e a r c hp a ya t t e n t i o no nm a c r o s c o p i c a lp h e n o m e n aw h i c hi s r e s u l t e db ym i c r o c o s m i ci n t e r a c t i o na m o n gi n d i v i d u a l s t h i ss y s t e mw i l1a c ta sa 啊h o l eb ym e a n so ft r a d i t i o n a l 珥e t h o d so fr e d u c i n gt h er e s t r i c t i o n s ，w h i c hc a nb e p r e d i c t e dt h a tt h eo v e r a l lb e h a v i o ro fc o m p l e xs y s t e m s ，i n c l u d i n gs e l f o r g a n i z i n g c h a r a c t e r i s t i c s ，s u c ha sh a v ee m e r g e d t h i sm a k e saw e bo fc o m p l e xs y s t e m so nt h e 髓yt ob e c o m et h ei n e v i t a b l et r e n d 。a tt h es a m et i m e ，c o n l p l e xn e t w 0 r ko ft h ec r a z e f o rb r e a k i n gt h eb o u n d a r i e sb e t w e e nd i s c i p l i n e s ，t op r o m o t et h es t a t i s t i c a lp h y s i c s ， n o n l i n e a rd y n a m i c s ，a p p l i e dm a t h e m a t i c s ，i n f o 珈a t i o ne n g i n e e r i n g ， s o c i 0 1 0 9 ya n d b i o l o g y ，a n do t h e rm u l t i d i s c i p l i n a r ya n dc r o s s d e v e l o p m e n t t h e r e f o r e ，t h ec o m p l e x n e t w o r ko fr e s e a r c hh a sg r e a tt h e o r e t i c a lv a l u e o nt h eo t h e rh a n d ， c o m m u n i c a t i o nn e t w o r k s ，s u c ha si n t e r n e t ，w w w ， p 2 p ， t a k e i m p o r t a n tr 0 1 ei no u rw o r l d m a n ys c i e n t i s t sp a ym u c ha t t e n t i o no nt h ed y n a m i c b e h a v i o ro ft h o s es y s t e m s 。t h o s en e t w o r k sa l s oc 8 nb er e g a r d e da sc o m d l e xn e t w o r k s a n db er e s e a r c h e df o rr e s o l v i n gt h es e r i o u si n f o r m a t i o nt r a f f i cj 鲫 a c c o r d i n gt o t h ed e v e l o p m e n to fc o m p l e xn e t w o r k sa n do u rr e a lc o n d i t i o n ， w em a k eas y s t e mw o r k 0 nt r a f f i cd y n a m i co fc o m p l e xn e t w o r k s f i r s t ，c h a p t e r1a n d2i n t r o d u c e dt h ei m p o r t a n t a n c eo fb a s i cr e s e a 工ho nc 伽p l e x n e t w o r ka n dm e t h o d sb r i e f l y 0 nt h i sb a s i s ，s t a r t i n gf r o mc h a p t e r3t oc h a p t e r4 ，w e p a yo u ra t t e n t i o no nt r a f f i ci n f o r m a t i o nr e s e a r c hs y s t e m l y w em a k eo u ts o m e e f f e c t i v ew a y st oe n c h a n c es c a l e f r e en e t w o 】c 8 p a ci t yu n d e rg l o b a la n dl o c a l r o u t i n gs t r a t e g yr e s p e c t i v l y ，i n c l u d i n gli n k c l o s i n ga n dc h a n g ei n f o p a c k e t s s e n d i n gm e t h o d s 0 u rr e s e a r c hm a yh a v es o m ep o s i t i v em e a n i n g so nd e s i g n i n gn e 鬻 r o u t i n gs t r a t e g y i nt h e1 a s tc h a p t e r ，w es u m m e r yo u rw o r ka n dg i v eo u to u re x p e c t i o n k e y w o r d s ：c o m p l e xn e t w o r k s ：i n f o r m a t i o nf l u xo nn e t w o r k s ：s c a l e f r e e n e t w o r k s ：l i n k c l o s i n g ：s h o r t e s tp a t h 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅或借阅，可以将学位论文编入有关数据库进行 检索，可以采用影印，缩印或扫描等复制手段保存，汇编学位论文。 保密的学术论文在解密后也遵守此规定。 作者签名： 年月 中国科学技术大学硕士论文无标度网络上的信息交通流研究 1 1 复杂网络研究简介 1 1 1引言 第l 章绪论 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述一个典 型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表 真实系统中不同的个体，而边则用来表示个体之间的关系，通常是当两个节点之 间具有某种特定的关系时连一条边，反之则不连边有边相连的两个节点在网络 中被看作是相邻的例如，神经系统可以看作是大量神经细胞通过神经纤维相互 连接形成的网络：计算机网络可以看作是自主工作的计算机通过通信介质如光 缆、双绞线、同轴电缆等相互连接形成的网络类似的还有电力网络，社会关系网 络，交通网络等等 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是 他们不在意的在这里，我们把网络不依赖于节点的具体位置和边的具体形态就 能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构那么， 什么样的拓扑结构比较适用于描述真实的系统呢两百多年来，对这个问题的研 究经历了三个阶段在最初的一百多年里，科学家们认为真实系统各因素之间的 关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像 是格子体恤衫上的花纹：又如最近邻环网，它总是会让你想到一群手牵着手、围着 篝火跳圆圈舞的姑娘到了2 0 世纪5 0 年代末，数学家们想出了种新的构造网 络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据 一个概率决定数学家把这样生成的网络叫做随机网络，它在接下来4 0 年里一直 被很多科学家认为是描述真实系统最适宜的网络直到最近几年，由于计算机数 据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不是规则网络， 也不是随机网络，而是具有与前两者皆不同的统计特征的网络这样的一些网络 被科学家们叫做复杂网络( c o m p l e xn e t w o r k s ) ，对于它们的研究标志着第三阶 段的到来 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这 几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是 中国科学技术大学硕士论文无标度网络上的信息交通流研究 大量真实复杂系统的拓扑抽象：其次，它至少在感觉上比规则网络和随机网络复 杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种简单 方法能够生成完全符合真实统计特征的复杂网络：最后，由于复杂网络是大量复 杂系统得以存在的拓扑基础，因此对它的研究被认为有助于理解“复杂系统之所 以复杂”这一至关重要的问题 4 ，5 1 1 2复杂网络研究现状 复杂网络是描述和理解复杂系统的一种很重要的方法复杂网络研究不局限 于经典统计物理的研究框架，从整体的角度来认识和研究复杂系统由于任何复 杂系统都可以从实际背景出发，抽象成由相互作用的个体构成的网络，因此，网 络无处不在，并且为复杂系统研究提供了一个崭新的、相对简单的研究平台然 而任何一种复杂系统都很庞大并且具有自身的特殊性，这增加了研究的难度，需 要多学科研究人员的共同努力和学科的交叉，同时也使得复杂网络的研究变得丰 富多彩复杂网络的发展得益于各个学科的齐头并进首先，随着数据采集的计算 机化，出现了各种真实网络的拓扑结构的大型数据库：第二，计算能力的大幅度 提高使我们可以研究包含几百万到几十亿个节点的网络，研究以前计算机能力所 不及的问题：第三，学科界限的打破为揭示不同的复杂网络的共同特性提供了有 利的条件：第四，从整体的角度研究系统行为的呼声越来越高，这就要求对网络 结构如何影响其上的动力学过程有一个深入系统的理解在这些发展趋势和环境 的推动下，复杂网络的研究得以迅猛的发展，提出了很多崭新的观念和研究方法 近年来，可以从图1 和图2 看出学术界关于复杂网络的研究正方兴未艾。特 别国际上有两项开创性工作掀起了一股不小的研究复杂网络的热潮。一是1 9 9 8 年w a t t s 和s t r o g a t z 在n a t u r e 杂志上发表文章，引入了小世界( s m a l 卜w o r l d ) 网络模型，以描述从完全规则网络到完全随机网络的转变。小世界网络既具有与 规则网络类似的聚类特性，又具有与随机网络类似的较小的平均路径长度。二是 1 9 9 9 年b a r a b a s i 和a l b e r t 在s c i e n c e 上发表文章指出，许多实际的复杂网络 的连接度分布具有幂律形式。由于幂律分布没有明显的特征长度，该类网络又被 称为无标度( s c a l e f r e e ) 网络。而后科学家们又研究了各种复杂网络的各种特 性。国内学界也已经注意到了这种趋势，并且也开始展开研究。加入复杂网络研 究的学者主要来自图论、统计物理学、计算机网络研究、生态学、社会学以及经 济学等领域，研究所涉及的网络主要有：生命科学领域的各种网络，i n t e r n e t w w w 网络，社会网络，包括流行性疾病的传播网络、科学家合作网络、人类性关系网 络、语言学网络，等等：所使用的主要方法是数学上的图论、物理学中的统计物 2 中国科学技术大学硕士论文无标度网络上的信息交通流研究 理学方法和社会网络分析方法。我们首先介绍这一研究的发展，并在此基础上论 述这类研究的重要的科学和哲学意义。 卑傍 图卜ls c i 收录的关于复杂网络的研究论文数量( 统计了从1 9 9 8 年到2 0 0 4 年第一季度的情况，从图中可以看出，复杂网络的研究方兴未艾) 疆 、 誓 议 袋 图卜2 关于网络的研究论文数量( 统计了从 1 9 9 7 年到2 0 0 3 年含有“n e t w o r k ”的文章数目) 目前已经得到研究的网络在结构上主要包括：规则( r e g u l a r ) 网络、随机 ( r a n d o m ) 网络和无标度网络等。在图论中，所谓规则网络如一维链、二维晶格 即具有平移对称性的网络。2 0 世纪5 0 年代以后无明确设计原理的、具有随意连 接关系的大规模网络，首先被匈牙利数学家p a u le r d s 和a l f r 6 dr 6 n y i 描述为 随机网络。这是最简单的也是被大多数人认识的复杂网络。在图论中，由n 个顶 点构成的图中，我们从中随机连接m 条边所构成的网络就叫随机网络。另一类网 络是同时具有高集聚程度、小最短路径的网络，称为小世界网络。w a t t s 和 s t r o g a t z 发现，对于o 时，度为k 的节点几乎不 存在，因此，这类网络也称为均匀网络( h 0 m o g e n e o u sn e t w o r k ) 近几年的大量研 究表明，许多实际网络的度分布明显不同于泊松分布特别地，许多网络的度分 布可以用幂律形式尸( j j ) 七吖更好的描述( 图( 卜3 ( b ) ) 数学上，如果一个函数 f ( x ) 具有如下性质：对任意给定常数a 存在常数b 使得厂( = 矿( x ) 则称该函 数是“无标度 的，而幂函数正是具有这种性质的唯一的函数，这表明具有幂律 度分布的网络没有明显的特征标度，所以这类网络称为无标度网络。这样，在一 个大规模的无标度网络中，绝大部分的节点的度相对很低，但存在少量的度相对 很高的节点。因此，无标度网络是非均匀的，而那些少量的度相对很高的节点称 7 中国科学技术大学硕士论文无标度网络上的信息交通流研究 为网络的中心结点( h u b ) 。 另外一种表示度数据的方法是绘制累积度分布函数： 最( k 尼) = 最 r 七 ( 1 5 ) 它表示的是度不小于k 的概率，这种方法的好处是可以表示所有的原始数据。 对大量真实网络数据的分析表明，小世界和无标度特性在真实网络中是广泛存在 的 3 ，4 ，8 ，9 ，1 0 图卜3 泊松分布( a ) 与幂律分布( b ) 示意图 泊松分布在均值处有个峰值曲线在偏离均值时呈指数衰减 幂律分布在双对数坐标上是一条直线 1 2 2 现实世界网络 最近一段人们对网络的研究大多数通过对真实网络的直接观察而的，因此 网络数据是人们研究的第一个出发点，另一方面在同一时刻研究不同类型的网络 又很有意义。特别是1 9 9 8 年w a t t s 和s t r o g a t z 在这方面有了突破性进展，他 们对不同学科分支的网络进行了横向比较，同时特别强调不同网络的共同特点， 下面是几种常见的网络类型。 1 社会网络( s o c i a ln e t w o r k s ) 中国科学技术大学硕士论文无标度网络上的信息交通流研究 社会网络由一群人构成，他们之间有特定的通讯，交流，互相影响的模式， 个体之间的友谊，公司之间的商业往来，家族之间的互相通婚等都可以构成社会 网络，而这几种网络在过去的一段时间内被人们深入研究了，同时人们也做了大 量的定量的研究，如1 9 2 0 年科学家们就研究了戴维斯的一小群妇女之间的友谊 关系，1 9 3 6 年人们又研究了工厂内工人之间构成的关系网络，同时第一次强调了 度分布的重要性。最近几年，人们又对公司网络和性接触网络给予了高度的重视。 传统的社会网络的研究并没有取得良好的结果，这主要是由于能够研究的具 体网络很不精确，主观因素强，样本小等原因造成的。除了m i l g r a m 的间接研究 方法外，人们大多数采用问卷调查的方法，这种方法不仅费时而且花费也很大， 最后得到的网络规模也很有限，同时研究的数据也很受被问卷入主观想法的影 响，因为每个人定义朋友的标准不同，所以这样建立的社会网络就很不客观。尽 管人们想了彳艮多办法去减少这种不一致性，研究中人们不得不接受大的误差。 由于上面的问题人们开始用另外的方法去研究网络，一个很可靠的数据就是 合作网络，这是一种典型的从属关系网络，该网络中参与者参与到一个群体或另 外一个群体的活动中去，如果他们参与到同一个任务，那么参与者之间就会有连 边形成。一个很经典的这类型网络就是演员合作网络，这是通过国际电影演员合 作数据库而构建成的，如果有两个演员他们参与到同一部电影中那么他们之间就 会有一条边相连，借助这个统计特性科学家们己经做了大量的理论研究，另一个 典型的网络就是由公司董事构成的，如果两个董事在同一个董事会中，那么他们 之间就有一条连边。再一个典型的网络就是科学家合作网络，如果两个科学家参 与到同一篇文章，那么他们之间也构成联系，甚至两个人如果被在上下文提及， 特别是在同一网页或报纸中提及，那么他们也构成联系。 2 信息网络( i n f o r m a t i o nn e t w o r k s ) 第二个网络范畴就是所谓的信息网络，典型的信息网络就是学术界中科学 家们之间的学术引用网络。大多数的学术文章都会引用以前相关课题的研究文 章。这类引用就可以形成一个网络，该网络中，网络的顶点代表文章，而一个顶 点指向另个顶点的有向连边就代表一篇文章引用另外一篇文章。这种学术引用 网络反映了存储于顶点的信碑息所构成网络的结构，因此它被叫为信息网络，当 然这样的网络实际上也有社会网络的某些特性。 信息网络的一个特殊点是，在该网络中没有回路形成，也就是不可能从一个 点出发通过其他点然后又返回到原顶点，这是因为人们只能引用过去已有的文章 而不能引用将来的文章。所以，所有的连边在时间上都是后向的，从而没有闭环 9 中国科学技术大学硕士论文无标度网络上的信息交通流研究 回路形成。基于学术研究的目的，引用网络有很大的优势，他们数量丰富而且非 常精确。对发表模式的量化研究至少可以追溯到1 9 2 6 年a 1 f r e d 的突破性研究， 他提出了所谓的科学成果产出原理，该原理提出各科学家写出的论文数量服从幂 率分布。而这个结论实际上是可以被扩展到社会科学领域。然而真正意义上的科 学引用网络开始于1 9 6 0 年代，那时人们才得以通过大的数据库来分析这种网 络。人们发现这种引用网络的出度和入度都服从幂率分布，这对后来的研究有着 深远的意义。此后由于更好的数据库资源的出现人们又做了大量的其他很有意义 的研究。 另外一个重要的信息网络就是万维网，这个网络由含有大量信息的网页构 成，网络中的连边代表一个网页向另外一个网页构成超级链接。值得注意的是网 页和i n t e r n e t 网络是不同的，后者是通过光纤构成的物理链接。与引用网不同， 万维网是可以构成环路的，那里没有自然的秩序或强制要求使网络中不能出现闭 环。1 9 9 0 年，a l b e r t 等人对万维网进行了深入的研究，他们的研究成果有着很 重要得影响。与引用网相似，万维网的出度和入度也服从幂率分布，同时还具有 其他属性。 3 技术网络( t e c h n o l o g i c a ln e t w o r k s ) 这是人造网络，其设计的典型目的是分配一些商品或资源，如电或信息。电 力格子是一个很好的例子，一个高伏电压三相传输线的网络，跨越一个国家或者 国家的一部分。其它分配网络包括航空路线网络，和道路网络，铁路网络以及人 行交通网络。河流网络被视为是分配网络的自然出现形式。电话网络和诸如邮局 或包裹递送公司使用的那些递送网络也都属于这一一般性类别，并且在学术研究 者之前就有相关企业进行了研究。电子电路介于分配网络和通讯网络之间。另一 个研究得非常广泛的技术网络是因特网，即，计算机之间物理连接网络。由于因 特网上计算机的数量庞大且经常变动，因此对此网络结构的研究通常是粗略的， 针对路由器一网络上控制着数据运动的有特殊目的的计算机，或“自治系统” 一即计算机群，群中联网是局部处理的，而群之间数据在公共因特网上流动。单 个公司或大学的计算机可能形成一个自治系统一此自治系统经常利用域名进行 简单联系。 4 生物网络( b i 0 1 0 9 i c a ln e t w o r k s ) 很多生物系统可以被表示成网络。生物网络的典型例子可能是代谢路径网 络，它是代谢基质和代谢产物的刻画，如果一己知代谢反应存在，其作用于给定 l o 中国科学技术大学硕士论文 无标度网络上的信息交通流研究 基质并产生指定产物，两者之间由有向边连接。一些学者对代谢网络的统计学属 性进行了研究，例如，j e o n gf e l l 和w a g n e r 以及s t e l l i n g 等人。其它的网络 有蛋白质相互作用网络( 与代谢物中的化学反应相反，它经常被指为蛋白质相互 作用网络) ，基因调节网络，基因表达式，即基因编码蛋白质的转录和翻译产物， 能够被其它蛋白质的存在所控制，包括催化剂和抑制剂，因此基因组自形成了一 个开关网络，顶点代表蛋白质，有向边代表蛋白质产物对其它顶点蛋白质的依赖 生物网络另一个研究得很多的例子是食物网，其中顶点代表生态系统中的物种， 从物种a 到物种b 的有向边表明a 捕食b 。有时按相反方向来画关联关系，因为 生物学家倾向于根据流经食物网的能量流或炭流来考虑：因此捕食者一猎物关联 关系被画为从猎物指向捕食者的箭头，表明当猎物被吃时能量从猎物流向捕食 者。 1 2 3 复杂网络拓扑模型 1 规则网络 在一个全局耦合网络中，任意两个点之间都有边直接相连。因此，在具有相 同节点数的所有的网络中，全局耦合网络具有最小的平均路径长度厶。= l 和最大 的聚类系数e ，= 1 。虽然全局耦合网络模型反映了许多实际网络具有的聚类和小 世界性，但可以很容易看到该模型作为实际网络模型的局限性。一个有n 个点 的全局耦合网络有n ( n 1 ) 2 条边，然而大多数大型实际网络都是很稀疏的。它 们边的个数一般至多是d ( ) 而不是p ( 2 ) 。 另一个被广泛研究的稀疏的规则网络模型是最近邻耦合网络，其中每一个节 点只和它周围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含n 个 围成一个环的节点其中每个节点都与它左右各k 个邻居点相连。对充分大的k 值，最近邻耦合网络的聚类系数为e ， ，因此，这样的网络是高度聚类的， 然而，最近邻耦合网络不是一个小世界网络。相反，该网络的平均路径长度为 k 一( 专o o ) 。 另一个简单的例子是星形耦合网络，它是一个同时具有聚类和小世界特性的 稀疏的规则网络。星形耦合网络有一个中心点，其余的n 一1 个点都只与这个中心 点连接。而它们彼此之间不连接，星形网络的平均路径长度为k 专2 ( 一o d ) 其聚类系数为c 。，专1 ( _ ) 。这表明星形网络模型同时具有稀疏性，聚类性 和小世界等特性。从这个方面来看，星形网络作为一些实际网络的模型要比最近 邻耦合网络好，当然大多数的实际网络并不具有精确的星形形状。 中国科学技术大学硕士论文无标度网络上的信息交通流研究 2 随机网络 与完全规则网络相反的是完全随机网络，一个典型的随机网络模型是e r d o s 和r 6 n y i 于4 0 多年前开始研究的e r 随机图模型。如果网络有n 个节点对任 意节点对( i ，j ) ，以相同的概率p 在它们之间连线，这样就可以得到包含约洲( n 1 ) 2 条边的e r 随机图理论的一个主要研究目标是：当概率p 为多大时，随机图 会产生一些特殊的属性e r d o s 和r 6 n y i 发现当概率p 达到或超过一个临界值 阢( h l ) 时，几乎所有的e r 随机图都是完全连通的 e r 随机图的平均度是 = p ( 一1 ) 兰州设三。j 是e r 随机图的平均路径 长度直观上，对于e r 随机图中随机选取的一个点网络中大约有 个其 它的点与该点之间的距离等于或非常接近，因此n 即k l i l l n 。这种平均路径长度以网络规模的对数增长的特性是典型的小世界 特征。因为1 n n 的值随n 增长得很慢，这就使得规模很大的网络也可以具有很 小的平均路径长度。 e r 随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均为 p 因此e r 随机图的聚类系数是c = p = 1 。这意味着大规模的e r 随机 图没有聚类特性，而实际的复杂网络一般都具有明显的聚类特性。也就是说，实 际的复杂网络的聚类系数要比相同规模的e r 随机图的聚类系数高得多。对于固 定的 ，当n 充分大时，e r 随机图的度分布可用p o i s s o n 分布来表示： 脚盼印刊脚幸 6 ， 当n 趋于无穷大时，上述近似等式是精确成立的。因此e r 随机图也被称为 p o i s s o n 随机图，尽管e r 随机图作为实际复杂网络的模型存在明显的缺陷。在 2 0 世纪的4 0 年中e r 随机图理论一直是研究复杂网络的基本理论。其中的些 基本思想在目前的复杂网络理论研究中仍然很重要。 1 2 中国科学技术大学硕士论文 无标度网络上的信息交通流研究 。固国 辩w i r i n g o f h a h o0 a ) 融i o n 舔如 图卜4 小世界模型( a ) w s 小世界模型( b ) n w 小世界模型 3w s 小世界网络模型( w a t t s s t r o g t zs m a l lw o r l dn e t w o r k ) ( 见表1 ) 小世界网络模型( 见图卜4 ) 反映了现实生活中的一种现象：一个人的朋友大 都是他的邻居或单位的同事，然而也有些是相距较远的人。w a t t s 和s t r d g t z 于 1 9 9 8 年提出了小世界网络模型，称为w s 小世界模型，该模型可以看作是从规则 网络向随机网络的过渡过程，其构造算法如下： a ) 初始网络是一个围成环状结构并包含n 个节点的最近邻耦合网络，其 中每个节点都与它左右相邻的各k 2 个节点相连。k 是偶数。 b ) 以概率p 随机地重新连接网络中的每条边，即依次选择网络中的每个 节点，将其所连接的边的另一个端点重新和网络中随机选择的一个节点相连。同 时规定任意两个不同的节点之间至多只能有一条边并且每个节点都不能有边与 自身相连。 在上述模型中，p ：o 对应于完全规则网络，p = 1 则对应于完全随机网络，通 过调节p 的值可以控制从规则网络到随机网络的过渡过程w s 小世界模型构造法 中的随机化过程有可能破坏网络的连通性，n e w m a n 等稍后提出了另一类小世界 网络模型，称为n w 小世界模型。该模型通过“随机化加边 的方式取代w s 小世 界模型中的“随机化重连 而得到。第一步算法同w s 模型的构造一致，第二步 构造算法为：以概率p 随机选取一对节点并加上一条边，同时规定任意两个不同 的节点之间至多只能有一条边并且每个节点都不能有边与自身相连。在n w 小世 界模型中，p ：0 对应于原来的最近邻耦合网络，p = l 则对应于全祸合网络。在理 论分析上，n w 小世界模型要比w s 小世界模型简单。当p 足够小和n 足够大时， n w 小世界模型本质上等同于w s 小世界模型。 中国科学技术大学硕士论文无标度网络上的信息交通流研究 可以简单的求得w s 小世界网络的聚类系数为： c ( p ) = 3 ( k 一1 ) ( 1 一p ) 3 2 ( 2 k 一1 ) 同样的，n w 小世界网络的聚类系数为： c ( p ) = 3 ( k 1 ) 【2 ( 2 k 1 ) + 4 印( p + 2 ) 】 ( 卜7 ) ( 卜8 ) w s 小世界模型的平均路径长度l 的精确解析表达式相对较难求出。可以 利用重正化群的方法得到如下近似表达式： 三( p ) = 2 彤( m 印2 ) k ( 卜9 ) 其中f ( u ) 为一普适标度。n e w m a n 等人基于平均场方法给出了如下的近似表 达式： 胁志洲压 ( 1 1 0 ) 1 4 中国科学技术大学硕士论文无标度网络上的信息交通流研究 曩l 餮磊氍奄铺湖啪m 曩t 蹶 n e t 瞅& 臻f厶_ occ o w 1 吣r 8 h l e 垤l1 5 3 1 2 73 5 2 l3 13 3 so 1 0 7 8 o o z 3 i m 研，c t d a m i i nl d3 0 l s 6 2 墨5 2 一o l l3 7 3 7 66 ，3 6 6 1 8 d 1 8 o 3 o i m 州e 聪。强2 2 s 2 2 66 l3 6 52 ”o - 7 9o o 2 7 m e d u n e 1 u 西。疆b p1 s z o 2 s 1l & l 6t 争lo 0 6 61 1 l o m a t h c o - a u t h o f 小p 7 0 9 7 5& 99 s8 2o 5 9s 4 1 0 。 e “，虎扯t i g n 峥h 3 1 52 8 3 2 6 21 9 80 s 9o s i i ，dp k f d b 1 5 44 7 s3 i o3 2 3o i so 0 3 w o f k d 矗s y n y m 2 2 ，3 i l1 3 8 s3 8 lo 7o o 0 0 6 p o v 盯耐 i ，9 4 12 甜 l 禽71 2 4o 0 8o 5 c l e g 嘲8 2 8 2l 2 6 s2 2 so 2 8o o s 洼。下标矗为麓帆嘲娼疆墨下的计算，曩进对比宴际一纂与相应囊弧一培相目的节a 奠期迎囊) 性质可取爱及支实一餐 具宥小世鼻和较毫鼍鼻蕞数的性质 4 无标度b a 网络( 将在第二章中详细介绍) 5 其它网络模型 虽然b a r a b a s i 和a 1 b e r t 提出的演化模型得到了普遍的重视，然而最早发 现现实网络的度分布具有幂律特性的物理学家是p r i c e 。他提出的累积优势 ( c u m u l a tiv ea d v a n t a g e ) 和b a r a b a si 等人提出的优先连接其实是一个概念，在 统计科学论文被引用的次数时，p r i c e 提出了入度和出度的概念并发现这两个指 标都具有幂律分布的特性c a l l a w a y 等人提出了一个简单的网络增长模型：在网 络中依次加入节点，每次加入一个节点的同时加入均值为m 条的无向边，m 是一 个平均值，而实际每次加入的边数可能会不同，因此m 并不局限于整数。该模型 同先前模型的主要不同在于新加入的边的一端并不是连接在刚加入的节点上，而 是从图中一致地随机选取两个节点进行连接，因此没有优先连接机制，导致该模 型并不表现出幂律度分布特性。a l d o u s 等人也提出了一个相关的模型，在m 一1 时该模型与同e a l l a w a y 等入的模型等价b a u e r 等人将此模型推广到了有向图的 形式d o r o g o v t s e v 等人将c a l l a w a y 的模型推广到包含优先连接的情 形。k t a p i v s k y 等人研究了一个完全有向的模型。其中节点和有向边以随机定常 速率加入，每个节点新加入一条指向外部的边的概率和它们的出度成正比，而新 加入一条指向内部的边的概率正比于其入度，再加上一个合适的常数偏移量。由 1 5 中田科学技术大学硕士论文无标度网络上的信息交通流研究 此得到的模型其入度和出度的分布都是幂律的，这与万维网中所观察到的特性是 相符的a i e l l o 等人也提出了一个类似但略有不同的模型，并给出关于相关性 质的严格证明k 1 e i n b e r g 等人认为某些网络的增长是通过复制节点来实现的， 他们以万维网的增长为例提出了如下模型：随机选取一个节点v 并加入m 条边， 加边的方式是随机选取另外一个节点，并将这个节点的所有边都和v 相连，重复 选择