（理论物理专业论文）信息传播的dfa分析.pdf

摘要 信息传播的d f a 分析 摘要 复杂网络可以被用来描述从自然到社会的各种系统。自复杂网络 的无标度特性被发现以来，它受到越来越多的关注。目前，研究如何 控制通讯流的堵塞是一个很热的课题。由于通讯网络不可能总是保持 畅通无阻的状态，因此，如何维持整个通讯网络保持正常并有效地工 作就是一个很重要的课题。为了更好的模拟网络中不同的节点拥有不 同的能力，我们采用各个节点的产生数据包和处理数据包能力与它们 各自的度相关的模型。在本文中，我们用d f a 的方法，分析了从三种 不同的路由策略中取出的数据信息的关联性。我们发现通讯数据的关 联度可以被分成三个区域：弱关联、中度关联、强关联。其中，d f a 的标度在弱关联区域和强关联区域是保持不变的，而在中度关联区域 时逐渐增加的。我们认为复杂网络的通讯流可以分为三个相：自由相、 缓冲相、堵塞相。这将比原来定义的两个相( 自由相、堵塞相) 更准 确。 关键字：通讯数据、d f a 、堵塞、自由相、缓冲相 a b 蚰 a c t a b s t r a c t c o m p l e x n e t w o r k sc b eu s e dt od e s c r i b eo fs y s t e m sf r o mn a t u r et o s o c i e t y , t h u st h e r eh a sb e e naq u i c k l yg r o w i n g i n t e r e s ts i n c et h e d i s c o v e r i e s0 1 1s c a l e f r e e p r o p e r t i e s a tp r e s e n tu n d e r s t a n d i n ga n d c o n t r o l l i n go ft r a f f i cc o n g e s t i o no nn e t w o r ki sa h o tt o p i c h o w e v e r , t h e c o m m u n i c a t i o ni nt h et r a f f i cd o e sn o ta l w a y sm a r c h g o 蠹e e l y t h e r e f o r e ， s u s t a i n i n gi t sn o r m a la n de f f i c i e n tf u n c t i o n i n gi sab a s i cr e q u i r e m e n t t o m o d e lr e a l i a i cs i t u a t i o nw h e r ed i f f e r e n tn o d e si nan e t w o r km a yh a v e d i f f e r e n tc a p a b i l i t i e s ，t h em e s s a g eo rp a c k e tc r e a t i o na n dd e l i v e r i n gr a t e s a tan o d ea l ea s s u m e dt od e p e n do nt h ed e g r e eo f t h en o d e i nt h i sa r t i c l e ， w ea n a l y z et h ec o r r e l a t i o no ft r a f f i cd a t af o rt h r e et y p i c a lr o u t i n g s t r a t e g i e sb yt h ed e t r e n d e df l u c t u a t i o na n a l y s i s ( d f a ) a n df i n dt h a t d e g r e eo fc o r r e l a t i o no ft h ed a t ac a nb ed i v i d e di n t ot h r e er e g i o n s ，i e ， w e a k , m e d i u m , a n ds t r o n gc o r r e l a t i o n t h ed f as c a l i n g sa r ec o n s t a n t si n b o t ht h er e g i o n so fw e a ka n ds t r o n gc o r r e l a t i o nb u tm o n o t o n o u s l y i n c r e a s ei nt h er e g i o no fm e d i u mc o r r e l a t i o n o u rr e s u l t ss u g g e s tt h a ti ti s b e u e rt oc o n s i d e rt h et r a f f i co nc o m p l e xn e t w o r k sa st h r e ep h a s e s ，i e ，t h e f r e e ，b u f f e r , a n dc o n g e s t i o np h a s e ，t h a nj u s ta st w op h a s e sb e l i e v e db e f o r e ， i e ，t h ef r e ea n dc o n g e s t i o np h a s e k e yw o r d s ：t r a f f i cd a t a ，d f a ，c o n g e s t i o np h a s e ，f r e ep h a s e ，b u f f e rp h a s e 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 蜱魄 幽 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：黼 日期： 2 出：5 f f 导师签名： 烈缉 日期：塑：12 绪论 t自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述 1 - 5 。 网络可以用来描述人与人之间的社会关系，物种之间的捕食关系，词与词之间的 语义联系，计算机之间的网络联接，网页之间的超链接，科研文章之间的引用关 系，以及科学家之间的合作关系，甚至产品的生产与被生产关系，例如在社区网 络上讨论流行病的传播 6 ，7 ，接触关系网络上讨论传染病的传播 8 ，9 ，计算 机病毒在i n t e r n e t 网络或邮件网络上的传播，在无标度权中网络上研究粒子跳跃 零区域的堵塞问题 8 1 ，在科学家网络上研究科学家之间的相互影响等。网络还 可以用来讨论网络的结构与功能关系，例如在食物链网络上讨论个别或部分物种 灭绝对整体生态系统的影响，在不同的网络上讨论传染病传播的控制，讨论合作 网络中的结构和分布 8 2 。此外，网络本身的演化过程也是一个有趣的问题 8 3 ， 例如i n t e r n e t 网络的形成被认为是无限定原则的，但是它却展现了一些重要而普 适的结构特征与稳定性，再比如，对于某一个学科内的引文网络与科学家网络的 演化机制的研究，有可能给出促进科学发展的新的方案与模式。 一个典型的网络是由许多节点与连接节点的一些边组成的，其中节点用来代 表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间 具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中 被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接 形成的网络 1 0 1 1 ；计算机网络可以看作是自主工作的计算机通过通信介质如 光缆、双绞线、同轴电缆等相互连接形成的网络 1 2 1 3 。类似的还有电力网络 1 4 、社会关系网络 1 5 、合作网络 1 6 、交通网络 1 7 等等。 大量的实证研究表明，真实网络几乎都具有小世界效应，同时科学家还发现 大量真实网络的节点度服从幂律分布 卜5 ，1 8 - 1 9 。研究复杂网络的终极目标之 一是理解复杂网络上的动力学行为，特别是理解网络拓扑结构对其上动力学的影 响。譬如：病毒传播的快慢以及最终传播范围问题与网络的拓扑结构有什么影响； 数据包的传输路线对其传输效率的影响；复杂网络中的随机行走问题；高压输电 网络结构对因级联故障而导致的大停电事故的影响；耦合振子之间的连接模式对 于整体同步能力的影响以及人际关系网络对于相应市场行为及博弈关系的影响 等等。 本文主要关注网络上的信息传输动力学问题。一提到信息传输，人们首先想 到的就是互联网中邮件的传递河题，事实上，货物运输或邮局服务网络、快递运 输等都可以看作信息传播问题。 本文的主要内容大致如下： 第一章主要介绍复杂网络的背景历史、复杂网络的基本概念、现实网络的类 型、复杂网络的特征属性、复杂网络上的网络模型。包括度分布，集聚系数，小 世界效应，平均路径，网络直径，节点负荷；随机网络、小世界网络和无标度网 络等。 第二章主要介绍复杂网络上数据包传递的一些背景知识、信息传播的动力学 模型和几种路由策略( 最短路径策略、有效路径优化策略、最优传输策略) 及其 它们之间的区别。 第三章主要介绍了我们是如何用d f a ( d e t r e n d e df l u c t u a t i o na n a l y s i s ) 的分析方法来研究信息传递的时间数据。并发现非最短路径策略中的缓冲相。 第四章主要对全文进行了总结，并展望了复杂网络科学的发展前景。 2 第一章复杂网络简介 第一章复杂网络简介 近年来，复杂网络的研究是新世纪科学技术前沿的战略性课题之一，也是最 近很热门的研究课题之一。现实世界中许许多多的网络都是复杂网络：从生物体 中的大脑结构到各种新成代谢网络、从i n t e r n e t 到w 啊、从大型电力网络到全 球交通网络、。从科研合作网络到各种政治、经济、社会关系网络等等，数不胜数。 因此，复杂动力网络的研究引起了不同学科的广泛重视和关注。今天，复杂动力 网络的研究正渗透到社会科学、物理学、以及医学、生物学等众多不同的学科。 对复杂网络以及网络拓扑结构如何影响其动力学行为的研究已成为一项极其重 要而且富有挑战性的科研课题。 复杂网络描述着各种各样的系统，例如，细胞就被描述为通过化学反应连接 化学物的复杂网络；国际互联网被描述为通过各种物理的或无线的连接把路由器 和计算机连接在一起的复杂网络；思想和理念在社会网上传播，其节点就是人类， 边就表示各种社会关系；万维网是一个网页通过超连接来连接的巨大的虚拟网 络。这些系统仅代表近来引起科学界研究确定复杂网络拓扑结构机理的许多系统 中的几个例子。 在过去的几年中，有关与网络刻画和理解的研究工作非常活跃。事实上，在 许多自然和人造系统中都存在着大规模的复杂网络。如生态系统中，物种之间的 相互关联可以描述为复杂的食物链网络；社会系统可以抽象成描述个体间多种相 互作用的图来代表；在科技领域中，互联网和万维网是自组织网络的原型代表； 在我们的现代社会中，许多庞大的基础系统如能源网和航空运输网，都是不可缺 少的网络系统。具有活力的细胞也不例外，基因、蛋白质和其他分子之间的相互 作用形成了一个复杂的网络，从而产生了细胞的组织和功能。 本章将介绍的内容分为以下几部分：网络的基本概念、现实网络的类型、网 络的特征属性和网络模型。 3 第一章复杂网络简介 1 1 复杂网络的的基本概念 j网络可以用来描述人与人的社会关系，物种之间的捕食关系，词与词之间的 语义联系、计算机之间的网络连接、网页之间的超连接、科研文章之间的引用关 系，以及科学家之间的合作关系等。网络也可以用来形容某种现象，例如在社会 关系网络上舆论是如何传播的，关系网络中疾病是如何传播的，e - m a i l 在互联 网络中是如何发送和接收的。 这些网络系统被考虑成点和边的集合，网络是顶点( 有时也称节点) 以及边 ( 顶点之间的关联用边来表示) 的集合，其中节点表示系统的元素，两节点的连 线表示元素之间的相互作用，见图1 1 1 2 1 和图1 1 2 。例如，因特网、万维网、 社会网络、组织网络、公司间商务关系网络、神经网络、新陈代谢网络、食物网、 分布网络如血管分布或邮政运输路线分布、论文之间相互引述而形成的网络等都 是可以如此描述。图( 1 1 2 ) 展示了现实生活中的一些复杂网络的关系示意图。 图( 1 1 1 ) ：一个包含8 个顶点和十条边的小网络 4 第一章复杂网络简介 图( 1 1 2 ) ：( a ) 反映淡水湖中物种捕食关系的食物网 2 2 】；( b ) 反映私人研究机 构中科学家之间合作关系的网络【2 3 】；( c ) 个体之间性接触网络，见p o t t e r a t 等人的研究【2 4 】 还有一些更复杂的网络，网络中可能存在不止一种类型的顶点或边。例如， 在社会网中，节点可以代表男人或女人以及不同国籍、年龄、收入等不同的人群， 连线可以代表两个人之间的朋友关系，也可以代表它们之间的商业关系，地理位 置关系等等。边可以带权重，如刻画二人相互认识程度的权重，程度不同，权重 值不同。边也可以是仅有一个方向的边或者是无向的。w w w 网络、细胞内化学反 应网络、食物链网络、引文网络、电力网络、神经网络和电话呼叫网络就是有向 网络，一般无向的网络比较常见，像电影演员合作网、i n t e r n e t 网络、科学家 合作网、人类性关系网络、蛋白质互作用网络、语言学网络等都是无向网络。另 外，网络随时间演化，边可以产生或消失，边上的权重也可以发生变化，见下图 ( 1 1 ，3 ) ：( a ) 只有一种节点和一种边的无向网络：( b ) 有几种不同类型的节点和 边的网络：( c ) 边和节点有权重的网络；( d ) 每条边都有方向的有向网络。 5 第一章复杂网络简介 甜 审 秭9 协 黼 中 秘 审 伏啪 图( 1 1 3 ) ：各种网络类型的例子 i 2 现实网络的类型 ，大多数复杂网络的研究始于人们想要了解从通讯网到生态网的各种实际网 络的愿望。近来许多关于网络的研究工作的开展，很大程度上是在实际网络的观 察中进行的。真实网络中按共同属性分类，本节将针对四个不同的网络类别进行 总结：社会网络、信息网络、技术网络和生物网络。 1 、社会网络 社会网络是人的群体的网络。在这些网络中，人与人的接触模式可以是朋友、 同学、同事、或俱乐部成员。不仅是人与人，也可以是公司与公司之间的商业关 系、家族与家族之间的联姻等。 2 、信息网络 信息网络经典之例是学术论文之间的引文网络 2 5 。大部分学术论文都经由 相关主题的其它文章来引用以前做的工作。这些引用就形成了一个网络，在其中 顶点代表论文，从论文a 到论文b 的有向边代表a 引用b 。则引文网络的结构反 映了存储在它的顶点上的信息的结构，即术语“信息网络”。信息网络另一个非 常重要的例子是万维网，它是一个由包含各种信息的网页所构成的网络，这些网 6 第一章复杂网络简介 页由从一张页面到另一张页面的超链接联结 2 6 。 图( 1 2 1 ) ：两个研究得最成功的信息网络。左边：学术论文引文网络，其中顶 点代表论文，有向边代表一篇论文被另一篇论文引用。由于论文只能够引用那些 在它们之前的文章( 图中位置更低的部分) ，所以图是非循环的一一没有闭合环。 右边：万维网，一个由因特网上可获得的文本页面构成的网络，其中顶点代表页 面，有向边代表超链接。万维网上没有限制环的出现，因此一般而言它是循环的 3 、技术网络 网络的第三种类别是技术网络，这是人造网络其设计的典型目的是分配一些 商品或资源，如电信、航空路线网络 2 7 ；和道路网络 2 8 ，铁路网络 2 9 ，3 0 以及公路交通网络 3 1 。电话网络和诸如邮局或包裹递送公司使用的那些递送网 络也都属于这种一般性类别。另一个研究得非常广泛的技术网络是因特网，即， 计算机之间物理连接网络。由于因特网上计算机的数量庞大且经常变动，因此对 此网络结构的研究通常是粗略的，针对路由器网络上控制着数据运动的有特 殊目的的计算机，或“自治系统”即计算机群，群中联网是局部处理的，而 群之间数据在公共因特网上流动。单个公司或大学的计算机可能形成一个自治系 统此自治系统经常利用域名进行简单联系。 4 、生物网络 生物网络的典型例子可能是代谢路径网络，它是代谢基质和代谢产物的刻 画，如果已知代谢反应存在，其作用于给定基质并产生指定产物，两者之间由有 向边连接。生物网络另一种重要的类别是基因调节网络。基因表达式，即基因编 7 第一章复杂赠络简介 码蛋白质的转录和翻译产物，能够被其它蛋白质的存在所控制，包括催化剂和抑 制剂，因此基因组自身形成了一个开关网络，顶点代表蛋白质，有向边代表蛋白 质产物对其它顶点蛋白质的依赖。食物网和神经网络也是生物网络。 1 3 复杂网络的特征属性 过去几年中，现实世界网络中的很多有趣的特征获得研究者们的关注。其中 小世界概念、度分布、群聚系数是三个最重要的概念。这节将介绍这三个概念及 网络的一些参数特征：度关联、路径长度、节点负荷等。 1 、最短路径长度一一网络中任意两点之间有若干条路径，最短路径长度 是指：这若干条路径中节点数最少的那条的边数。我们用7 ”来表示f 距离j 点的 最短路径长度。 平均路径长度一整个网络中每对节点所需要经过的平均步数，即0 的平均值。可以用如下式子表达： f ) 2 而了b 善，。 ( 1 3 1 ) 网络直径一一在网络中，从一个节点到达另一个节点所需要经过的最 大的步数，尽管网络直径的概念与平均路径长度的概念差别很大，但很多文献中 直接用网络直径来描述节点间的平均路径长度。 2 、度关联一如果从一个度为k 的节点与一个度为k 。的节点相连的几率 与k 无关，那么我们说这个网络是不相关联的。在一个无向网络中，度关联用 p ( k l 幻来表示度为k 的节点与度为k + 的节点相连的几率。且 p ( k i 七) = l ( 1 1 3 2 ) k 对于度相关网络 3 2 】 8 第一章复杂网络简介 彬阶鬻 ( 1 3 3 ) 其中p ( t 七) 为连接几率，p ( 后，后) = i ，为度为k 的节点与度为七 的节点的所有连线数目。 对于不相关网络： p ( | j i k ) ：套啤 ( 1 3 4 ) 3 、节点负荷一一节点负荷是与最短路径长度有关的另一个参量。在整个 网络中，从一个节点沿着最短路径到另一个节点时，会经过一些节点。如果我们 考虑任何一对节点在沿着最短路径行走时经过某个点的次数，我们会发现网络中 有一些重要的节点会比其它节点经过的次数多。这种现象可以由节点负荷来定量 表示 3 3 】。即我们定义节点i 的负荷t 为网络中任何一对节点之间的最短路径经 过节点i 的次数。更确切来说，假如厶是从节点h 到节点j 之间最短距离的个 数，l h 加是节点h 与节点j 的经过节点i 的最短距离的个数。那么节点i 的负荷 为 b l = 厶l n 其中求和是对所有h ，j 且，h 为了表示这个量的统计性质，我们考虑n ( 6 ) 为一个节点的负荷为b 的几率。 平均负荷 定义为 ) 。多数情况下 可发现，现实世界网络的顶点度分布与随机网络截然不同。大多数网络的顶点度 分布都远远偏离p o i s s o n 分布，如万维网( a l b e r t ，j e o n g 和b a r a b d s i ，1 9 9 9 ) ， 国际互联网( f a l o u t s o s 等人，1 9 9 9 ) ，和代谢网( j e o n g 等人，2 0 0 0 ) 度分布 具有一条幂律尾部。见图( 1 3 1 ) 分布明显向右倾斜，这表明其分布的右边尾 部要长且值远大于平均数。当度分布满足 p ( 尼) 一k 吖( 1 3 6 ) 这类网络称为无标度网( b a r a b d s i 和a l b e r t ，1 9 9 9 ) 在研究发复杂网络度分布的过程中，已经发现的有效方法可以分为两类：一 类是动力学方法，如平均场方法和速率方程方法。另一类是概率论方法，有主方 程方法和马氏链方法。 图( 1 3 1 ) ：六个不同网络的累加顶点度分布。图中水平轴为顶点度( 在有向 引文网络和万维网下为顶点入度) ，竖轴为顶点度的累加概率分布，即度数大于 或等于的顶点的个数占顶点总个数的比例这些网络分别是：( a ) 反映数学家合 作关系的网络 3 7 】；( b ) 反映由i s l 分类的从1 9 8 1 到1 9 9 7 年之间所有论文的引文情 况的网络 3 8 】；( c ) 1 9 9 9 年左右的包含3 0 4 7 个顶点子集的万维网【3 9 】；( d ) 自治系 统水平的因特网，1 9 9 9 年4 f l 4 0 】；( e ) 美国西部电力网【4 1 】；( f ) 在酵母茵 s c e r e v is i a e 的新陈代谢过程中蛋白质的相互作用网络 4 2 】。其中，网络( c ) ， ( d ) 、( f ) 顶点度服从幂律分布；网络( b ) 在尾部上服从幂律分布；网络( e ) 顶点度 l o 第一章复杂网络简介 服从指数分布( 采用的是一维线性对数刻度) ；网络( a ) 的顶点度分布服从某种 类型的幂律分布，或者可能是两个具有不同幂的幂律分布 5 、群聚系数一一在复杂网络中，如果节点a 与节点b 相连，并且节点b 与节点c 相连，那么节点a 也极有可能与节点c 相连。在社会网络中也可以形容 成你的朋友的朋友也可能是你的朋友。那么群聚系数就是表示这种你朋友的朋友 是你朋友的几率。 群聚系数的一种定义是由w a t t s 和s t r o g a t z 提出的 4 3 。首先考虑局部i 点 的群聚系数，节点i 的度为k ，则它的邻域( 与i 点有连线的相邻节点的全体) ， 最多有k ( k 一1 ) 2 条连线。如果i 点的邻域中实际存在的连线数为e ( i ) 条，那么节 点f 的群聚系数用表示： q = 翥筹i 篇淼，s 以顶点为中心的三点组的个数 ， 。 其中三角形是指网络中包含三个顶点的集合，每个顶点与其他两个顶点都有边关 联。“关联三点组”是指包含三个顶点的集合，集合中一个顶点有边与其他两个 由无向边相连的顶点相关联。见图( 1 3 2 ) ： 对于度为0 或1 的顶点而言，由于分子和分母均为0 ，令c = 0 。整个网络 的群聚系数就是网络中所有节点的c j 的平均值 c = 乏c ， ( 1 3 8 ) 群聚系数的另一种定义是由n e w m a n ，s t r o g a t z 和w a t t s 4 4 提出的。首先 计算网络中三个连通节点的总数，然后计算网络中三角形的总数，网络的群聚系 数，即 c = 蒜篇焉氅 s 。 网络中顶点关联三点组的总数 事实上，c 等于因添加第三条边而形成三角形的三点组的个数占三点组总个数比 例。分子中的因子3 是指每个三角形在三点组中要计数三次，c 的值在 0 ，1 间变动。c 是平均概率，即网络中与同一个顶点相连的另两个顶点自身相互关联 第一章复杂网络简介 的平均概率。也可以如下表示： 一 6网络中三角形的总数c 2 苌蓐砭而丽砸丽 其中，长度为2 的路径是指从一个指定顶点开始的有向路径。 图( 1 3 2 ) ：图中有一个三角形和八个关联三点组，由公式( 1 3 7 ) ，得c = 丽1 3 ， 由公式( 1 3 9 ) 得c = ；。 6 、小世界效应社会心理学家s t a n l e ym i l g r a m ( 1 9 6 7 ) 提出的“六度 分离”概念，他断定在美国大多数人之间相互认识的途径的典型长度为六 ( k o c h e n ，1 9 8 9 ) 。小世界效应就是这种现象的一种简单描述，大多数网络中，尽 管网络规模很大，任意两节点间都存在一条最短路径。 对于网络上发生的动力学而言，小世界效应具有明显的含义。例如谣言的传 播速度远比其他的网络要快的多。同时，他也影响了因特网上数据包从一台计算 机传递到另一台计算机所需要经过的顶点数，影响到乘坐飞机或火车的旅行者图 中所需经过的中转站数，影响到一种疾病在人群中传播所需的时间长短，以及其 他。 1 2 第一章复杂网络简介 1 4 复杂网络上的网络结构模型 ， 这节，将介绍最经典的一些网络模型，包括我们在以后的章节中用到的b a 模型。 1 4 1 随机网络( e r d o s - r e n y i 模型) e r d o s r e n y i ( e r ) 模型的描述如下：给定网络节点总数n ，网络中任意两 个节点以概率p 连线，由于网络中连线数目是一个随机变量，取值可以从0 到 n 1 ) 2 ，有n 条连线的网络数目为r “：- 1 】，其中一个特定网络出现的概率 为p ( g o ) = p “( 1 一p ) n n - 1 7 2 卜n 。因此，可生成的不同网络的总数为 2 n ( n 一1 ) ，2 ，它们服从二项分布。网络中平均连线数目为p n ( n 1 ) 2 。 随机网络e r 模型的第二种描述方式：给定网络节点总数n 和连线总数n ， 而这些连线是从最大可能n 州一1 ) 2 条连线中随机选取的这样，可生成的不同网 络的总数为f n ( n 一1 ，它们出现的概率相同，服从均匀分布。网络中两个节点 连线的概率为p = 志 黼 、馨 p 棚a 雌 掌 第一章复杂网络简介 图( 1 4 1 ) ： e r d s s - r6n y i 模型演化过程的图示。初始时有n = 1 0 个孤立结点， 然后以概率p 连接每一对结点，第二行给出了p = o 1 和p = o 1 5 时两种不同的结 果。注意到图中出现了树( 阶数为3 ，长虚线) 和环( 阶数为3 ，短虚线) ，并在 p r o 1 5 = 1 5 i n 时出现了连接了半数结点的集群。 1 、随机网络的度分布：在一个以连接几率p 随机相图中，节点i 的度k ，分 布满足二项式分布 户( t = _ j ) = c 矗一。p ( 1 - p ) ”。 ( 1 4 1 ) 这个几率代表了从一个特定的节点连出k 条边的方式数，为了得出度为k 的节点 的个数z 。，我们就要算出以等于某特定值r 几率，即p ( x k = ，) 。因此，度为k 的节点数大概为 e ( x t ) = n p ( k l = k ) = 以 ( 1 4 2 ) 其中以= c ；一，p ( 1 - p ) “h 在斗0 0 时，x 。的几率分布p ( 以= ，) 满足泊松分布，即 ，( 以_ ，) 玎 鲁 ( 1 4 3 ) 因此度为k 的节点数目满足泊松分布，平均值为五 随机网络的度分布为p ( 七) = c ：一。p 。( 1 一p ) “4 在n 寸c o 时，可以由泊松分布来代替，即 p 玎呼i 如譬 4 4 ) 2 、随机网络的群聚系数：随机网络中的一个节点和它的最近邻，其中任意 两个邻居相连的几率等于网络中随机选择两个节点相连的几率。因此随机网络的 集聚系数为 c 删= p = 等 ( 1 4 45 ) 3 、随机网络的网络直径：一个网络直径是指任意一对节点间的最大距离， 严格来说，如果一个不完全连接的网络，也就是说包括一些孤立的集团或孤立点， 1 4 第一章复杂网络简介 那么这个网络直径趋于无穷大。但是我们可以定义最大的集团的直径，如果p 不是很小，那么随机网络的直径则很小，假定某个网络的直径为d ，那么距某一 特定节点的d 的节点数目接近于 4 ，即 4 a c ，因此网络直径约为 d 。! ! 丛竺。 l o g ( 。而自然中许多系统具有一个共同 特征，尸( | ) 无标度，服从大于许多数量级的幂律分布，由于前两种模型的网络 大小是一定的，而大多数现实网络是开放的，即通过不断增加新节点到系统中构 成网络。因此，节点数在网络中的使用期限内自始至终是增加的。例如演员网、 万维网、研究论文引文网都是不断增长的。其次，大多数实际网络显示出择优连 接特性。因此b a 网络，体现着两种特质，并能使标度分布不变。 1 7 第一章复杂网络简介 图( 1 4 5 ) ：无标度网络的拓扑结构1 9 9 9 年，物理学家给出了生成无标度网络 的一种简单方法，本图例有13 0 个节点，节点度服从幂指数为一3 的幂律分布。 具体步骤如下： ( 1 ) 增长：开始于少量节点( ) ，在每个时间间隔添加一个具有m ( m o t 条边的新节点( 连接到己存在于系统的节点上) 。 ( 2 ) 择优连接：当选择与新节点连接的节点时，假设新节点连接到节点i 的 概率7 取决于该节点的连通度t ，则有 x c k , ) = 南岛 ( 1 4 9 ) j 在t 个时间间隔后，模型产生一有n = m 0 + f 个节点和所，条边的随机网络。如下 图( 1 4 6 ) 所示，该网络演化进入标度不变态具有k 条边的节点的概率服从 幂律分布。指数为y m o d d = 2 9 + 0 1 。 1 8 第一章复杂网络简介 下面我们根据连续性理论，主方程方法以及速率方程方法来推导网络的度分布 ( 1 ) 连续性理论 节点i 的度七，随时间变化的方程为 鲁一轰 n 4 1 0 ) 基中j k ，= 2 m t m ，代入方程( 1 4 l o ) ，我们得到 堕：脚生：墨( 1 4 1 1 ) 根据初始条件七，( f ) = m ，我们求得 屯= 川咖4 ，其中圳2 ( 1 4 1 2 ) 方程( 1 4 1 2 ) 表明网络中所有度的演化规律都是相同的，满足幂律变化。 根据方程( 1 4 1 2 ) ，我们可以写出一个节点在t 时刻的度t p ) 小于k 的几率， p 缸o ) 后】，为： p 阮( f ) 明= p ”矽m u p t ( 1 4 1 3 ) 考虑到我们每隔一段时间会向网络中增加一个新点，因此n n n - - + n g 的几率密度，即 p ) = 丽1 ( 1 4 1 4 ) 将方程( 1 4 1 4 ) 代入方程( 1 4 1 1 ) ，我们得到 p 静小酾m 1 p t 4 朋， 因此度分布p ( 七) 可以得出： 础) = 盟笋= 丽2 m 1 a t 万1 ( 1 4 1 6 ) 1 9 第一章复杂网络简介 当t _ 时 p ( 2 m “9 k - r , 其中，= 1 f l + l = 3 ( 1 4 1 7 ) ( 2 ) 主方程方法 p ( 七，j ，f + 1 ) = _ k f - 1 p ( j 一1 ，刎+ ( 1 一万k ) p ( d ( 1 4 1 8 ) 其中p ( k ，t i ，f ) 表示时刻进来的点在t 时刻其度为k 的几率。右边第一项表示在 t 时刻度为k - 1 ，且有一条新的连线连接它的几率，第二项表示在t 时刻，度为k ， 且没有新的连线连接它的几率。 度分布可表示为： p ( 七) = 鲫( p ( _ j ，t ) ) t ( 1 4 1 9 ) 对方程( 1 4 1 9 ) 两边求和，从而可以求得其度分布为： p ( 栌牖p ( ) 丘拥+ l ，( 1 4 2 0 ) 【2 ( m + 2 ) 孟= m 方程( 1 4 2 0 ) 是一个回归方程，可以求得度分布为 p ( j ) = 面2 m 而( m + 1 ) ( 1 4 2 1 ) ( 3 ) 速率方程方法 望鉴：m ( k - 1 弋) n i k _ z ( t ) - k n 一 k ( t ) + 瓯月 ( 1 4 2 2 ) d t k n k ( t ) ” 方程( 1 4 2 2 ) 右边第一项代表了新的连线与那些有k - 1 条边的节点相连，使这 些节点的边从k 1 增加至k ，从而增加了边为k 的节点数目；第二项代表了新的 连线与那些有k 条边的节点相连，使这些节点的边从k 增加至k + l ，从而减少了 边为k 的节点的数目；第三项代表了有m 条边的新节点。在极值情况下， n a t ) = ( 七) ，而且。k n a t ) = 2 r o t ，从而得到与式( 1 4 2 2 ) 相同的回归方程。 主方程方法与速率方程方法完全等价，且与连续性理论所得到的结果相同， 因此在计算复杂网络的度分布时，这三种方法是可互换的。 第一章复杂网络简介 图( 1 4 7 ) ：改变m ，网络增长到n = 1 0 0 0 0 时的度分布。其中圆圈代表舻3 时的度分布，方形代表m = 5 时的度分布，星形代表m = 7 的度分布。其中m 。= m 1 5 本章小结 本章中，首先介绍了复杂网络的概念、它的背景与发展、它的拓扑结构；其 次，列举了一些真实网络的实例；再次，将不同网络的特征属性一一道详：最后， 详细介绍了最为重要的三种网络模型( 随机网络、小世界网络、无标度网络) ， 其中的无标度网络也是我们之后介绍的工作所采用的网络模型。值得一提的是， 最近一种混合模型 8 4 】的提出，它既有偏好依附又有随机连接， 乃= 豇( 1 丽- p ) k j + p ，其中o p l , p 是一个可以调节的参数。当p = o 时，网 络是一个度分布为p ( k ) k 4 的无标度网络；当p = l 时，网络是一个度分布为 p ( 后) p 圳4 的随机网络。 2 1 第二章复杂网络中的信息传播 第二章复杂网络中的信息传播 近年来，复杂网络中信息、包裹传递的交通拥挤问题一直是个重要的研究课 题，越来越受到物理学界和工程界的关注。比如互联网和交通网上的信息传递。 以前的一些工作主要是讨论交通的增长如何驱动网络结构的演化，另一些工作则 研究不同种类的网络拓扑结构如何影响发生于其上的交通动力学。由于现代通讯 网络的度分布呈p o w e r - l a w ，我们在s c a l e f r e e 网中研究如何充分利用网络减缓交 通拥挤。 据估计美国有一半以上的劳动力致力于信息领域，而不是狭义上的买卖。因 此，在网络中传递的信息也存在着堵塞现象。这种堵塞现象不仅存在在互联网、 万维网络中，也存在如货物运输或邮局服务网络中。信息网络中的一个重要问题 是理解如何控制堵塞以及如何使网络正常并高效的运作。 2 1 复杂网络上信息传播的发展历程 复杂网络上的信息传播问题已经得到广泛的研究 4 6 5 8 。在以前的这些模型 中，信息处理器是路由器，它们的作用是把数据包传送到目的地。在计算机网络 中，节点可以作为主机或者路由器。主机可以产生有着固定目的地的信息或者数 据包，同时还可以接收从其它主机上传来的数据包。路由器的作用是找到一条从 信息的产生点到目的地的最短距离，并且在每个时间段将数据包沿着最短距离向 着目的地传送一步。最短距离是有着最少连线的一条路径。以前的研究主要针对 三种不同的计算机网络模型：( i ) 网络边上的节点作为主机，内部的节点作为路 由器 5 1 1 。( i i ) 所有的节点都既作为主机又作为路由器 5 2 ，5 5 ，5 6 ，( i i i ) 一部 分节点作为主机其它的节点作为路由器 5 3 ，5 7 ，5 8 。 第二章复杂网络中的信息传播 图2 1 1 ：二维格子模型，网络中节点分为两类：图中灰色格子为主机，负 责产生和接收信息，圆圈作为路由器，负责存储和传播信息 5 3 】。 图2 1 2 ：二维格子模型，网络中节点分为两类：图中边上的节点( 格子) 作为 主机，负责产生和接收信息，内部的节点( 圆圈) 作为路由器，负责存储和传播信 息【5 2 】。 瓣窳 图2 1 3 ：在【5 9 】中，研究了一维格子，二维格子以及c a y l e y 树的几种模型 但是这些模型主要是在二维格子【5 1 5 4 ，5 7 1 采1c a y l e y 树 5 4 - 5 6 】的网络结 构上研究的。c a y l e y 树模型只包含两个要素( 1 ) 待传输的信息包( 2 ) 传输渠道，虽 第二章复杂网络中的信息传播 然这个模型比较简单，但是它包含了信息传输的一些主要特点。 图2 。1 4 ：一个典型的c a y l e y 树模型，( 3 ，4 ) ，代表分支为3 ，层数为4 。 以前的工作 4 6 5 8 ，6 0 6 7 认为每个节点的能力都是一样的。也就是说，每 个节点有相同的信息产生和传输几率。这种模型对于描述现实的网络例如因特网 来说太过于简单化了。就我们所知，在因特网中，很多用户既可以是个人也可以 是大的公司或企业。对于前者来说，不同的个人有不同的产生和传播率；对于后 者，不同的公司或企业大小不同，因此也应该有不同的产生几率和传输几率。 因此，我们采用了一个l i u 模型【6 8 】，该模型主要包含两个因素： ( 1 )单位时间内每个节点产生的数据包数目与它的边数成正比即南五。其 中毛是节点的边数，旯为每条边产生的一个数据包的几率。 ( 2 )就传输方面而言，每个节点在单位时间内最多能传输1 + 夕致个数据 包，其中口0 为调节参数。因此该模型代表了在一个在一般的网络 中，每个节点有不同产生和传输能力的信息传播模式。 2 2 网络动力学模型 “u 模型的动力学过程如下： 1 、在每个时间段t ，节点i 以几率毛旯产生一个数据包，如果节点i 上已经有等 第二章复杂网络中的信息传播 待传输到目的地而经过该节点的数据包，那么这些新产生的数据包将放在队列的 最后面。 2 、在每个时间间隔t ，节点i 可以最多将( 1 + 芦甄) 个数据包向前传输一步，一旦 数据包到达目的地，则从该网络中移走。 3 、当某个新的数据包产生后，它的目的地及产生时间都被记录下来。目的地在 网络中随机选择产生，路由器负责找到一条从源点到目的地的最短距离，在以后 的时闯中，数据包将沿着这条最短路径前移。如果同时有几条最短路径，那么就 选择一条有着最少等待的数据包的站点。 4 、在每个时间段，如果某个节点待传输的数据包数目大于1 4 - 阮，那么队列中 的前面( 14 - 后。) 个数据包将朝着目的地向前移动一步，并且放在节点队列的最 后面。如果等待的数据包数目小于