（物理电子学专业论文）短信网络拓扑结构及演化模型研究.pdf

短信网络拓扑结构及演化模型研究 摘要 自然世界和人文世界中存在大量的复杂系统，复杂网络系统是其中 最重要的一种表现形式，如i n t e m e t 网络，w w w 网络，计算机网络，e m a i l 网络等。这些网络的拓扑结构形式有着纷繁复杂的表现，这在近几年引 起了各领域学者的广泛关注，由此也引发了复杂网络的研究热潮。更为 许多专家学者所关注的是，这些网络的演化形式及过程，由于研究对象 规模庞大，计算复杂，跟踪和研究网络的演化成为这一领域的研究难点 和热点。 随着个人移动通信技术的快速发展，目前中国大陆已经拥有超过3 5 亿的手机用户，其中文本短信更是己迅猛的速度成为移动通信用户的一 种重要的通信方式，据统计仅0 5 年春节7 天长假全国手机短信发送量就 达1 2 0 亿条左右。从2 0 0 0 年的发送总量为1 0 亿条，到2 0 0 5 年的3 0 4 6 亿条，我国手机短信发送量6 年增长了3 0 0 多倍。对短信网络的研究不 仅对国民经济发展有着重要的意义，同时对短信网络的研究可以使我们 更清晰的认识和理解移动通信网络的结构模式和演化特点。 本论文研究的内容主要分为两个部分，一部分研究了短信网络的拓 扑结构，另一部分研究了短信网络的演化特点。 首先介绍目前世界上对复杂网络研究的进展与基本理论，介绍复杂 网络的一些基本概念，引出目前学术界最关注的几种复杂网络形式，如 随机网络，小世界网络，s c a l e f r e e 网络等几种网络模型的构造，然后引 入复杂网络研究的最主要的几种度量，如网络中度的概念，最短路径的 概念，成簇系数等等。 然后重点介绍目前学术界最关注的b a 模型，主要介绍b a 模型的演 化方式，目前学术界对b a 模型的讨论都集中于其演化方式上，即许多 网络虽具有幂律的度分布，但其网络演化却与b a 模型有着很大的不同。 然后引入短信网络的概念，所有数据均来源于实际的运营商网络， 我们发现，短消息网络具有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 有着基本吻合的特征，但是实际网 络演化模式却大相径庭。 关键字：复杂网络，短信网络， s c a l e f r e e ，网络演化，b a 模 型，度的分步，成簇系数，最短路径 i i s m sn e t w o r km o d e la n de v o l v e m e n t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to nt h et e c h n o l o g yo fc e l l u l a rp h o n e s ，s h o r t m e s s a g e ( s m ) h a v e b e c o m eo n eo ft h em o s t i m p o r t a n tw a y s i n c o m m u n i c a t i o n b ym a k i n gu s eo fr e a ld a t a w ec o n s t r u c ta ne v o l v i n gs h o r t m e s s a g es e r v i c e s ( s m s ) n e t w o r k w 色f i n dt h a tt h es m sn e t w o r ki s a s c a l e f r e en e t w o r k b yi n v e s t i g a t et 1 1 em e a nc o n n e c t i v i t ya n dt h em e a np a t h l e n g t hofs m sn e t w o r k ，w ef m dt h a tt h e r ea r et w od e s c r i p t i o n sb a s e do n d i f f e r e n tt i m em e a s u r e t h en u m b e ro fn o d e so rt h en u m b e ro fe d g e s - r e p r e s e n t i n gd i f f e r e n ts t a g e so f t h es m sn e t w o r k se v o l u t i o n t h i st e x tr e g a r d st h en e t w o r ko ft h ec o m m u n i c a t i o nb a s e do ns m sa st h e r e s e a r c ho b j e c t ，a n da n n o u n c et h a tt h ec o m p l i c a t e dn e t w o r kc h a r a c t e r i s d ci n t h ec o m m u n i c a t i o nn e t w o r ke s p e c i a l l yi nm o b i l ec o m m u n i c a t i o nn e t w o r ki n t h er e a l i s t i cs o c i e t y , w er e g a r dt h e p e o p l ew h os e n ds m sa sn o d e o f n e t w o r k e v e r yp e o p l eh a v es m se x c h a n g e ds e tu pt h er o u t ea m o n gt h e m w e u t i l i z em a t r i xt o e x p r e s s 也i sn e t w o r k a n dh a sc a l c u l a t e dt h en e t w o r k p a r a m e t e r s ，s u c ha sd i s t r i b u t i o no fd e g r e eo ft h en e t w o r k ，c l u s t e rc o e f f i c i e n t ， n e t w o r kd i a m e t e ra n dt h ea v e r a g es h o r t e s tp a t h ，t h er e s u l to fc a l c u l a t i o n s h o w st h a tt h es m sn e t w o r kb e l o n gt os c a l e f r e en e t w o r k t h ea u t h o rb a s i n go nac e r t a i nt i m ea n do n ea r e ah a v er e g a r d e dt i m ea s t h eu n i t ，r e d u c e dt h ef o r m i n gp r o c e s so f t h es m sn e t w o r k , a n dh a sc a l c u l a t e d t h eg r o w t h 谢t ht h en e t w o r k ，m o s tl a r g ed i a m e t e ro fn e t w o r k ，a v e r a g es h o r t e s t p a t h ，p e r c e n t a g ep a r a m e t e ro fn e t w o r kt h a tn o d ew h i c ht a k ew h o l en e t w o r k w i t hc o u r s et h a tt i m ed e v e l o p i tc a nm a k eu sh a v eb e t t e ru n d e r s t a n d i n go ft h ec h a r a c t e r i s t i co fm o b i l e i c o m m t m f i c a t i o nn e t w o r kt h r o u g ht h es t u d y i n gs m sn e t w o r k ，w ec a l la p p l y v a r i o u sk i n d so fa c h i e v e m e n t st h a ts t u d yo fc o m p l i c a t e dn e t w o r ka tp r e s e n tt o t h eo p e r a t i o no fm o b i l ec o m m u n i c a t i o n ，s u c ha si no r d e rt ok e e pt h ec u s t o m e r h e r eb e t c e r , t h eo p e r a t o rs h o u l dp a ym o r ea t t e n t i o nt ot h o s em a i nn o d e si n u s e r sn e t w o r k ，i tc a ne v e nm a k em o r ee f f i c i e n tt h a tp r e v e n tt h ev i r u si nt h e m o b i l en e t w o r kf r o mt r a n s m i t t i n ge t c k e yw o r d s ：c o m p l e xn e t w o r k ，s h o r tm e s s a g i n gs e r v i c e s ，s c a l e f r e e n e t w o r k ，n e t w o r ke v o l u t i o n ，b am o d e l ，d e g r e e d i s t r i b u t i o n ，c l u s t e r i n gc o e f f i c i e n t ， s h o r t e s tp a t h 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担切相关责任。 本人签名：堡丝望日期：墨堑：i ：型 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 1 1 日期：趔：亟挫 日期：垒叠! ! ：鲎 北京邮电火学硕士学位论文 第一章引言 第一章引言 复杂性，这一名词截至目前为止仍然没有一个被大家公认的定义，但大家都能认 同的是，它具有与随机性完全不同的更复杂更丰富的表现形式和特征。对于复杂性的 定义目前业界较为认同的说法是，首先复杂系统必须由大规模的元素所组成，或者说 由大量的“节点”所组成，每个元素或节点都具有各自的动力学特性，但整个系统并 不是简单的由各个独立的系统进行简单的叠加，而是各个节点相互影响，相互制约， 相互作用，从而使整个系统具有极其纷繁复杂的动力学特性。这一特性，有两个关键 点，一个是大量的节点而不是几个或者小规模的数量；另一关键点是，节点问的相互 作用 “。 我们居住的世界是一个接近于混沌的世界，世界如此纷繁复杂。文化，社会，经 济，物理以及我们的生态系统都在进行着不断的演化，不断的被不计其数的因素( 节 点) 所影响。他们的一个共性是大量的因素间的相互作用使系统变得更加复杂 2 1 。近 几年，由许多学科互相渗透融合而形成了一个新兴的学科一复杂性科学。这也是由 简单的相互作用而形成的复杂动力学现象。这些不同的学科领域相互渗透最后形成一 个由其共性复杂性，为研究对象的学科。 利用物理学的一些思想和方法进行其它领域的研究，这就不是简单的纯粹的物理 了，这一思想已经不是新鲜的事物了。物理学家认识到一点，它们的研究思想可以作 为认识一些社会现象的工具。例如，七十年代后期开始，物理学家们开始关注经济学， 地理学，生物学，社会学和生态学。 在复杂网络研究领域内，目前物理学家们都试图提出一种模型，利用该模型可以 解释目前真实世界中的复杂网络现象。他们的目标是揭示掩藏在复杂的网络结构下面 的动力学机制或者说是原理，“上帝之手”究竟是什么? 例如，幂律分布，成簇系数， 随机过程，网络半径等等概念都是物理学家们由复杂网络中挖掘出的可以用来度量复 杂网络特性的物理量纲。 本文的研究并不是试图建立一中全新的复杂网络模型，而是通过对短信网络，这 一真实的动态复杂网络的研究和挖掘，揭示出目前专家学者对复杂网络研究所忽略的 一些因素，信息流的因素。目前的研究者们所关注的复杂网络，大都将注意力集中到 北京邮电人学硕士学位论文 第一章引言 网络的节点，对网络中“边”的意义认识不够，其实复杂网络最大的复杂性并不在于 节点的多少，而在于节点间的相互作用。目前大家最关注的复杂网络是如何产生的问 题，如w w w 是如何形成的，i n t e m e t 的主机是如何连接在一起的，但任何人都无法 重现如此庞大的网络的生长过程，那么我们将如何对这一领域进行研究呢? 通过信 息流，复杂网络上的信息流。通过信息的流动，我们将可以重新发现整个网络的动态 生长过程。也就是说本文给出一个以短信网络为实物模型，以信息流动为研究对象的 全新的复杂网络的研究方法。这不仅仅能够帮助人们更好的认识移动网络的特征，也 对人们进一步研究复杂网络，给出一个全新的视角。 北京邮电大学硕士学位论文 第一章引言 参考文献 1 g i r v a n ，m & n e w m a n ，m e j ( 2 0 0 2 ) c o n u n u n i t ys t r u c t u r ei ns o c i a la n db i o l o g i c a l n e t w o r k s p r o c n a t l a c a d s c i ，9 9 ，8 2 7 1 8 2 7 6 ， 【2 s c h w e i t z e r , f & h e l b i n g ，d ( 2 0 0 1 ) g u e s te d i t o r s i n t r o d u c t i o n a d v c o m p l e xs y s t ， 4 1 - 2 3 北京邮屯大学硕士学位论文 第二章复杂网络综述 2 1 引言 第二章复杂网络综述 我们的世界被不断变化的复杂网络所影响。i n t e m e t 是一个以计算机和路由器为 节点，以他们的连接为边的一个复杂网络：w o r l dw i d ew e b ( w w w ) 是一个以互联 网页为节点，以e t f i j 之间的超文本链接为边一个虚拟网络；e - m a i l 网络，是一个以电 子邮箱为节点，以邮箱间的邮件往来为边的虚拟复杂网络；以及本文所要研究网络实 体，短信网络，是一个以移动电话为节点，以其间的短信往来为边的虚拟网络。这些 网络形式在现在的社会生活中极大的影响着人们的生活，甚至某些人这些网络为生， 有些人以这些网络作为工作生活工具，失去了这些网络，他们就无法生存。总而言之 这几种网络极大的影响着人们的生产生活，其中的短信网络由于其独特性，它是以移 动通信为基础的网络形式，也是目前人们关注的焦点。 尽管无论是i n t e m e t ，w w w ，e m a i l 网络还是短信网络，都属于人造网络，但 是它们与生命体中的网络，如神经网络，蛋白质网络等有许多共性。但无论哪种网络 我们对他们的认知都是有限的。更好的理解人造网络，无论是对提高网络安全性，增 加网络容量，提高网络的运行效率都是有着重大的意义的，如果我们更好的认识这些 人造网络，我们就可以对网络病毒的传播行为有更好的认识，从而更好的预防病毒的 传播：如果我们更好的认识网络结构及其演化特点，我们就可以在资源消耗不变的情 况下，大大的提高我们的网络容量；同时我们可以使我们的网络变得更通畅，更有利 于信息的流动，从而更好的提高网络的执行效率川。另一些，在我们生活中，对我们 生活有着巨大的影响的网络如细胞网络，社会生态学网络，电话网络，论文引用网络， 电力网络和语言网络等也都属于复杂网络1 2 ，也具有复杂网络的特性。本文从现在开 始，首先让我们把目光集中在以上这些纷繁复杂的网络形态具有哪些特殊的结构特 征，我们可以发现，尽管网络不同，但是他们却有着令人惊讶的共同的网络结构特点。 这些人造的和自然的网络结构都具有哪些特征呢? 潜伏在这些网络下的物理特 征都有哪些呢，具有极其紧密结构和鲁棒性的i n t e m e t 是随机网络吗? 目前的一致看 法是在每个复杂网络系统下面都存在着一个非随机的网络拓扑结构特征1 3 】。这是目前 绝大多数物理学家对该领域进行研究的着眼点或者说是切入点。目前大家遇到的最大 北京邮电大学硕士学位论文第二章复杂网络综述 挑战是揭开隐藏在成百上千的混沌的节点和边之中的网络模型特点。复杂网络的研究 涉及的领域很多，如计算机科学，数学，工程学，生物学，物理学，经济学，社会学 等。然而我们发现，在研究网络节点的相互作用的时候，统计物理成为一个非常有用 的分析工具，利用统计物理这一工具，人们从宏观上研究网络要素间的相互作用，从 微观角度研究网络的节点。利用统计工具，人们目前更感兴趣的是网络间的结点是如 何相互作用的，比如谁与谁相互作用。当网络中的结点是唯一的，不可替换的，如人 类，蛋白质而不是那些可以相互替换的，比如电子，原子等，我们就必须清楚谁作用 于谁【4 j 。而某些网络，我们只要清楚谁和谁作用即可，本文所关注的短信网络，我们 暂时不考虑网络的方向性问题，而是仅仅考虑网络的相互作用。 复杂网络的研究由于以下方面的进展，在最近几年有了很大突破【2 1 ： 用于研究巨型网络的大规模数据库技术的出现； 计算机的计算能力不断提升； 各学科的不断渗透以及学科边界被不断打破： 全局化的观点，人们将复杂系统看作一个整体的系统进行研究 2 2复杂网络的定义 网络通常的表述方法是用图来表述，通常由1 个节点和m 条连接这些点的边所 组成，边可以是带方向的，也可以是不带方向的。由于本文中只考虑不带方向的边， 故表示连接节点“和节点v 的边e 。和边p 。代表相同的意义。 珏= 4 v e r t i c e s m = 4 e d g e s 一 图( 2 - 1 ) 这是一个示意性的网络，它有 = 4 个节点( “，v ，z ，y ) 和m = 4 条边 ，e 。，e v y ，e u v ) 表示网络的图的结构信息用临接矩阵b 来表示，如果节点f 与节点j 存在着连接 的边，那么矩阵上相应位置上b 。我们就用1 来表示，如果不存在连接我们就用0 来 表示，显然一个无向图的临接矩阵具有对称结构。 北京邮电大学硕士学位论文 第二章复杂网络综述 2 3 网络的拓扑结构 如果要想深入理解网络的内在特征，我们就不得不谈到三个概念：网络的度数， 网络的成簇系数和网络的最短路径。 2 3 1 节点的度 度盔代表节点v 所连通的边的数目，也等价于该节点所有的邻居的数目。节点的 度的概念在物理领域中代表节点的局域连通性。度岛可以由临接矩阵的矩阵表达式中 推导出来： t = ( 曰2 ) 。= 岛 ( 2 - 1 ) - 1 还有一个节点度的扩展概念，节点度的分布，度的分布用分布函数p 倍) 来表 示，p 倍j 表示网络中的节点具有七条边或者七个邻居的随机分布概率。节点度的分 布是整个网络的基本统计特性，表征网络的全局连通性。 2 3 2最短路径 在这里我们首先定义所有边的长度都为1 。路径长度是指从某一节点沿该网络到 达另一节点所经过的距离，在本文中也就是指从一个节点到达另一个节点所经过的边 的数目。最短路径长度f ，是从节点i 到节点，的最短的路径长度，也就是经过的最少 的边的数目。它是以边长作为长度单位进行度量的拓扑距离。路径长度的分布p 何 是所有节点对之间最短路径的统计分布特性。一个集团是指一系列连接在一起的节点 的集合，如果一个用来表示网络的图只包含一个集团，那么我就说该图是连接的。当 一个图是连接的，我们就存在着这样一个概念，平均最短路径长度f ，他表示该图的 任意两点的最短路径集合( 如) 的平均值。在这里，我们可以把，定义为图的直径。 然而在其他的文献中也有把图的直径定义为最大的最短路径长度的。由此我们可以定 义，当一个节点具有最小的到达其他节点的最短路径长度时，我们称此节点为该图的 中心节点。平均最短路径长度是对所有节点对之间最短路径长度的平均值，是网络的 特征尺度，表征网络的连通性。 另外还有一个较近似的概念被称作介数( b e t w e e n n e s s ) h ，这一概念是由g i r v a n n e w m a n ( 2 0 0 2 ) 提出的。介数的定义是，某一节点被其他的节点的最短路径所经过 的次数，这一物理量可以衡量网络中节点对网络联通性的贡献度。相应的具有最高介 北京邮电大学硕士学位论文第二章复杂网络综述 数值的节点被称作网络的中心节点。 2 3 3成簇系数 成簇系数c 是表示图中某一节点的两个最近邻同时也是其他节点最近邻的概率。 在图中，这样一种关系就形成了一个三角形，见如图( 2 2 ) 。很高的成簇系数反映在 图中就是具有很多的三角形。一个通用的成簇系数的定义由n e w m a n ( 2 0 0 2 ) 4 1 给出如 下： c = 3 ( 2 2 ) 川口 这里n 。代表图中的三角型的个数，n 。是图中所有相连的三个点的组合的个数， 这种三点集合，存在着方向性，如图( 2 2 ) 中间的连接起始点分别为x ，y 和v 时三 点的集合是不同的，虽然他们都是由x ，y 和v 组成。公式中的因子3 作用是将一个 三角形转换成三个三元组( 三个节点的集合) 这一因子也将成簇系数的取值范围限制 在了o 1 之间。在我们的短信网络中，节点代表使用移动终端的人，边代表两个人存 在着短信往来。成簇系数代表的含义就是，当某一终端用户与其他两用户存在短信往 来的时候，另一用户也同这两用户存在短信往来。由此我们可以看出，最短路径属于 网络的全局属性，成簇系数代表网络的局部属性。 图( 2 - 2 ) 计算一个具有m = 4 个节点，n = 4 个边的图的成簇系数的方法如下：图中有一个三角形和 五个相连的三角，其中的三个三角在图中用箭头表出，另外两个三角，如果移动内部箭头的起始 位置也可以得到，也就是把一v 起始的前头分别换成以x 和以y 起始。那么成簇系数我们利用方 程( 2 - 2 ) 可以计算得到为3 5 。 网络中的三角形的个数n 可以有邻接矩阵直接计算得出，这里t r 代表邻接矩阵 对角线上的元素和 1 扎= 柏3( 2 3 ) d 此外还存在着一种定义成簇系数的方法【”，若z ；是节点f 的最近邻节点的数目， 1 北京邮电大学硕士学位论文第二章复杂网络综述 这些最近邻节点之间全部可能的连通的边数目为并( z f l 1 ) 1 2 ，若y ( o 是这些近邻 之间实际存在着的连通边的数目，则把节点i 的成簇系数c ( 。定义为： c - - y 化乳z p - 1 ) 2 1( 2 4 ) 成簇系数c ( 1 表征了节点f 附近环境的连通性。平均成簇系数c 是对网络上全部 节点的c ( c 进行平均所得到的平均值，表征了整个网络的平均的“成簇性质”。 2 3 4 网络模型 自然界中的网络有一些共同的特征，如很高的聚集性，较小的网络半径，而度的 分布往往不同于随机图中的度的分布( w a t t s s t r o g a t z ，1 9 9 8 ；b a r a b f i s i & a l b e r t ， 1 9 9 9 ；k l e m m & e g u i l u z ，2 0 0 2 ) 6 - 8 1 我们经常可以发现某些具有一定斜率特征的度的分 布形式。人们都在试图找到一种简单的网络模型，可以重现这些自然界中的网络的形 成过程。目前在网络模型建立方面的研究已经产生了一些突破性的进展，目前最主要 的三个网络模型是：随机图理论，小世界模型，s c a l e f r e e 模型。 2 3 5随机网络 随机网络模型时由e r d s s r e n y i 在1 9 5 9 年提出的翻，目前已经发展为数学中非 常重要的一个分支，在交通，通信，计算机科学技术等许多工程实际领域都有很重要 的应用。随机网络理论在复杂网络研究中也扮演着举足轻重的作用。见图( 2 3 ) 图( 2 - 3 ) 图中的网络为n = 2 4 个节点，m = 6 0 条边的网络，相应的系数p = 0 2 2 。该网络是用e r 模 型的生成方法产生，该图的平均度数 = 5 。 随机图理论最早提出的成形的网络模型， n 个固定的节点，刀个边是从p 堕娶尘 随机图网络定义如下： 个可能边中随机选取。连通概率p 是指 j ! 型! 皇奎耋至圭兰竺垄蝥；一；一一一；一； ；垒耋墅坚蝥垒 任意两个节点相连接或者说这两个节点间存在边的概率 p ：栉 塑攀】( 2 - 5 ) 由n 个节点和肝个随机边可构成c ：( 。) 2 个等价的构型。 节点度的分布p 例( b o l l o b a s ，1 9 8 1 ) 【10 】是一个二项式： 尸( 女) = 蝶一l p ( 1 一p ) “1 。( 2 6 ) 为二项式分布，当n 很大时，近似为p o i s s o n 分布，如图( 2 - 3 ) 所示 m 一“等( 2 - 7 ) - p n ( 2 - 8 ) 这里 表示平均度的分布。 图( 2 - 4 ) 当n 很大时，随即网络度的分布近似于p o i s s o n 分布，该图中横坐标k 代表度数，纵坐 标是经过归一化后的度的概率分布值。 随机i 羽被人们广泛深入地研究过，其中一个重要的结论就是当 i n ( n ) 时整体 网络是处于一个连接状态的1 1 一( d o r o g o v t s e v & m e n d e s 2 0 0 2 ；b a r a b 缸i & a l b e r t ，2 0 0 2 ) ，此时网络的半径为 乙d i n n i n ( 2 - 9 ) 成簇系数是： ：p “尘( 2 1 0 ) 凡 随机网络有比较小的半径，这一特征与许多自然界中的网络相似，见表( 2 一1 ) 。 9 北京邮电大学硕士学位论文第二章复杂网络综述 但我们可以注意到公式( 2 - 9 ) 中，当网络规模非常大的时候，成簇系数几乎是可以忽 略的，这一特征与自然界中许多实际网络的的特征却有很大的出入，如表( 2 1 ) ，现 实世界中的许多网络都有很高的成簇系数。 n e t w o r kn ( k ) i k | dgg 删 r e f e r e n c e w w w ( s i t el e v e l ) 1 5 3 1 5 73 5 23 13 3 50 1 10 0 0 0 2 3 a d a m i c ( 1 9 9 9 ) i a t e m e t ( 1 9 9 9 ) 5 2 8 7 3 83 76 20 2 10 0 0 1 v 矗z q u e ze t a l ( 2 0 0 2 ) c e l e g a 船( a e u r a l ) 2 8 21 42 6 52 2 50 2 80 ，0 5 w a t t s s l r o g a t z ( 1 9 9 8 ) p o w e f 蛳d ( u s ) 4 9 4 1 2 6 71 8 7 1 2 _ 4 0 0 80 0 0 5 w a t t s s u x ) g a t z ( 1 9 9 8 ) 表( 2 1 ) 表中显示了真实世界中许多网络的平均路径长度和成簇系数。图中n 代表网络的节点数 目，即网络规模。 代表平均度数，l 代表平均路径长度，代表具有相同的路径节点数目n 和度数 胁的利用e - r 模型构造的网络的平均路径长度。c 代表成簇系数，c ，“代表利用e - r 模 型构造的具有相同 和 抄的网络的成簇系数。 网络拓扑结构随p 变化的规律【1 1 1 ( b o l l o b a s ，1 9 8 5 ) 如下 ( 1 ) 已含有k 个节点和1 条边的任意子图出现的临界概率p czn 4 “( 2 - 11 ) 对于k 阶树：，= 一l 靠( ) n “1 对于k 阶环： ，= k p c ( 忉 r 1 对于七阶完全图： ，：丛冬尘p c 。c n - 2 ( t - n z ( 2 ) 若把连通概率表达为：p ( ) * n 2 ，其中z 是一个可调参量，可以取值一 一到0 ，则为图( 2 5 ) 所示，可以得到 图( 2 5 ) 当z - 3 2 时，全部图只包含孤立的节点；当z = - 3 2 时，1 阶树突然出现；当z 。一1 时， 环突然出现：当z = - 2 3 时，完全图突然出现 ( 3 ) 由于 扮= p n ，则 当 辂 j 时，最大子图是树： 当 眵= j 时，子图是环的复杂结构： 当 时，出现巨大的连通图，随着 0 时，在网络上引入无序，扩展了度分布，同时 保持平均值 扮= 芷，即在 扮= 定处有一个峰值，如图( 2 1 1 ) 所示： 图( 2 - 1 1 ) 不同p 是pn ，函数图像，这种度分布的形状类似于随机图，即所有节点有近手相同 的k 。集中在嶂值附近，网络的拓扑是相对均匀的。 ( 3 ) b a r r a t ，w e i g t ( 2 0 0 0 年) 【1 9 】得到p 倒的定量表达式为： ，k 、一= k 一 ，( 尼，= 7 篓2 1 c k ，：( ，一p ) ”p k zn i ；兰j ；：；i 。一，等 c z 2 z ) 对于k k 2 时，f ( k ，k ) = i n i 后一k 2 ，k 1 2 ) ，( 2 - 2 2 ) 式表明，w s 模型的度 分布属于p o i s s o n 类型的函数。 2 3 7s c a l e - f r e e 网络 不久前，b a r a b 出s i & a l b e r t ( 1 9 9 9 ) 1 7 】在对许多真实世界的网络进行研究时发现一 些特别的现象，首先每个节点的度数并不均匀，网络中总是存在几个具有较大度数的 点，另外，他们发现许多网络的度的分布函数呈现出幂律分布的特点。渐渐地人们不 断发现，诸如w w w ，i n t e m e t 网络，分子网络等许多真实世界的网络都呈现出幂律 分布的度的特征。在1 9 9 9 年b a r a b 缸i & a l b e r t ( 1 9 9 9 ) 提出了一种新的网络模型，该 模型的构造方法如下： ( 1 ) 开始时的网络具有较小的节点数目m d ，在每一个时间步长中，向网络增加 一个新的节点，它具有聊( 埘s 嘞) 条边，它是从此新的节点连通到所个不同的老的 节点。 ( 2 ) 当选定新的节点与其连通的老的节点时， 概率i i ，取决于节点i 上的度数墨，即： 毗) 2 轰 假设：新的节点连通老的节点i 的 ( 3 ) 经过t 步骤以后，所生成的新的网络具有n = t + m d 个节点， 我们利用数值模拟的方法可以看到其度的分布服从如下函数： p ( k 1 k 1 r = 3 如图( 2 5 ) 所示： ( 2 2 3 ) 和删条边。 ( 2 2 4 ) 图( 2 - 5 ) 该图是利用上述网络构造方法进行数据模拟的结果：( a ) b - a 模型的度的分布图，该图 中节点总数n = m 。+ t = 3 0 0 0 0 0 ，圆点代表网络的起始点d = = 1 ，方块代表网络的起始点m d = m = 3 ， 菱形代表网络的起始点m o = m = 7 ，图中的点划线是斜率为2 9 的斜线，可以看出拟合的非常好。 图中的小插图是经过归一化的度的分布图，可以看其中的点划线斜率为3 。( b ) 图示显示的是具 有相同的起始点数m 。= m = 5 ，不同的节点个数的度的分布，圆点代表n = 10 0 0 0 0 ，方块, p , , 襄n = 1 5 0 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 e r t ，j e o n g ( 1 9 9 9 年) 7 】从如下方程出发： 鲁一一轰 5 ， 得到如下结果： 置( o ：m ) 4：1 2 ( 2 - 2 6 ) 此式表明：所有的节点的度数都以同样的方式随着时间演化，遵从幂数律，不同 节点的差别是幂数律的截距不一样。 b ) 当r 呻m 时，度分布得到的渐进形式为 p ( 七) 2 7 4 k 。 ，2 石1 + 1 一( 2 - 2 7 ) 与数值模拟结果一致。 ( 3 ) b a 模型指出：出现无标度分布p ( k ) tk 。的必要条件是生长和择优连通两 个因素同时存在。 d ) 当只存在生长因素，连通概率无关时，即：( 置) = _ 三- i ，得到的度 l y , q n + c j 分布为： p ( 七) = 一ee x p ( 一生) ( 2 2 8 ) 即为指数分布形式，如图1 0 a 所示 2 i x 1 矿 图( 2 - 6 ) 该图为两种不同的模型的度的分布，( a ) 对- i - 模_ e da 的度的分布，圆点代表网络的起始 点m d = m = ，方块代表网络的起始点m o = m = 3 ，菱形代表网络的起始点d = m = j ，三角形代表网 络的起始点l t t o = r r i = 7 ，网络尺寸为n = 8 0 0 0 0 0 ，插图为再t = 7 和t = 9 7 分别进入网络的两个节点的 演化形式，点划线的斜率为岛“j = m l nr o + t - 1l ( b ) 为对于模型b 的度的分布，n = 10 0 0 0 ，圆 1 8 北京邮电大学硕士学位论文第二章复杂网络综述 点代表t = n ，方块代表t = s n ，菱形形代表t = 4 0 n ，插图为两个节点度数的时间演化。 路径长度 ( 1 ) 数值模拟结果如图( 2 7 ) 所示：b a 模型中的平均路径长度，在任何n 值时， 都比随机图小，这表明：无标度网络的非均匀拓扑比随机图中的均匀拓扑，更有效与 使节点之间接近。 图( 2 - 7 ) 图中是由b a 模型构造的s c a l e f r e e 网络中，平均最短路径长度随网络尺度的变化而变 化。与之对比的是相同网络规模的随机图的平均最短路径长度的变化情况。 成簇系数 ( 1 ) 数值模拟结果