（概率论与数理统计专业论文）poisson增长与删除的无标度网络的分析与研究.pdf

中文摘要 摘要：要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就 需要对实际网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模 型。w a t t s 和s t r o g a t z 的小世界网络模型显示了平均路径长度( 刻画节点均距) 和聚 类系数( 刻画局部平均耦合程度) 这两个指标的重要性，而b a r a b i s i 和a l b e r t 在开 创性文章中提出了无标度网络的概念，他们探索了w w w 等几个大型网络的数据 库，实证结果与理论分析表明这些网络的度分布呈幂律形式。同时实证发现，大 量的实际网络都是无标度网络，因此无标度网络是一个值得研究的课题，所以不 断有人对b a 模型进行改进研究。 本文主要是基于b a 无标度网络模型以及前人所做的一些模型的基础上，提出 了几种p o i s s o n 网络模型，主要有节点的增长与连接的删除的p o i s s o n 网络模型、节 点的增长和连接的增加以及连接的删除的p o i s s o n 网络模型，节点的增加和删除的 p o i s s o n 网络模型，通过计算它们的度分布是幂律分布，幂指数范围在1 到3 之间； 同时，本文还提出了节点增加与删除的亚线性增长的p o i s s o n 网络模型，通过分析 表明，这类网络体现了“富者愈富”现象，但稳态平均度分布并不是幂律分布。 关键词：复杂网络；无标度网络；度分布；幂律指数 分类号：0 2 1 1 a b s t r a c t ： a b s t r a c t t ou n d e r s t a n dt h en e t w o r ks t r u c t u r ea n dt h er e l a t i o n s h i pb e t w e e nn e t w o r k sa n d b e h a v i o r sa n dt h u si m p r o v et h en e t w o r k sb e h a v i o rt oc o n s i d e r , o nt h en e e df o rt h e a c t u a ls 仃u c t u r eo ft h en e t w o r kh a v eag o o du n d e r s t a n d i n g ，a n do nt h i sb a s i st oe s t a b l i s h as u i t a b l en e t w o r ks t r u c t u r em o d e l t h es m a l ln e t w o r km o d e li n t r o d u c e db yw a t t sa n d s t r o g a z ，i tr e v e a l st h ei m p o r t a n c eo fa v e r a g ep a t hl e n g t ha n dc l u s t e r i n gc o e f f i c i e n t b a r a b f i s ia n da l b e r tp u tf o r w a r das c a l e f r e en e t w o r kc o n c e p t t h e ye x p l o r e dan u m b e r o fl a r g en e t w o r k ss u c ha sw w w d a t a b a s e ，e m p i r i c a lr e s u l t sa n dt h e o r e t i c a la n a l y s i s s h o w e dt h a tt h ed i s t r i b u t i o no ft h e s en e t w o r k sw a st h ef o r mo fp o w e r - l a w e v i d e n c e f o u n da tt h es a m et i m e ，al a r g en u m b e ro fr e a ln e t w o r k sa r es c a l e - f r e en e t w o r k s ，t h e s c a l e - f r e en e t w o r ki sat o p i cw o r t h yo fs t u d y , s ot h e r eh a v eb e e ni m p r o v e m e n t st ot h e b am o d e ls t u d y t h i sp a p e ri sb a s e dm a i n l yo nt h eb as c a l e f r e en e t w o r km o d e l ，a sw e l la ss o m e m o d e l sb yo u rp r e d e c e s s o r s ，e s t a b l i s h e ds e v e r a lp o i s s o nn e t w o r km o d e l s i n c l u d i n gt h e g r o w t ho fn o d e sa n dt h ed e l e t i o no fl i n k si sp o i s s o np r o c e s sm o d e l ，t h eg r o w t ho fn o d e s a n dc o n n e c t i o n s ，a sw e l la sac o n n e c t i o nt od e l e t ei sp o i s s o np r o c e s sm o d e l ，t h eg r o w t h a n dd e l e t i o no fn o d e si sp o i s s o np r o c e s sm o d e l b yc a l c u l a t i n gt h ed e g r e ed i s t r i b u t i o ni s ap o w e r - l a wd i s t r i b u t i o n ，a n dt h ep o w e ri n d e xr a n g i n gf r o mo n et ot h r e e a tt h es a m e t i m e ，t h i sp a p e ra l s or a i s e dt h es u b l i n e a rg r o w t ha n dd e l e t i o no fn o d e si sp o i s s o n p r o c e s sm o d e l ，t h r o u g ht h ea n a l y s i ss h o w st h a ts u c hn e t w o r k sr e f l e c tt h e d c hi sg e t t i n g r i c h e r ，b u tt h es t e a d y s t a t ea v e r a g ed e g r e ed i s t r i b u t i o ni sn o tp o w e r - l a wd i s t r i b u 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 c a l e - f r e en e t w o r k s ；d e g r e ed i s t r i b u t i o n ； p o w e r - l a wi n d e x c l a s s n o ：0 2 1 l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：彳1 互耘签字日期：厶。7 年1 月眵日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：予1 塑杀幺 签字日期：埘7 月c ；日 导师签名： 签字同期： 纱日 致谢 两年的研究生学习和生活中，我要特别感谢导师王金亭教授。他以循循善诱 的授课方式和孜孜不倦的耐心辅导，教会了我很多新的科研思路和方法，使我受 益匪浅。他严谨的治学风格，乐观积极、甘于奉献的生活态度，将永远是我学习 的榜样! 本论文是在王老师的精心指导和关怀下完成的。无论是在研究生课程学习过 程中，还是在论文选题、研究、定稿的过程中，王老师白始至终给了我大力的支 持和帮助，在此向王老师表示深深的感谢。 我还要感谢在我攻读硕士学位期间给予我帮助的院领导和老师，我同门的师 哥师姐师弟师妹和同窗的各位同学。 于恒松 2 0 0 9 年5 月 于北京交通大学理学院 1 引言一模型研究的理论背景及研究现状 1 1 复杂网络概述 1 1 1 复杂网络的历史与发展 地球上任意两个人之间要通过多少朋友才能相互认识? 万维网上从一个页面 到另一个页面平均需要点击多少次鼠标? 层出不穷的计算机病毒是如何在互联网 上传播的? 各种传染病包括非典型肺炎以及现在的甲型流感是如何在人类和动物 中流行的? 局部故障是如何触发大面积停电事故的? 大城市交通阻塞问题是如何 引起的? 应该如何建立合理的公共卫生与安全网络? 这些问题尽管看上去各不相 同，但每个问题都涉及很复杂的网络，包括w w w 、i n t e m e t 、社会关系网络、经 济网络、电力网络、交通网络等等。更重要的是越来越多的研究表明，这些看上 去各不相同的网络之间有着许多惊人的相似之处。 近年来随着复杂网络的兴起，使得人们开始广泛关注网络结构复杂性及其与 网络行为之间的关系。要研究各种不同复杂网络在结构上的共性，首先需要有一 种描述网络的统一工具。这种工具在数学上称为图，任何一个网络都可以看作是 由一些节点按照某种方式连接在一起而构成的一个系统。实际网络的图表示方法 可以追溯到1 8 世纪伟大的数学家欧拉对著名的“k o n i g s b e r g 七桥问题 的研究。 事实上，今天人们关于复杂网络的研究与欧拉当年关于“七桥问题”的研究在某 种程度上是一脉相承的。 2 0 世纪6 0 年代，由两位匈牙利数学家e r d 6 s 和r 6 n y i 建立的随机图理论 1 3 】， 被公认为是在数学上开创了复杂网络理论的系统性研究。他们的重要发现是：e r 随机图的许多重要性质都是突然涌现的。也就是说，对于任意给定的概率p ，要 么几乎每一个图都具有某个性质q ，要么几乎每个图都不具有该性质。在2 0 世纪 6 0 年代以来的几十年中，随机图理论一直是研究复杂网络的基本理论，但绝大多 数实际的复杂网络结构并不是完全随机的。例如，两个人是否是朋友，i n t e m e t 中 两个路由器之间是否有光纤连接，w w w 上两个页面之间是否有超文本链接等都 不会是完全靠抛硬币来决定的。 在2 0 世纪即将结束之际，对复杂网络的科学探索发生了重要的转变，复杂网 络理论研究也不再局限于数学领域。人们开始考虑节点数量众多、连接结构复杂 的实际网络的整体特性，掀起了研究复杂网络的热潮 4 ，2 5 。 有两篇开创性的文章可以看作是复杂网络研究新纪元丌始的标志：一篇是美 国康奈尔( c o m e l l ) 大学理论和应用力学系的博士生w a t t s 及其导师、非线性动力 学专家s t r o g a t z 教授于1 9 9 8 年6 月在n a t u r e 杂志上发表的题为“小世界 网络 的集体动力学( c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s ) 的文章 2 6 】；另 一篇是美国n o t r ed a m e 大学物理系的b a r a b f i s i 教授及其博士生a l b e r t 于1 9 9 9 年 1 0 月在s c i e n c e 杂志上发表的题为随机网络中标度的涌现( e m e r g e n c eo f s c m i n g i nr a n d o mn e t w o r k ) 的文章【5 】。这两篇文章分别揭示了复杂网络的小世界特征和 无标度性质，并建立了相应的模型以阐述这些特性的产生机理。 过去关于实际网络结构的研究往往着眼于包含几十个，至多几百个节点的网 络，而近年关于复杂网络的研究中则常可以见到包含几万到几百万个节点的网络。 网络规模尺度上的变化也促使网络分析方法做出相应的改变，甚至于很多问题的 提法都要有相应的改变。就目前而言，复杂网络理论的主要是按照以下思路进行 的： ( 1 ) 发现：揭示现实生活中的网络，刻画网络系统结构的统计性质，以及度量这 些性质的合适方法； ( 2 ) 建模：建立合适的网络模型以帮助人们理解这些统计性质的意义与产生机 理： ( 3 ) 分析：基于单个节点的特性和整个网络的结构性质分析与预测网络的行 为； ( 4 ) 控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、 同步和数据流通等方面。 1 1 2 复杂网络拓扑建模发展现状 要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需 要对实际网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。 一个典型的网络是由多个节点与连接两个节点之间的边组成的，其中节点用来代 表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间 2 具有某种特定关系则连一条边，反之则不连边，有边相连的两个节点在网络中被 看作是相邻的。把网络不依赖于节点的具体位置和边的具体形态就能表现出来的 性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。 两百多年来，对网络拓扑结构建模的研究经历了三个阶段。在最初的一百多 年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例 如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹( 图1 1 ( a ) ) ； 又或者最邻近环网，它会让你想到一群手牵着手围成一圈的兄弟( 图1 1 ( b ) ) 。 到了二十世纪五十年代末，数学家们想出了一种新的构造网络的方法，在这种方 法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学 家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被很多科学家认 为是描述真实系统最适宜的网络 1 3 】。直到最近几年，由于计算机数据处理和运算 能力的飞速发展，科学家们发现了大量的真实网络既不是规则网络，也不是随机 网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们 叫做复杂网络( c o m p l e xn e t w o r k s ) ，对于它们的研究标志着第三阶段的到来。 ( a )( b ) ( a ) 二维平面上的欧几里德格网；( b ) 最邻近环网 图1 1 简单规则网 不管是规则网络还是随机网络，它们的拓扑结构完全不能代表现实世界中的 复杂网络的拓扑结构。直n - 十世纪末，小世界网络模型( w s 模型) 和无标度网 络模型( b a 模型) 的出现才揭开了现实世界复杂网络拓扑结构建模的新篇章。自 此以后，大量的复杂网络拓扑结构建模的文章蜂拥而出。大体上可以把现在的拓 扑结构建模的文章分为两类： 一类是基于无标度网络模型( b a 模型) 所建立起来的，关于网络节点择优连 接和网络演化增长的拓扑结构建模。这类模型的拓扑结构的建模方面是对网络 的择优连接进行限制或者改变，以此来观察网络的结构与行为之间的关系，并进 3 而考虑改善网络的行为。例如，b a r a b 矗s i 等人对b a 模型的择优连接条件进行限制， 研究了网络节点度分布变化情况 6 】；k r a p i v s k y 等人对b a 模型的择优连接条件进 行了改变，研究了网络节点度分布指数的变化情7 5 己 2 0 。这类模型的拓扑结构建模 的另一方面是改变网络的演化增长，进而来研究网络的动力学情况等。例如， d o r o g o v t s e v 等人加速了网络的增长，研究了网络节点度分布变化情况 1 2 ；a m a r a l 等人对网络增长的老龄化进行了研究 3 】。 另一类是基于节点度序列( 节点连接度序列就是指将节点的连接度按某种顺 序排列起的序列) 的拓扑结构建模。a i e l l o 等人首先提出了一种给定节点连接度序 列的随机图模型。g k a n t s i d i s 等人基于马尔科夫链方法构造了一个给定度序列的随 机图模型 1 5 】。m o l l o y 等人给出了一种给定期望度的一般随机图模型 2 2 】。 1 2 复杂网络的应用及研究意义 2 0 世纪9 0 年代以来，以i n t e m e t 为代表的信息技术的迅猛发展使人类社会大 步迈入了网络时代。从i n t e r a c t 到w w w ，从大型电力网络到全球交通网络，从生 物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治、社会关 系网络等，可以说，人们已经生活在一个充满着各种各样的复杂网络的世界中。 人类社会的网络化是一把“双刃剑：它既给人类社会生产和生活带来了极大的 便利，提高了人类生产效率和生活质量，但也给人类社会带来了一定的负面冲击， 如传染病和计算机病毒的快速传播以及大面积停电事故等。因此，人类社会的日 益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。长期以来， 通讯网络、电力网络、生物网络和社会网络等分别是通信科学、电力科学、生命 科学和社会学等不同学科的研究对像，而复杂网络理论所要研究的则是各种看上 去互不相同的复杂网络之间的共性和处理它们的普适方法。从2 0 世纪末开始，复 杂网络研究正渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂 网络的定量与定性特征的科学理解，已经成为网络时代科学研究中一个极其重要 的挑战性课题，甚至被称为是“网络的新科学 。 以生命科学为例，2 0 世纪的生命科学研究主流是建立在还原论基础上的分子 生物学。还原论的基本前提是，在由不同层次组成的系统内，高层次的行为是由 低层次的行为所决定的。具有还原论观点的生物学家通常认为，只要认识了构成 4 生命的分子基础就可以理解细胞或个体的活动规律，而组分之间的相互作用常常 被忽略不计。尽管基于还原论的分子生物学极大地促进了人类对单个分子功能的 认识，然而绝大多数生物特征都来自于细胞的大量不同组分，如蛋白质、d n a 、 r n a 和小分子之间的相互作用。对这些极其复杂的交互作用网络的结构和动力学 的理解已成为2 1 世纪生命科学的关键性研究课题和挑战之一。 1 3 本课题研究的主要模型及方法 b a r a b 直s i 等人的主要贡献是提出了增长和择优连接时形成无标度网络的机制， 将连续化方法应用到了复杂网络的研究中，获得了增长网络节点度关于时间的微 分方程，为复杂网络的研究提供了新思路 5 】。然而在现在的绝大多数增长模型中， 只有连接和节点的增长【2 9 】，没有连接或节点的删除，或者有增长也有删除 8 ，1 6 】， 但只按一定的时间间隔进行数据统计。本课题主要是在b a 模型和前人的其他模型 基础上，进一步将其扩展，构建了4 个既有节点和连接的增加又有删除的p o i s s o n 网络模型，分别通过研究分析得出结论。这四个模型分别为 ( 1 ) 网络开始于较少的个节点的完全图，在时刻t ，按照参数为 的 p o i s s o n 过程到达一个节点，并且这个节点与网络中已存在的m ( i n m 0 ) 个节点相 连( 连接时按择优连接) ；按照参数为以的p o i s s o n 过程删除网络中的一条连接( 删 除按照反择优删除) ； ( 2 ) 网络开始于较少的个节点的完全图，在时刻t ，按照参数为丑的 p o i s s o n 过程到达一个节点，并且这个节点与网络中已存在的m ( m m 。) 个节点相 连( 连接时按择优连接) ；按照参数为丑的p o i s s o n 过程删除网络中的一条连接( 删 除按照反择优删除) ；按照参数为无的p o i s s o n 过程加入n 条连接( 连接时按择优 连接) ： ( 3 ) 网络开始于较少的个节点的完全图，在时刻t ，按照参数为 的 p o i s s o n 过程到达一个节点，并且这个节点与网络中已存在的m ( m m 0 ) 个节点相 连( 连接时按择优连接) ：按照参数为厶的p o i s s o n 过程删除网络中的一个节点( 删 除按照反择优删除) ； ( 4 ) 网络开始于较少的m o 个节点的完全图，在时刻t ，按照参数为a 的 p o i s s o n 过程到达一个节点，并且这个节点与网络中已存在的，l f 口( m t 口) 个节点 相连( 连接时按择优连接) ；按照参数为如的p o i s s o n 过程删除网络中的一个节点 ( 删除按照反择优删除) 。 6 2 复杂网络的统计特征 近年来，人们在刻画复杂网络结构的统计特性上提出了许多概念和方法，其 中有三个基本的概念 2 3 1 ：平均路径长度( a v e r a g ep a t hl e n g t h ) 、聚类系数( c l u s t e r i n g c o e f j f i c i e n t ) 和度分布( d e g r e ed i s t r i b u t i o n ) 。实际上，w a t t s 和s t r o g a t z 提出小世界 网络模型的初衷，就是想建立一个即具有类似于随机图的较小的平均路径长度， 又具有类似于规则网络的较大的聚类系数的网络模型。另一方面，b a r a b f i s i 和a l b e r t 提出的无标度网络模型，则是基于许多实际网络的度分布具有幂律( p o w e r - l a w ) 形式的事实。下面就对这三个基本的复杂网络统计特征作简要的说明。 2 1 平均路径长度 网络中任意节点对间的平均间隔距离对于了解网络的结构有指导意义，例如 在社会网络中它反映了社会聚集行为的传递性和可搜索性。网络中两个节点i 和 之间的距离谚，定义为连接这两个节点的最短路径上边的数目。网络中任意两个节 点之间的距离的最大值称为网络的直径( d i a m e t e r ) ，记为d ，即d = m a x 盔， i 。， 。 网络的平均路径长度定义为任意两个节点之间的距离的平均值，即 三= 广上一略 ( 2 1 ) 去( + 1 ) 陀， 其中，为网络节点数。网络的平均路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理，在公式( 2 1 ) 中包含了节点到自身 的距离( 当然该距离为零) 。如果不考虑节点到自身的距离，那么要在公式( 2 1 ) 的 右端乘以因子( + 1 ) ( 一1 ) 。在实际应用中，这么小的差别是完全可以忽略不计 的。一个含有个节点和m 条边的网络的平均路径长度可以用时间量级为 o ( m n l 的广度优先搜索算法来确定。 2 2 聚类系数 7 在你朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性称为网 络的聚类性。一般地，假设网络中的一个节点f 有屯条边和其他节点相连，：这- k i 个 节点就称为节点f 的邻居，显然，这砖个节点之间最多可能有屯 ，一1 ) 2 条边。而 这屯个节点之间实际存在的边数e 和总的可能的边数后，阮一1 ) 2 之比就定义为节 a i 的聚类系数e ，即c i = 2 e ，k ，伍，- 1 ) 。 从几何特点看，上式的一个等价的定义为g = 与节点i 相连的三角形的数量 弓丽薪丽磊三菊面蕊。 其中，与节点f 相连的三元组是指包括节点i 的三个节点，并且至少存在从节点f 到 其他两个节点的两条边。 图2 1 以：i 了点k 为顶点之一的三元组的两种可能形式 整个网络的聚类系数c 就是所有节点f 的聚类系数c ；的平均值。很明显， 0 c 1 。c = 0 当且仅当所有的节点均为孤立节点，即没有任何连接边；c = 1 当 且仅当网络是全局耦合的，即网络中任意两个节点都直接相连。对于一个含有个 节点的完全随机的网络，当很大时，c = o ( 2 v _ 1l 。而许多大规模的实际网络都 具有明显的聚类效应，它们的聚类系数尽管远小于l 但却比o ( n 。1 ) 要大得多。事 实上，在很多类型的网络( 如社会关系网络) 中，你的朋友的朋友同时也是你的 朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当专o 。时， c = 0 ( 1 1 。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具 有类似于社会关系网络中“物以类聚，人以群分 的特性。 2 3 度与度分布 度是描述一个网络图的最基本的术语，也是单独节点的属性中简单而又重要的 概念。节点f 的度定义为与该节点相连接的边的数目。直观上看，一个节点的度越 大就意味着这个节点在某种意义上越“重要 。网络中所有节点f 的度的平均值称 为网络的( 节点) 平均度，记为( 后) 。网络中节点的度的分布情况可用分布函数p ( 后) 来描述。度分布函数反映了网络系统的宏观统计特征。p ( k 1 表示的是一个随机选 定的节点的度恰好为k 的概率。 规则的格子有着简单的度序列，因为所有的节点具有相同的度，所以其度分布 为d e l t a 分布，它是单个尖峰。网络中的任何随机化倾向都将使这个尖峰的形状变 宽。完全随机网络的度分布近似为p o i s s o n 分布。其形状在远离峰值( 七) 处呈指数 下降。这意味着当k ( k ) 时，度为后的节点实际上是不存在的。因此，这类网络 也称为均匀网络。这几年的大量研究表明，许多实际网络的度分布明显地不同于 p o i s s o n 分布。特别地，在现实世界中更普遍存在的是具有幂律度分布p ( k 1 o c k 一， 的复杂网络，例如万维网，神经系统网，人类社会关系网等等。幂律分布曲线比 p o i s s o n 指数分布曲线下降要慢得多。幂律分布也称为无标度( s c a l e f r e e ) 分布， 具有幂律度分布的网络也称为无标度网络。 9 3网络拓扑基本模型及其性质 在w a t t s 和s t r o g a t z 关于小世界网络，以及b a r a b i s i 和a l b e r t 关于无标度网络 的丌创性工作之后，人们对存在于不同领域的大量实际网络的拓扑特征进行了广 泛的实证研究。在此基础上，人们从不同角度出发提出了各种各样的网络拓扑结 构模型 1 0 - 1 8 。 3 1规则网络 在一个全局耦合网络中，任恿两个点之i 司都有边直接相连。因此在具有相i 司 节点数的所有网络中，全局耦合网络具有最小的平均路径长度= 1 和最大的聚类 系数c 0 = 1 。虽然它反映了许多实际网络具有的聚类和小世界的性质，但该模型 作为实际网络模型的局限性也是很明显的，一个有个点的全局耦合网络有 n ( n - 1 ) 2 条边，然而大多数大型实际网络都是很稀疏的，它们的边数一般至多 d ( ) 而不是d ( 2 ) 。 一个得到大量研究的稀疏的规则网络模型是最近邻耦合网络，其中每一个节 点只和它左右各k 1 2 个邻居点相连，这里k 是偶数。对较大的k 值，最近邻耦合 网络的聚类系数为e 。= 百3 ( 耳k 可- 2 ) 三。然而，最近邻耦合网络不是一个小世界网络， 相反，对固定的k 值，该网络的平均路径长度为厶。互n o o ( n 一) 。这可以 从一个侧面帮助解释为什么在这样一个局部耦合的网络中很难实现需要全局协调 的动态过程( 如同步过程等) 。 另外一个常见的规则网络是星形耦合网络，它有一个中心点，其余的n 一1 个 点都只与这个中心点相连，而它们彼此间不相连。 星形网络的平均路径长度为乙_ 2 一黜卅( 咄 星形网络的聚类系数为= n v - = _ _ _ 1 1 - - - ) i ( n - - o o ) a 1 0 星形网络是比较特殊的一类网络。这里假设如果一个节点只有一个邻居节点， 那么该节点的聚类系数定义为1 。有些文献中则定义只有一个邻居节点的节点聚类 系数为0 。若依此定义，星形网络的聚类系数为0 。 一一桊 ( 曩)b )( d ( a ) 全局耦合网络；c o ) 最近邻耦合网络；( c ) 星形耦合网络 图3 1 几种常见的规则网络 3 2 随机网络模型 与完全规则网络相反的是完全随机网络，其中一个典型的模型是e r d 6 s 和 r 6 n y i 于5 0 多年前开始研究的e r 随机网络模型 13 】。 根据随机图理论，如下图3 2 所示，假设网络中有n 个节点，以相同的概率p 连接每对节点，则最后产生一个有个节点、r ( 一1 ) 2 条边的e r 随机网络模 型。 由随机网络模型的选定概率p ，我们可知 ( 1 ) 当p = 0 时，边数为0 ，网络中所有节点都是孤立的，节点闯无相互联系， ( k ) 卸，c = o ，瑚 2 ) 当夕= l 时，边数为n ( n 一1 ) 2 ，网络完全连通，所有节点都是最近邻，到网 络中任何节点的路径长度都是1 ； 3 ) 当p 介于0 和1 之间( 通常情况下 时，网络边数介于0f 6 jn ( n - 1 ) 2 之间。 网络中节点度的平均值( 后) = p ( n - 1 ) ，c = p ，ko c l i i n m k ) 固定e r 随机图的平均度仕) 不变，则对于充分大的，由于每条边的出现与 否都是独立的，e r 随机图的度分布可用p o i s s o n 分布来表示： p = 卧叫枞可( k ) k e - ( k ) ( 3 ) 其中( 露) 为平均度。图3 2 给出了e r 随机网络的节点度分布图。由图3 2 可 以看出在忙) 附近p ( 七) 有最大值，随着七的增大p ( 露) 迅速衰减。对固定的后，当 趋于无穷大时，最后的近似等式是精确成立的。因此，e r 随机图也称为“p o i s s o n 随机图”。 0s i1 01 s；0：s ：s4 d k 图3 2 随机网络模型的节点度分布( 取自文献【5 】) 3 3 小世界网络模型 前两节已经提到，规则的最近邻耦合网络具有高聚类性，但并不是小世界网 络；另一方面，e r 随机图虽然具有小的平均路径长度但却没有高聚类特性。因此， 这两类网络模型都不能再现真实网络的一些重要特征，毕竟大部分实际网络既不 是完全规则的，也不是完全随机的。 作为从完全网络向完全随机图的过渡，w a t t s 和s t r o g t z 于1 9 9 8 年引入了一个 有趣的小世界网络模型 4 】，称为w s 小世界模型。w s 小世界模型的构造算法如下： ( 1 ) 从规则图开始：考虑一个含有个点的最近邻耦合网络，它们围成一个环， 其中每个节点都与它左右相邻的各刚2 节点相连，k 是偶数。 ( 2 ) 随机化重连：以概率p 随机地重新连接网络中的每个边，即将边的一个端点 保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个 不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 在上述模型中，p = 0 对应于完全规则网络，p = 1 则对应于完全随机网络，通 1 2 垤 k 把 驰 * 舵 虻 o 口 o 口 a a a 2 ) 廿 过调节p 的值就可以控制从完全规则网络到完全随机网络的过渡，如图3 3 所示。 o 桊 完全规则网络小世界网络完全随机网络 p = 0 4p = 1 图3 3 小世界网络模型 由上述算法得到的网络模型的聚类系数c ( p ) 和平均路径长度l ( p ) 的特性都 可以看作是重连概率p 的函数。图3 4 显示了网络的聚类系数和平均路径长度随重 连概率p 的变化关系( 图中对两个值作了归一化处理) 。由图3 a 可以看出，小世 界网络模型显示了较大的聚类系数和较小的平均路径长度。 图3 aw s 小世界模型的聚类系数和平均路径长度随重连概率p 的变化关系( 取自文献【2 6 】) w s 小世界网络的聚类系数为c ( p ) = 若篓杀( 卜p ) 3 迄今为止，人们还没有关于w s 小世界模型的平均路径长度( p ) 的精确解析 表达式，不过，利用重正化群方法可以得到公式三( p ) ：警i ( u k p 2 ) 其中厂( “) 为 一普适标准函数，至今还没有它的精确表达式； 对于基于“随机化重连”机制的w s 小世界模型，当k 叫2 时，度分布 小广r ( 1 - p 僻 p ( 后) = i ：产l p ) 叫k 月= o” 降。( 堕丝芝竺 ( j j - ( k 2 ) 一万) ! p 一硝2 ( 3 2 ) | b 宝窑丑盘堂甄堂僮监窑!囤垒拓赴基主撼型盈甚毽厦 而当k r 2 时，( t ) = o 图3 5k = 3 ，p 取不同值时w s 模型的度分布( 1 瞳自文献 2 6 1 ) 另一个研究更多的小世界网络模型是由n e w m a n 和w a t t s 稍后提出的，称为 n w 小世界模型。该模型是通过用“随机化加边”取代w s 小世界模型构造中的“随 机化重连”而得到的。具体构造算法如下： ( 1 1 从规则图开始：考虑一个含有个点的最近邻耦合网络，它们围成一个环， 其中每个节点都与它左右相邻的各剧2 节点相连，茁是偶数。 ( 2 ) 随机化加边：以概率p 在随机选取的一对节点之间加上一条边。其中规定， 任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身 相连。 在n w 小世界模型中，p = 0 x 寸_ 应于原来的最近邻耦合网络，p = l 则对应于 全局耦合网络。在理论分析上，n w 小世界模型要比w s 小世界模型简单。当足口 够小和足够大时，n w 小世界模型本质上等同于w s 小世界模型。 3 4b a 无标度网络模型 e r 随机图和w s 小世界模型的一个共同的特征就是网络的连接度分布可以近 似用p o i s s o n 分布来表示，该分布在度平均值f 舢处有一峰值，然后呈指数快速衰 减。这意味着当女远远大于( 七) 时，度为k 的节点几乎不存在。因此，这类网络也 称为均匀网络或指数网络( e x p o n e n t i a ln e t w o r k ) 。近年来在复杂网络研究上的另一 重大发现就是许多复杂网络，包括i n t e r n e t 、w w w 以及新陈代谢网络等的连接度 分布函数具有幂律形式。由于这类网络的节点的连接度没有明显的特征长度，故 称为无标度网络。 为了解释幂率分布的产生机理，b a r a b a s i 和a l b e r t 提出了一个无标度网络模型， 现被称为b a 模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两 个重要特性 5 ，6 ： ( 1 ) 增长( g r o w t h ) 特性：即网络的规模是不断扩大的。例如，每天都会 有大量新的科研文章发表，而w w w 上则每天都有大量新的网页产生。 ( 2 ) 优先连接( p r e f e r e n t i a la t t a c h m e n t ) 特性：即新节点更倾向于与那些具 有较高连接度的“大 节点相连。这种现象也称为“富者愈富 现象 或“马太效应”。例如，新发表的文章更倾向于一些已被广泛引用的重 要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著 名的网站。 基于网络的增长和择优连接特性，b a 无标度网络模型的构造算法 ( 1 ) 增长( g r o w t h ) ：从一个具有个节点的网络开始，每一时间步增加一个节 点，并连接到m 个已存在的节点上，这里m m o ； ( 2 ) 择优连接( p r e f e r e n t i a la t t a c h m e n t ) ：一个新节点与一个已存在的节点i 的相 连接的概率正比于节点f 的度，关系式为：兀r2 亨 ( 3 3 ) 经过t 时间步以后，该模型产生一个具有n = f + 个节点，m t 条边的网络。 b a 无标度网络的平均路径长度为三芘i l 丽o g n ，这表明该网络也具有小世界 性。聚类系黼= 斜 h ( 等) _ 嘉 掣，这表明轴随机图 类似，当网络规模充分大时b a 无标度网络不具有明显的聚类特征。 b a 网络的度分布函数为p ( 七) = 面万2 m 石( m 丽+ 1 ) o c2 m 2 七一，这表明b a 无标度 网络的度分布函数可由幂指数为3 的幂律函数近似描述( 图3 6 ) 。 韭瘟窑通盘生熊主堂僮监奎 3囤些扛赴基圭搓型毽甚挂厦 圈3 6 b a 无标度网络模趟的度分布p ( 女) ( n = 1 0 0 0 ) ( 1 睨白文献【5 】) 3 5b a 模型的几种扩展模型 b a 无标度网络模型的精彩之处在于它把实际复杂网络的无标度特性归结为 增长和优先连接这两个非常简单明了的机制。这很好的体现了科学研究中的从复 杂现象提取简单本质的特点。当然这不可避免地使得b a 无标度网络模型和真实网 络相比存在一些明显的限制。例如，b a 模型只能生成度分布的幂律指数固定为3 的无标度网络，而各种实际复杂网络的幂律指数则不甚相同，而且大都属于2 至3 的范围内。此外，实际网络常常具有一些非幂律特征，如指数截断( e x p o n e n t i a l c u t o f f ) 、小变量饱和( s a t u t m i o nf o rs m a l lv a r i a b l e s ) 等。因此，在b a 模型中的基 础上人们做了各种各样的扩展其中一些重要的扩展模型都是通过修改b a 模型中 盼优先连接方式而获得的，如考虑初始吸引度和非线性优先连接概率f 2 1 等。下 面简单介绍一下几个b a 无标度网络的扩展模型。 3 5 1 适应度模型 在b a 无标度网络中，越老的节点具有越高的的度。然而在许多实际网络系统 中，节点的度及其增长速度并非只与该节点的年龄有关，而与节点内在的性质也 有一定的关系。b i a n c o n i 和b a r a b d s i 把这一性质称为节点的适应度( f i t n e s s ) ，并 据此提出了适应度模型【1 4 ( f i t n e s s m o d e l ) ，其构造算法如下： ( 1 ) 增长：从一个具有个节点的网络开始，每次引入一个新的节点并且连接 到研个已存在的节点上，这里聊m o 。每个节点的适应度按概率分布p ( 7 7 ) 选取。 ( 2 ) 优先连接：一个新节点与一个已经存在的节点f 相连接的概率n ，与节点f 的 度如节点的度巧和适应度仇之间i 芮足关$ 1 - i ，= j z 丛, l j l 乃 ( 3 4 ) 可以看出，适应度模型与b a 无标度模型的区别在于，在适应度模型中的优先 连接概率与节点的度和适应度之积成正比，而不是仅仅与节点的度成正比。这样， 在适应度模型中，如果一个年轻的节点具有较高的适应度，那么该节点就有可能 在随后的网络演化过程中获取更多的边。 3 5 2 局域世界演化网络模型 b a 无标度网络模型根据公式( 3 1 1 ) 来计算每一个节点的优先连接概率，由此 得到幂律形式的网络度分布。然而，在许多现实的网络中，由于局域世界连接性 的存在，每一个节点都有各自的局域世界，因此也只占用和使用整个网络的局域 连接信息。李翔等建立了局域世界演化网络模型 2 1 1 ，模型的构造算法如下： ( 1 ) 增长：网络初始时有个节点和e o 条边。每次新加入一个节点和附带的m 条边。 ( 2 ) 局域世界优先连接：随机地从网络已有的节点中选取m 个节点m m ，作 为新加入节点的局域世界。新加入的节点根据优先连接概率 l o c a l ( 咖n - ( i l w ) 忐三羔忐 ( 3 5 ) 来选择与局域世界中的m 个节点相连，其中l w 由新选的m 个节点组成。在每一 时刻，新加入的节点从局域世界中按照优先连接原则选取m 个节点来连接，而不 是像b a 无标度网络模型那样从整个网络中来选择。构造_ 个节点的局域世界的法 则依赖于实际不同的局域连接性而不同。 1 7 4p o i s s o n 增长与删除的网络模型 自从b a r a b i s i 和a l b e r t 提出b a 模型后，人们不断在b a 模型的基础上做了 各种各样的扩展。b a r a b f i s i 等人主要提出了增长和择优连接时形成无标度网络的机 制，将连续化方法应用到了复杂网络的研究中，获得了增长网络节点度关于时问 的微分方程。然而在现在的绝大多数增长模型中，只有连接和节点的增长，没有 连接或节点的删除，或者有增长也有删除 1 2 2 9 】，但只按一定的时问间隔进行数 据统计。下面这四个模型主要是在b a 模型和前人的其他模型基础上，进一步将其 扩展推广，构建了既有节点和连接的