（光学专业论文）复杂网络可靠性研究.pdf

复杂网络可靠性研究 摘要 我们接触的许多自然和人造的网络都属于复杂网络，例如，计算 机网络，i n t e m e t 网络，w w w 网络，人际关系网等。这些网络与我们 的日常生活密切相关所以我们有必要深入研究和更深刻的理解这些 复杂网络的性质，包括网络的拓扑结构、运行机制、动力行为、同步 能力、抗干扰能力等，以便更好的设计和管理这些实际的复杂网络为 我们服务本文所研究的复杂网络可靠性对于网络结构优化、防备病 毒攻击和防治流行病等方面，都具有十分重要的意义。本文基于复杂 网络中典型的网络模型随机网络和s c a l e f r e e 网络模型来研究复杂网 络的拓扑结构参数对其可靠性的影响，以及复杂网络同步特性的可靠 性，并简单介绍相关理论在通信网络中的指导作用。 本论文从以下几个方面展开：首先总结了复杂网络研究的历史现 状和研究成果；其次，研究复杂网络拓扑结构参数对其可靠性的影响； 再次，研究复杂网络同步特性的可靠性。最后，介绍复杂网络可靠性 理论在通信网络建设中的运用。 文章首先介绍目前世界上对复杂网络研究的进展与基本理论，在 技术上给出了复杂网络的定义，介绍了复杂网络的一些基本刻画量， 比如网络中度的概念以及网络度分布、最短路径、聚集系数等；涉及 到的复杂网络网络模型，如随机网络，s m a l l w o r l d 网络，s c a l e f r e e 网络，局部演化网络等几种网络模型的构造和常用模型。同时，结合 复杂网络的自身特点，总结了复杂网络常用的研究方法。 然后，以有代表性的随机网络和s c a l e f r e e 网络模型为基础，以平 均最短路径和平均聚集系数两方面为评价标准，通过对网络进行随机 攻击和选择攻击讨论网络被攻击后其性能的变化，对应的讨论了复杂 网络的容错性和抗攻击性。 再对复杂网络的同步特性的可靠性进行分析。以网络所对应的邻 接阵的第二大特征值作为判断依据，对复杂网络同步特性受到随机攻 击和选择攻击的影响进行分析，得到复杂网络同步的容错性和抗攻击 性随着网络参数的变化关系。 最后，对复杂网络同步理论在通信网中的应用进行简单介绍。 复杂网络同步理论在通信网络的灾害控制和网络的优化构建方面都 具有指导意义。 关键字：复杂网络，随机网络，s c a l e f r e e 网络，聚集系数，最短路 径，同步可靠性 r e s e a r c ho nc o m p l b xn e t w o r k s d e p e n d a b i l i t y m a n yn a t u r a la n dm a n m a d en e t w o r k sa r ec o m p l e xn e t w o r k s f 0 r e x a m p l e ，i n t e r n e tn e t w o r k ，w w wn e t w o r k ，c o m p u t e rn e t w o r k ，e t c t h e s e n e t w o r k sh a v ea f f i n i t yi no u rl i f e ，t h e r e f o r ei ti sn e c e s s a r yt op r o f o u n d r e s e a r c ha n dc o m p r e h e n dt o p o l o g ys t r u c t u r e ，r u nm e c h a n i s m ，d y n a m i c s a c t i o n ，s y n c h r o n i z a t i o na b i l i t y , a n t i - j a m m i n ga b i l i t yo fc o m p l e xn e t w o r k s ， f o rb eb e t t e rt od e s i g na n dm a n a g et h e s ef a c tn e t w o r k s r e s e a r c h i n g a n t i - a t t a c k i n gc a p a b i l i t y o fc o m p l e xn e t w o r k sh a v eq u i t e i m p o r t a n t m e a n i n gf o rp r e v e n t i n gv i r u sa t t a c ka n dd e f e n d i n ge p i d e m i c ，e t c t h i sp a p e ri sd i v i d e di n t of o u rp a r t s ：f i r s t l y , t h eh i s t o r ya n da c t u a l i t y i nt h es t u d yo fc o m p l e xn e t w o r k sw e r es u m m e du p s e c o n d l y , t h er o b u s t o fa n t i - j a m m i n gi nc o m p l e xn e t w o r k sw a sd i s c u s s e d ，b y r e s e a r c h i n g r e l a t i o no fe r r o r - - t o l e r a n c ea n da t t a c k i n g - t o l e r a n c ew i t hs i z ea n da v e r a g e d e g r e eo fc o m p l e xn e t w o r k s t h i r d l y , c o m p l e xn e t w o r k s s y n c h r o n i z a t i o n a b i l i t ya f t e ra t t a c k i n gw a sd i s c u s s e d t h e n ，a p p l i c a t i o nd e p e n d a b i l i t y t h e o r yo fc o m p l e xn e t w o r k si nc o m m u n i c a t i o n sn e t w o r k sw a si n t r o d u c e d e v o l v e m e n ti nr e s e a r c h i n ga n dt h eb a s i ct h e o r yo fc o m p l e xn e t w o r k sa r c i n t r o d u c e df i r s t ；i nt h i sp a r t ，s o m eb a s i cc o n c e p t sa r ep u tf o r w a r d e d ，s u c h a sr a n d o mn e t w o r k ，s m a l l w o r l dn e t w o r k ，s c a l e f r e en e t w o r k ，a n db r i n g f o r w a r dt h em o d e lo ft h o s en e t w o r k s t h e ns o m em e a s u r e m e n t si n s t u d y i n gc o m p l e xn e t w o r k sa r ei n t r o d u c e d ，s u c ha sd e g r e ei nn e t w o r k s , s h o r t e s tp a t ha n dc l u s t e r i n gc o e f f i c i e n t ，e t c t h e n ，t h ec a p a b i l i t ya f t e ra t t a c k e dw a sj u d g e db ya v e r a g es h o r t e s t p a t ha n da v e r a g ec l u s t e r i n gc o e f f i c i e n tb a s e do nr e p r e s e n t a t i v em o d e lo f c o m p l e xn e t w o r k s ，c o n n e c t i v i t y i sa n i m p o r t a n t s t a n d a r d f o r d e p e n d a b i l i t yi nt h i sp a r t a f t e r , s y n c h r o n i z a t i o na b n i 哆i sd i s c u s s e d 嬲w e l l 蠲t h es e c o n d l a r g e s te i g e n v a l u ew a su s e di nj u d g i n gs y n c h r o n i z a t i o nd e p e n d a b i l i t yo f c o m p l e xn e t w o r k s ；t h er e l a t i o ni ns i z ea n da v e r a g ed e g r e eo fc o m p l e x n e t w o r k sa n ds y n c h r o n i z a t i o nd e p e n d a b i l i t yo fc o m p l e xn e t w o r k sw e r e d i s c u s s e d f i n a l l y , d e p e n d a b i l i t yt h e o r yo fc o m p l e xn e t w o r k sa p p l i c a t i o ni n c o m m u n i c a t i o n sn e t w o r k sw a s i n t r o d u c e d d e p e n d a b i l i t y - t h e o r y o f c o m p l e xn e t w o r k sa f f e c tc o n t r o l d i s a s t e ra n do p t i m i z i n gi nc o m p l e x n e t w o r k s k e y w o r d s ：c o m p l e xn e t w o r k ，r a n d o mn e t w o r k ，s c a l e - f r e en e t w o 啦 s h o r t e s tp a t h ，c l u s t e r i n gc o e f f i c i e n t ，s y n c h r o n i z a t i o nd e p e n d a b i l i t y 北京邮电大学硬+ 学位论文目录 目录 第一章复杂网络概述l 1 1 引言l l2 复杂网络的定义2 1 3 复杂网络的刻画3 1 4 复杂网络模型5 1 5 复杂网络的研究方法1 5 1 6 小结1 6 第二章复杂网络结构参数对可靠性的影响1 7 2 1 引言1 7 2 2 复杂网络建模和可靠性评价1 8 2 3 复杂网络的结构参数1 9 2 4 网络的结构参数和可靠性的关系2 0 2 5 小结2 7 第三章复杂网络同步的可靠性分析2 9 3 ，l 引言2 9 3 2 网络同步理论2 9 3 3 数值计算结果及分析3 l 3 4 小结3 8 第四章复杂网络可靠性理论的指导意义4 0 4 ，l 引言4 0 4 2 可靠性理论对通信网优化的指导作用4 0 4 3 可靠性理论对网络病毒防治的指导作用4 1 第五章总结4 6 参考文献4 7 攻读硕士期间发表的论文5 0 致谢5 1 【符号说明：本文第二，第三章中不区分n 和，都表示网络中接点数；畦， 和k a y 都表示网络平均度，c 和c 都表示网络聚集系数。l 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：，二兰j _ j 江日期： 幽12 ：巧 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期问论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：婴：i ：兰兰 日期：嵯盈与一 北京邮电大学硕士学位论文第一章复杂网络概述 1 1 引言 第一章复杂网络概述 近年来，复杂网络引起了许多相关领域研究人员的关注笼统的说所谓复杂网 络就是具有复杂拓扑结构和动力行为的大规模网络例如，i n t e r a c t 网，w w w 网，食 物链网络，科学家合作网络，细胞神经网络，流行病传播网络等都是复杂网络复杂 网络的节点可以是任意具有特定动力和信息内涵的系统的基本单位，而边则表示 这些基本单位之间的关系或联系i n t e m e t 是一个以计算机和路由器为节点，以他 们的连接为边的一个复杂网络；人际关系网是以人为节点，以人与人之间的联系 为边构成的复杂网络；食物网络是以物种为节点，以捕食与被捕食关系为边构成 的复杂网络；这些网络形式不仅仅对于我们进行科学研究很有价值，有的在现在 的社会生活中极大的影响着人们的生活，甚至成为某些人赖以生存的工具和手 段，比如，i n t e m e t 网络，自来水网络，以及供电网络等等；总而言之，复杂网络 极大的影响着人们的生产生活，目前，人们越来越广泛的认识和研究复杂网络， 并且复杂网络的相关理论已经对我们的生产和生活产生了指导意义。由于以上种 种原因，我们有必要去研究这些复杂网络的行为。 尽管无论是i n t c m e t ，自来水网络，供电网络等都属于人造网络，但是它们 与自然网络，如神经网络，蛋白质网络等有许多共性。无论哪种网络我们对他们 的认知都是有限的。更好的理解复杂网络，无论是对提高网络安全性，增加网络 容量，提高网络的运行效率都是有着重大的意义的，如果我们更好的认识这些网 络的可靠性，我们就可以对网络病毒的传播行为有更好的认识，从而更好的预防 病毒的传播；如果我们更好的认识网络结构及其演化特点，我们就可以在资源消 耗不变的情况下，大大的提高我们的网络容量；同时我们可以使我们的网络变得 更通畅，更有利于信息的流动，从而更好的提高网络的执行效率。过去的研究【1 4 j 发现，尽管网络不同，但是他们却有着令人惊讶的共同的网络结构特点。 复杂网络的研究只有几十年，理论还很不完备，所以我们很难对复杂网络给 出确切定义，但是可以对复杂网络的一些要素进行总结；首先复杂系统必须由大 规模的元素所组成，或者说由大量的“节点”所组成，每个元素或节点都具有各自 的动力学特性，但整个系统并不是简单的由各个独立的系统进行简单的叠加，而 是各个节点相互影响，相互制约，相互作用，从而使整个系统具有极其纷繁复杂 的动力学特性。这一特性，有两个关键点，一个是大量的节点而不是几个或者小 规模的数量；另一关键点是，节点问的相互作用。这是目前绝大多数物理学家对 该领域进行研究的着眼点或者说是切入点。目前大家遇到的最大挑战是揭开隐藏 北京邮电大学硕士学位论文第一章复杂网络概述 在成百上千的混沌的节点和边之中的网络模型特点。 利用物理学的一些思想和方法进行其它领域的研究，这就不是简单的纯粹的 物理了，这一思想已经不是新鲜的事物了。物理学家认识到一点，它们的研究思 想可以作为认识一些社会现象的工具。在复杂网络研究领域内，目前物理学家们 都试图提出一种模型，利用该模型可以解释目前真实世界中的复杂网络现象。他 们的目标是揭示掩藏在复杂的网络结构下面的动力学机制或者说是原理，例如， 幂律分布，聚集系数，随机过程，网络半径等等概念都是物理学家们由复杂网络 中挖掘出的可以用来度量复杂网络特性的物理量纲。 复杂网络的研究涉及的领域很多，如计算机科学，数学，工程学，生物学， 物理学，经济学，社会学等。我们发现，在研究网络节点的相互作用的时候，统 计物理成为一个非常有用的分析工具，利用统计物理这工具，人们从宏观上研 究网络要素间的相互作用，从微观角度研究网络的节点。利用这一工具，我们深 入研究和更深刻的理解这些复杂网络的拓扑结构，运行机制，动力行为，同步能力， 抗干扰能力等，更好的设计和管理这些实际的复杂网络对于更好多防备网络攻 击，防治流行病等也具有十分重要的意义。 1 2 复杂网络的定义 究竟复杂网络的定义是什么? 任何一个完备的理论总要能对它研究的对象 给出定义。但是任何一个正在发展的理论并不需要首先给出它所研究的对象的确 切定义。它首先需要的是能够确定哪些可以作为它的研究对象，以及如何对它们 的行为进行刻画当然，综合这几十年的研究，我们可以对复杂网络给出一个技 术上的定义。 1 2 1 从图论角度 设有端集v = v i ，屹以 和边集e e 。，e ：厶，通常由_ ，1 个节点和册条 连接这些点的边所组成，边可以是带方向的，也可以是不带方向的。由于本文中 只考虑不带方向的边，所以表示连接节点和节点，的边e 。和边代表相同的 意义。 2 1 5 2 3 北京邮电大学硕士学位论文 第一章复杂网络概述 图1 - 1 这是一个示意性的网络，它有n = 5 个节点n ，2 3 ，4 ，5 ) 和 m = 4 条边( o n e l ，e 2 3 ，c 2 s ) 节点4 是孤立节点 1 2 2 从矩阵角度 最常用表示网络的图的结构信息用邻接矩阵彳，如果节点i 与节点，存在着 连接的边，那么矩阵上相应位置上4 ；我们就用1 来表示，如果不存在连接我们 就用0 来表示，显然一个无向图的邻接矩阵具有对称结构。本文为了研究复杂网 络同步特性的方便，我们定义的网络用比较特殊的对称邻接阵来表示， a = a i j 1 1 0 1o 。1 00 1 1 a ， 对角线上元素4 一荟4 ，j o 图1 1 可以表示为矩阵 一21 13 o1 0 o l 1 o 01 101 1o0 0oo oo一2 ( 1 - 1 ) ( 1 2 ) 1 3 复杂网络的刻画 如果要想深入理解网络的内在特征，也为了下文叙述的方便，我们就不得不 谈到几个概念：网络的度数，网络的最短路径，网络的聚集系数，临接矩阵特征 值。 1 3 1 节点的度 度岛代表节点f 所连接的边的数目，也等价于该节点所有的邻居的数目。节 点的度的概念在物理领域中代表节点的局域连通性。度岛可以由临接矩阵中推导 出来： 2 荟( 气) ( 1 3 ) 还有一个节点度的扩展概念，节点度的分布，度的分布用分布函数p 倍夕 来表示，p 倍j 表示网络中的节点具有k 条边或者k 个邻居的概率。节点度的分 布是整个网络的基本统计特性，表征网络的全局连通性和节点在网络中的重要 佳，以及网络的均匀性等。 对于如本文所用的( 1 - 1 ) 结构的矩阵，节点的度就是对角元素的绝对值， 3 北京邮电大学硕士学位论文第一章复杂网络概述 孤立节点度值为0 。 此外，复杂网络的平均度也是一个很重要的概念，平均度本文用 表示， = 了k ；n ， ( 1 - 4 ) 钉 网络平均度表征了整体上网络节点平均度数，也就可以用来衡量网络的疏密 程度， 越大，相应网络越密集，反之，网络越稀疏。 1 3 2 最短路径 在这里我们首先设定所有边的长度都为1 。路径长度是指从某一节点沿该网 络到达另一节点所经过的距离，在本文中也就是指从一个节点到达另一个节点所 经过的边的数目。最短路径长度b 是从节点f 到节点，的最短的路径长度，也就 是经过的最少的边的数目。它是以边长作为长度单位进行度量的拓扑距离。路径 长度的分布即) 是所有节点对之间最短路径的统计分布特性。还存在这样一个概 念，平均最短路径长度工，他表示该图的任意两点的最短路径集合t l , j ) 的平均 值。在这里，我们可以把定义为图的直径。然而在其他的文献中也有把图的直 径定义为最大的最短路径长度的。由此我们可以定义，当一个节点具有最小的到 达其他节点的最短路径长度时，我们称此节点为该图的中心节点。平均最短路径 长度是对所有节点对之间最短路径长度的平均值，是网络的特征尺度，可以表征 网络的连通性。 另外还有一个较近似的概念被称作介数( b e t w e e n n e 鼹) b o i ，这一概念是由 g i r v a n n e w m a n ( 2 0 0 2 ) 提出的。介数的定义是，某节点被其他的节点的最短 路径所经过的次数，这一物理量可以衡量网络中节点对网络联通性的贡献度。相 应的具有最高介数值的节点被称作网络的中心节点。 1 3 3 聚集系数 聚集系数c 是表示图中某一节点的两个最近邻同时也是近邻的概率。 设点i 这些近邻之间实际存在着的连通边的数目用e ，表示，则把节点i 的聚集系 数c 。定义为： q - 志 ( 1 - 5 ) 聚集系数c ；表征了节点i 附近环境的连通性。平均聚集系数c 是对网络上 全部节点的c ；进行平均所得到的平均值，表征了整个网络的平均的“聚集性质”， 也可以衡量整个网络的连通性。 1 3 4 临接矩阵特征值 临接矩阵的特征值是用来表征网络同步特性重要参数。对于物理学家而言， 研究复杂网络的最终目标之一是理解网络拓扑结构对物理过程的影响。网络上的 4 北京邮电大学硕士学位论文第一章复杂网络概连 同步是一项重要的研究课题。人们已经观察到的同步现象包括夏日夜晚青蛙的齐 鸣，萤火虫的同步发光，心肌细胞和大脑神经网络的同步；等等。同步特性复杂 网络的重要性质，复杂网络同步特性的重要刻画量就是邻接矩阵的特征值，具体 内容见本文3 2 。 1 4 复杂网络的模型 复杂网络模型研究是一个循序渐进的过程，先是某个网络模型出现并被大家 用来描述网络，随着研究的深入发现现有的网络在某一方面或者某些方面与真是 网络存在比较大的差距，人们就对该网络模型进行修正，当这种修正仍然不能满 足研究需要，人们就试图找到另一种简单的网络模型来研究；当然，因为实际网 络千差万别，所以某一个网络模型很难概括所有的实际网络，这时，就会有几个 网络模型同时在被人们关注。本文主要用随机网络和s c a l e f r e e 网络来研究复杂 网络的可靠性和同步特性等。所以我们有必要对网络模型作简单的介绍：最初是 研究随机网络模型，而且随机网络的e - r 模型一直沿用了近四十年：但是随着研 究的深入，发现实际网络和e - r 随机模型之间有一定的差异，所以仅用随机网络 模型对网络进行描述显然有悖；之后，我们发现实际网络存在小世界现象，所以， 1 9 9 8 年w a t t s s t r o g a t z 提出w - s 小世界模型，目前在网络模型建立方面的研究 已经产生了一些突破性的进展，最主要的网络模型是：随机网络，小世界 ( s m a l l - w o r l d ) 网络，s c a l e f r e e 网络。 1 4 1 随机网络 随机网络模型最初由p e r d 6 s 和r e n y i 在1 9 5 9 年提出的i l l j ，目前已经发展 为数学中非常重要的一个分支，在交通，通信，计算机科学技术等许多工程实际 领域都有很重要的应用。随机网络理论在复杂网络研究中也扮演着举足轻重的作 用。 p = o j 。j 气 一专j j | 。 - 、， - p = o 1 5 p o 1 5 北京邮电大学硕士学位论文第一章复杂网络概述 图1 - 2 图中的网络是用e - r 模型的生成方法产生，反映了随机网络的生成过程，初始是n f f i l 0 的孤立点，分别以p f f i 0 1 和p f f i 0 1 5 连接网络中各最 随机图理论是最早提出的成形的网络模型，随机图网络定义如下： 个固定的节点，甩条边是从【! ! 唑生】个可能边中随机选取。连通概率p 是 指任意两个节点相连接或者说这两个节点间存在边的概率 p 圳【盟掣】( 1 - 6 ) 由个节点和厅条随机边可构成c 品( ，- 1 ) ，：个等价的构型 节点度的分布p ( b o l l o b a s ，1 9 8 1 ) 1 1 2 j 是一个二项式。 p ( k ) - c 熹一。p ( 1 一p ) ”“ ( 1 - 7 ) 当n 很大时，近似为p o i s s o n 分布，如图1 - 3 所示 聃m e - ( 1 1 0 ) 6 北京邮电大学硕士学位论文 第一章复杂网络概述 聚集系数是： 0 1 1 1 随机网络有比较小的半径f 。“* l n o v ) b n 口v ) 1 ；然后对网络中的所以边，以概率p 断开其中一个节点并且重 新连接，所连接的新节点从网络中随机选取，如果所选节点已经与此节点相连， 则再重新选择别的节点继续连接，也就是对每个节点的边，我们以概率p 重连， 保持边的总数目不变，如图( 1 - 4 a ) 所示。 令一种改进的构造方法是n e w m a n w a t t s 模型( 1 9 9 9 年1 f 1 7 1 ，该模型是从一 个具有n 个节点的规则网络开始，以概率p 附加随机边，边的总数目增加，如图 ( 1 - 4 b ) 。这个模型在一定程度上比w - s 模型更容易分析因为这种网络不会造成 孤立的聚集团出现，而且在p 比较小，比较大时，这一模型等同于w - s 模型。 o 霸 r o w i r i n g f l i n k s o 囝 b a d d i t i o o fl i n k s 图1 4 图中有两种方式构造小世界网络模型，方式a ) 是将原来的边进行重联，这样边的总 数目保持不变即平均度数不变，这种方法称为w - s 模型：方式b ) 是保持原来的连接方式的 情况下，增加新的连接，即边数增加，平均度数不再保持恒定，这种方法成为n - w 模型 现在让我们来看看随机重连对网络刻画量平均最短路径l 和平均聚集系数 8 北京邮电大学硕士学位论文第一章复杂网络概述 c 的改变：见图1 - 5 ，图中p 表示重连概率，l ( 0 ) 和c ( 0 ) 分别表示规则网络的平 均最短路径和平均聚集系数；当p = 0 时就是规则网络j p = 1 则为随机网绕对于 0 p 1 的情况存在一个很大的p 的区域同时拥有较大的集聚程度和较小的 最小距离，也就是说0 p 1 ( 1 - 1 3 ) 经过大量数值模拟【3 1 ，琊3 l 得到和p 之间存在关系一p “，其中f = j 坷，并且 d 是n e w m a n w a t t s 模型最初格子的维数，进而得到目前被广泛认可的随着和 p 变化的标度形式为： 9 北京邮电大学硕士学位论文第一章复杂网络概述 工( ，p ) 掣f ( p k n ) ( 1 - 1 4 ) 其中，标度函数，为： 川- 。飘翥羹： m 均 “- p c a r 4( 1 - 1 6 ) n e w m a n ，w a t t s ( 1 9 9 9 年v 1 7 】利用重整化群和级数展开方法，证明此关系。 n e w m a n ，m o o r e 和w a t t s ( 2 0 0 0 年) m 筇1 ，利用平均场方法，得到了标度函数俐 的具体形式q = 1 ) ： ， ) 。了而4t 姐h 了而u ( 1 - 1 7 ) 2 再让我们看看小世界网络的聚集系数c ，对于由w - s 模型所得到的c 随p 变 化规律，如图1 - 5 所示，对于规则网络的c 为： c ( 0 ) 一黼( 1 - 1 8 ) 当k 很大时，c a 大约是3 4 。 由n e w m a n - w a t t s 模型，可得到c 纠表达式为( n e w m a n2 0 0 1 ) 【嬲】 c 硒岽耘( 1 - 1 9 ) 当k 很大时 c ) 2 4 - 1 - 8 p 二- i - 4 p 2 0 - 2 0 ) 当p 加时，c 纠一3 4 小世界网络度分布：( 1 ) 在w - s 模型中，p = o 时，每个节点有相同的k ，因 此度分布是d 函数，中心在k 上。( 2 ) p o 时，在网络上引入无序，扩展了度 分布。同时保持平均信( 七 = k ，即在 = k 处有一个峰值，如图1 - 6 所示： 1 0 北京邮电大学硕士学位论文 第一章复杂网络概述 1 0 1 矿 - 襞 - 鼍爨； 67 9 l ，f 口， - o k 膣 。 图1 - 6 不同p 时p 他，函数图像，这种度分布的形状类似于随机图，即所有节点有近乎 相同的k ，集中在峰值附近，网络的拓扑是相对均匀的 ( 3 ) b a r r a t ，w e i g t ( 2 0 0 0 年) 1 3 3 j 得到p f 动的定量表达式为： ，k 、t 一等一一 p ( 七) - 7 薹l , k ) 。；n ，：( 1 一p y p i k ”：! 妄1 k ； i i e 吾 ( - 2 - ) j ：6博一z 一万j ! 对于k k 2 时，厂氆，k ) 一m i n ( k k 2 ，x ，2 ) ，( 1 - 2 1 ) 式表明，w - s 模型 的度分布属于p o i s s o n 类型的函数。 小世界网络模型虽然解决了随机网络与实际网络之间聚集系数之间的差距， 但是在度分布方面和随机网络模型一样，也是当比较大时，满足p o i s s o n 分布， 但是b a r a b a s i 和a l b e r t 在对实际网络进行统计中意外发现许多实际网络的度分 布都有指数尾巴，而且这种尾巴还有自相似性。所以b a r a b a s i 和a l b e r t 2 4 l 首先 建立b a r a b a s i b e f t 模型( 简称b 诅模型) 讨论网络的这一特性。 1 4 3s c a l e - f r e e 网络 b a r a b f i s i & a l b e r tf 1 9 9 9 ) 在对许多真实世界的网络进行研究时发现一些特别 的现象，首先每个节点的度数并不均匀，网络中总是存在几个具有较大度数的点， 另外，他们发现许多网络的度的分布函数呈现出幂律分布的特点。渐渐地人们不 断发现，诸如w w w ，i n t e m e t 网络，分子网络等许多真实世界的网络都呈现出 幂律分布的度的特征。见图1 7 北京邮电大学硕士学位论文第一章复杂网络概述 图1 - 7n = 1 3 0 ，节点度服从幂指数是3 的幂率分布的s c a l e - f r e e 网络示意图 1 9 9 9 年b a r a b f i s i & a l b e r t ( 1 9 9 9 ) 提出了一种新的网络模型，该模型的构造方 法如下： ( 1 ) 生长：开始时的网络具有较小的节点数目m 口，在每一个时间步长中，向 网络增加一个新的节点，它具有m ( m 硼o ) 条边，它是从此新的节点连接到系 统中已经存在的m 个不同的的节点。 ( 2 ) 偏好依附：当选定新的节点与其连接的老的节点时，假设：新的节点连 接老的节点i 的概率n ，取决于节点i 上的度数跹，即： n ) 。蠢( 1 - 2 2 ) 7 。 经过t 步骤以后，所生成的新的网络具有n - - - t - - m d 个节点，和m t 条边。 首先，我们看看s c a l e - f r e e 网络的度分布。我们利用数值模拟的方法可以看到其 度的分布服从如下函数 p ) “k ” ，- 3 ( 1 2 3 ) 如图1 8 所示： 北京邮电大学硕士学位论文第一章复杂网络概述 k 图1 - 8 该图是利用上述网络构造方法进行数据模拟的结果：( a ) b a 模型的度的分布图，该 图中节点总数n = = 3 0 0 0 0 0 ，0 ，m o = m = 1 ；口，m o = m = 3 ；，m o = m = 7 ；图中的点划线是斜率 为2 9 的斜线，可以看出拟合的非常好。图中的小插图是经过归一化的度的分布图，可以看 其中的点划线斜率为3 ( b ) 图示显示的是m o = m = 5 ，不同的节点个数的度的分布，0 ， - 2 0 0 0 0 ；口，n = 1 2 0 0 0 ；，n = 2 0 0 0 0 0 。其中的插图代表其中两个节点度的演化过程，这 两个点分别在第5 和笫9 5 步进入系统，点划线的斜率为0 5 。 理论进展： b a r a h a s i ，a l b c r t ，j e o n g ( 1 9 9 9 年) i 刎提出连续体理论，并且b a r a b a s i ，a l b e r t 和 j o e n g ( 1 9 9 9 年) 【捌给定点i 的度t 随时间的变化方程，假定t 是连续的实变量， 则疋满足的动力学方程： 扣一轰 m 2 4 ) 由于七= 2 r o t - m , 月f i ，由( 1 - 2 4 ) 推出得到如下结果： k , q ) = 胁( 勺4 卢= 1 2 l i 此式表明：所有的节点的度数都以同样的方式随着时间演化， 不同节点的差别是幂数律的截距不一样。 当t 0 0 时，度分布得到的渐进形式为 州“2 m 1 垆r 一吉小3 ( 1 2 5 ) 遵从幂数律， f 1 2 6 ) 北京邮电大学硕士学位论文第一章复杂网络概述 与数值模拟结果一致。 然后，我们再看平均最短路径 数值模拟结果如图1 - 9 所示：取相同平均度k - - - 4 ，比较相同规模的b - a 模 型和随机网络模型进行比较发现，b a 模型去中的平均路径长度，在任何值时， 都比随机图小，这表明：无标度网络的非均匀拓扑比随机图中的均匀拓扑，更有 效与使节点之间接近。而且b o l l o b a s 和r i o r d a n ( 2 0 0 1 ) 【硐得到分析结果为： 工l n ( ) i n t o ( j r ) ( 1 - 2 7 ) 图1 - 9 图中是由b a 模型构造的s c a l e - 触网络( 0 ) 中，平均最短路径长度随网络尺度的变 化而变化与之对比的是相同网络删莫的随机图( r a ) 的平均最短路径长度的变化情况 聚集系数 ( 1 ) 数值模拟结果如图1 1 0 所示：取b - a 模型和随机网络模型平均度 = 彳 相同，比较随机网络c 。= 朋也得到无标度网络的聚集系数： c ” ( 1 2 8 ) 比随机网络中的c z 一，随着下降的要缓慢一些。 1 4 北京邮电大学硕士学位论文 第一章复杂网络概述 1 0 - 1 1 酽 ) 1 酽 o 严 1 矿 图1 - 1 0 图中为由b - a 模型构造的网络的聚集系数( o ) 随网络规模的变化情况，网络的平 均度数为( k ) 一4 。相应的( 一) 是随机图的聚集系数 ( 2 ) 无标度网络与小世界网络也不同，在小世界网络中，c 不依赖于。 我们可以看到，s c a l e f r e e 网络两个关键因素线性增长和偏好依附导致了这 种网络的模型的几方面特性都与随机网络和小世界网络有很大的不同，它服从幂 律分布的度的特性，更小的网络半径和聚集系数。在近几年的研究中人们发现， 许多真实世界网络的都与s c a l e f r e e 网络有着很强的相似性，如w w w ，i n t e m e t , e - m a i l 网络等。由此说明b a 模型与真实世界的网络模型更近了一步。 1 5 复杂网络的研究方法 图论与统计物理都是研究复杂网络的有力工具。人们最初研究网络所使用的 工具主要是图论，网络作为图论的概念是指由一个点集y f g ) 和一个边集f g ) 组成的一个图，且erg j 中的每条边e ；有y r 回的一对点r u ，vj 与之对应。从 统计物理学的角度来看，网络是一个包含了大量个体以及个体之间相互作用的系 统，是把某种现象或某类关系抽象为个体( 顶点)