（概率论与数理统计专业论文）m为随机变量的ba模型的度分布.pdf

原创性声明 f 1 1 1 if lli ii ii i ii ii il y 1718 9 3 4 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：i 坠丑 日期：耳年旦月孕日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 储签名：逝导师签名丝咝嘿肆年月粤日 摘要 本文利用马氏链方法及技巧研究b a 模型中m 为随机变量的情 况，严格证明度分布的存在性、无标度性，并给出它的精确解。全文 由四部分组成，具体结构如下： 第一章，绪论部分。简要介绍研究背景、研究现状及本文的基本 框架。 第二章，预备知识。介绍本文所涉及的理论知识，主要包括：从 规则图到随机图论进而到复杂网络的演化史；网络的度量特征；两种 典型的复杂网络( 小世界网络，无标度网络) ，网络度分布的几种求 解方法。 第三章，核心结果。研究b a 模型中m 为随机变量的网络的稳 定性。根据马氏链方法和技巧严格证明度分布的存在性、无标度性， 并求出其精确解。 第四章，总结与展望。总结本文主要工作，探求其不足之处及可 拓展空间。 关键词度分布，无标度性，马氏链 a b s t r a c t b a s e do nt h em e t h o da n dt e c h n i q u e so fm a r k o vc h a i n ，t h i sp a p e r p r o v i d e sar i g o r o u sp r o o f f o rt h ee x i s t e n c ea n ds c a l e f r e ep r o p e r t yo ft h e d e g r e ed i s t r i b u t i o no ft h eb am o d e l ，w h e r em i sar a n d o mv a r i a b l e a n d t h ee x a c tf o r m u l ao ft h ed i s t r i b u t i o ni sg i v e n t h i sp a p e ri so r g a n i z e da s f o l l o w s i nc h a p t e r1 ，w ei n t r o d u c et h er e s e a r c hb a c k g r o u n d ，s t a t u sq u o a n dt h eb a s i cf r a m e w o r ko ft h i sp a p e rb r i e f l y c h a p t e r2i n t r o d u c e st h e p r e l i m i n a r yk n o w l e d g e ，i n c l u d i n gt h ee v o l v i n gh i s t o r yo fc o m p l e x n e t w o r kf r o mt h er u l e sm a pt ot h er a n d o mg r a p ht h e o r y , n e t w o r k m e a s u r e m e n tc h a r a c t e r i s t i c s ，t w ot y p i c a lc o m p l e xn e t w o r k s ( s m a l l - w o r l d n e t w o r k sa n ds c a l e f r e en e t w o r k ) ，a n ds e v e r a ls o l u t i o n so ft h en e t w o r k d e g r e ed i s t r i b u t i o n i nc h a p t e r3 ，w es t u d yt h es t a b i l i t yo ft h eb am o d e l w i t har a n d o mv a r i a b l em w eg i v eap r o o ft h ee x i s t e n c eo ft h ed e g r e e d i s t r i b u t i o n ，a n di t se x a c ts o l u t i o n sa r eo b t a i n e d i nc h a p t e rf o u r , a s u m m a r yi sp r e s e n t s w ed i s c u s st h ei n s u f f i c i e n c yo ft h i sp a p e ra n d e x t e n d e ds p a c e k e yw o r d sd e g r e ed i s t r i b u t i o n ，s c a l e f r e e ，m a r k o vc h a i n i i 目录 第一章绪论1 1 1 问题提出的背景及研究现状1 1 2 论文的主要内容与结构3 第二章预备知识4 2 1 网络的度量特征，4 2 2 复杂网络发展历程与研究现状7 2 3 度分布的定义及其计算方法1 7 第三章b a 模型中m 为随机变量的度分布2 5 3 1 引言：2 5 3 2b a 模型2 5 3 3m 为随机变量的增长网络模型描述2 6 3 4 度分布2 7 第四章总结与展望3 5 参考文献3 6 致谢4 l 读硕士期间主要研究成果4 3 i i i 硕士毕业论文第一章绪论 第一章绪论 1 1问题提出的背景及研究现状 1 7 3 6 年欧拉( e u l e r ) 解决了著名的七桥问题，开创图论学科。2 0 世纪6 0 年代， 由匈牙利数学家e r d o s 和r e n y i 建立的随机图理论( r a n d o mg r a p ht h e o r y ) 叱在数学 上开创了复杂网络理论的系统性研究。在2 0 世纪后的4 0 年中，随机图理论一直 是研究复杂网络的基本理论。近年来在统计物理中出现的小世界网络( s m a l l w o r l dn e t w o r k s ) 【2 】和无标度网络( s c a l e f r e en e t w o r k s ) 【3 】更是引发了复杂网络的研 究热潮。 复杂网络理论研究的是各种看上去不同的复杂网络之间的共性和处理它们 的普适方法。从2 0 世纪末开始，对复杂网络的科学探索发生了重要的转变，复杂 网络也不再局限于数学领域。复杂网络研究已渗透到数理学科、生命学科和工程 学科等众多不同的领域。对复杂网络定量与定性特征的科学理解，已成为网络时 代科学研究中一个极其重要的挑战性课题，甚至被称为网络新科学。人们对复杂 网络的研究主要集中在以下三个领域： 1 网络的生成机制及演化模型，即通过生成机制建立网络模型【4 蚓，模拟 真实的网络； 2 复杂网络的稳定性，研究限制条件对网络几何特性的影响，如复杂网络 承受意外故障和黑客攻击的能力等； 3 复杂网络的动力学行为，这是人们研究复杂网络的主要目的之一，掌握 建立在这些网络上的系统的工作方式和机理，认识复杂系统内部深奥的动力学行 为。 过去关于实际网络结构的研究常常着眼于包含几十个，至多几百个节点的网 络，而近年来关于复杂网络的研究中则常可以见到包含从几万个到几百万个节点 的网络。网络规模尺度上的变化也促使网络分析方法作出相应的改变，甚至于很 多问题的提法都要有相应的改变。复杂网络研究的简单历史见下表【7 】： 硕士毕业论文第一章绪论 时间( 年)人物事件 1 7 3 6 e u l e r七桥问题 1 9 5 9 e r d s s 和r 6 n y i随机图理论 1 9 6 7 m i i g r a m小世界实验 1 9 7 3 g r a n o v e t t e r 弱连接的强度 1 9 9 8 w a t t s 和s t r o g a t z小世界模型 1 9 9 9b a r a b d s i 和a l b e r t无标度网络 从上图可以看出，无标度网络模型是2 0 世纪与2 1 世纪之交由b a r a b a s i 和a l b e r t 等人提出的，他们首先从动态增长的观点研究了复杂网络具有幂律度分布的形成 机理。现在通常将无标度网络的基本模型称为b a 模型。b a r a b a s i 和a l b e r t 等认为 以前的许多网络模型都没有考虑到实际网络的两个重要特性： ( 1 ) 增长( g r o w t h ) 特性：即网络的规模是不断扩大的。例如，每个月都会有大量 的新的科研文章发表，w w w 上每天都有大量新的网页产生。 ( 2 ) 优先连接( p r e f e r e m i a la t t a c h m e n t ) 特性：即新的节点更倾向于与那些具有较 高连接度的“大 节点相连接。这种现象也称为“富者更富伍c hg e tr i c h e r ) ”或“马 太效应( m a t t h e we f f e c t ) ”。例如，新发表的文章更倾向于引用一些被广泛引用 的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站 点。基于网络的增长和择优连接特性，b a r a b a s i 和a l b e r t 等人提出了b a 模型的 构造算法1 3 】： ( 1 ) 增长：从一个具有m 。个节点的网络开始，每次引入一个新的节点，并且连接 到m 个已存在的节点上，这里m 聊。； ( 2 ) 择优连接：一个新节点与一个已经存在的节点f 相连接的概率兀， i 的 度t 、节点的度数乃之间满足如下关系：兀，2 专 b a 无标度网络的提出，引发了复杂网络和复杂系统的研究热潮。实证研究发现， 许多现实网络，包括信息网络、社会网络和生物网络都具有无标度特性。因此无 2 硕士毕业论文第一章绪论 标度网络的提出，极大地激发了科学界的研究热情，他们探索无标度网络背后的 形成机理和组织原则，建立恰当的模型去拟合复杂网络自组织过程。b a 模型提 出后，引起了推广b a 模型的一个小高潮。例如k r a p i v s k y 等人1 4 j 根据实证和模 拟都是统计网络中度为k 的点数m ( f ) ，代替研究忍( f ) 而考虑，( f ) 的变化规律， 他们分析了按结点泼数非线性择优连线将会破坏网络的无标度性，只有渐近线性 择优连线才能产生无标度网络。d o r o g o v t s e v 等人【5 1 从概率角度，把色( 矿) 作为随 机变量来处理，提出了原始吸引模型。他们还研究了连线书按幂律加速增长的模 型，不过非线性连线数同样会破坏网络的无标度特性和稳定性。本篇硕士论文把 b a 模型中的m 随机化，利用马氏链首达概率法严格证明度分布的存在性、无标 度性，并给出它的精确解，相关文献见【8 1 1 | 。 1 2 论文的主要内容与结构 本文利用马氏链方法及技巧研究了b a 模型中当m 为随机变量时，严格证明 度分布的存在性、无标度性，并给出它的精确解。全文由四部分组成，具体结构 如下： 第一章，绪论部分。简要介绍研究背景、研究现状及本文的基本框架。 第二章，预备知识。介绍本文所涉及的理论知识，主要包括：从规则图到随 机图论进而到复杂网络的演化史；网络的度量特征；三种典型的复杂网络( 小世 界网络，无标度网络及可导航网络) ，网络度分布的几种求解方法。 第三章，核心结果。研究b a 模型中当m 随机化时出现的结果。根据马氏链 方法和技巧严格证明度分布的存在性、无标度性，并求出其精确解。 第四章，总结与展望。总结本文主要工作，探求其不足之处及可拓展空间。 硕士毕业论文第二章预备知识 2 1 网络的度量特征 第二章预备知识 广泛的应用前景使得复杂网络的研究备受国内外科学界的密切关注。如今， 复杂网络已经成为了横跨社会科学、自然科学、生命科学和工程科学等领域的重 要研究学科，例如，因特网、万维网 1 2 , 1 3 】、社会网络【1 4 - 引、组织网络、公司间商 务关系网络1 1 6 】、神经网络、生物网络【1 7 , 1 8 】、分布网络如血管分布或邮政运输路线 分布、论文之间相互引述而形成的网络【1 9 , 2 0 等。 近年来人们在刻画复杂网络结构的统计特性上提出了许多概念和方法，其中 有三个基本的概念：平均路径长度( 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 f i c i e n t ) 、和度分布( d e g r e ed i s t r i b u t i o n ) 1 2 1 】。实际上，w a t t s 和s t r o g a t z 提出小 世界网络模型的初衷，就是想建立一个既具有类似于随机图的较小的平均路径长 度，又具有类似于规则网络的较大的聚类系数的网络模型。另一方面，b a r a b a s i 和a l b e r t 提出的无标度网络模型，则是基于许多实际网络的度分布具有幂律 ( p o w e r - l a w ) 形式的事实。这里先介绍复杂网络的几个基本概念，它们是理解 复杂网络的基础。本节内容主要取自文献【引。 定义2 1 1 平均路径长度( a v e r a g ep a t hl e n g t h ) 网络中的两个节点f 和之间的距离d 。定义为连接这两个节点的最短路径 上的边数，网络中任意两个节点之间的距离的最大值称为网络的直径( d i a m e t e r ) ， 记为d ，即 d = m a x d n ( 2 一1 ) ， 。 网络的平均路径长度工定义为任意两个节点之间的距离的平均值，即 k 丽1 舻e ，吒 亿2 长度也称为网络的特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理， 4 硕士毕业论文第二章预备知识 在上述公式中包含了节点到自身的距离( 当然该距离为o ) 。如果不考虑节点到 自身的距离，则要在上述公式的右端乘以因子( + 1 ) ( n 1 ) 。在实际应用中， 这么小的差别是可以完全可以忽略不计的。一个含有个节点和m 条边的网络 的平均路径长度可以用时间量级为o ( m n ) 的广度优先搜索算法来确定。 定义2 1 2 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 在你的朋友关系网中。你的两个朋友可能彼此也是朋友，这种属性被称为聚 类特性。一般的，假设网络中一个节点f 有尼，条边将它和其他节点相连，这尼，个 节点就称为节点f 的邻居。显然，这个节点最多可能有屯 ，一1 ) 2 边。而这七，个 节点之间实际存在的边数e 和总的可能的边数七。k i 一1 ) 2 之比就定义为节点珀勺 聚类系数c ，即 c , = 2 e ，( 七，阮一1 ) ) ( 2 3 ) 从几何特点上看，上式酊一个等价定义为 c f = 与点f 相连的三角形的数量 与点f 相连的三元组的数量 ( 2 4 ) 其中，与节点f 相连的三元组是指包括节点f 的三个节点，并且至少存在从节点f 到其他两个节点的两条边。 整个网络的聚类系数c 就是所有节点的聚类系数c ；的平均值。很明显， 0 c 1 。c = 0 当且仅当所有的节点均为孤立节点，即没有任何连接边；c = 1 当且仅当网络是全局耦合的，即网络中任意两个节点都直接相连。对于一个含有 个节点的完全随机网络，当很大时，c = o ( n _ 1 ) ，而许多大规模的实际网络 都具有明显的聚类效应，它们的聚类系数尽管远小于l 却比0 ( 1 ) 要大的多。 事实上，在很多类型的网络( 如社会关系网络) 中，你的朋友的朋友同时也是你 的朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当专o 。时， c = o ( 1 ) ，这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上 具有类似于社会关系网络中“物以类聚，人以群分的特性。 定义2 1 3 度( d e g r e e ) 与度分布( d e g r e ed i s t r i b u t i o n ) s 硕士毕业论文第二章预备知识 度( d e g r e e ) 是网络中单独节点的属性值中简单而又重要的概念。节点f 的 度后，定义为与该节点连接的其他节点的数目。直观上看，一个节点的度越大，就 意味着这个节点在某种意义上越“重要 。网络中所有节点i 的度k ，的平均值( 砖称 为网络的( 节点的) 平均度。网络中节点的度的分布情况可用分布函数p ( 七) 来 描述，p ( k ) 表示一个随机选定的节点的度恰为k 的概率。 度分布是复杂网络中的一个重要统计特征量。规则网有着简单的度序列：因 为所有的节点具有相同的度，所以其度分布为d e l t a 分布，它是单个尖峰。网络 中的任何随机化倾向都将使这个尖峰的形状变宽。完全随机网络的度分布近似为 p o i s s o n 分布，其形状在远离峰值处成指数下降。这意味着当k ( k ) 时，度为k 的节点实际上是不存在的。因此，这类网络也称为均匀网络( h o m o g e n e o u s n e t w o r k ) 。 近几年的大量研究表明，许多实际网络的度分布明显的不同于p o i s s o n 分布。 特别的，许多网络的度分布可以用幂率的形式p ( k ) o ck 吖来更好的描述。幂率分 布曲线比p o i s s o n 指数分布曲线下降要缓慢的多。 幂律分布也称无标度分布，具有幂律分布性质的网络也称为无标度网络。在 一个度分布为具有适当幂指数( 通常为2 ，3 ) 的幂律形式的大规模无标度网 络中，绝大部分节点的度相对很低，但存在少数的度相对很高的节点。因此，这 类网络通常称为非均匀网络( i n h o m o g e n e o u sn e t w o r k ) ，而那些度相对很高的节 点称为网络的“集线器”( h u b ) 。例如，美国高速公路网就可以近似的看作是一 个均匀网络，因为不可能有上百条高速公路都经过同一个城市；而美国航空网可 以看作是一个无标度网络，大部分机场都是小机场，但却存在少量连接众多小机 场的非常大的机场，如芝加哥、达拉斯、亚特兰大和纽约机场。 定义2 1 4 小世界效应( s m a l l - w o r l de f f o r t ) 网络的平均顶点度固定，平均路径长度，很小，随网络大小以对数的速度或慢 于对数的速度增长，那么称此网络具有小世界效应。 对于网络发生过程的动力学而言，小世界效应具有明显的含义。例如，如果 考虑信息或其它任何之物在网络上的传播，小世界效应表明在多数现实时间网络 6 硕士毕业论文 第二章预备知识 上这将是一个快速的传播过程。举例子来说，如果一个谣言从任意人传播到任 一其他人只需要六步，那么他的传播速度将远比在需要一百步或一百万步的情况 下快得多。小世界效应影响到因特网上数据包从一台计算机传递到另一台计算机 所需经过的顶点数，影响到乘坐飞机或火车的旅行者途中所需经过的中转站数， 影响到一种疾病在人群中传播所需的时间长短，以及其它。 定义2 1 5 无标度网络( s c a l e f r e en e t w o r k s ) 网络的度分布 尸( j i ) ) 具有幂律尾部： 尸( 七) k ，k l ，y l 则这类网络被称为无标度网络，其中称y 为度指数。无标度网络最重要的特性是 标度不变性( s c a l ei n v a r i a n c e ) 。这类网络的节点的连接度没有明显的特征长度。 2 2 复杂网络发展历程与研究现状 2 0 世纪9 0 年代以来，以i n t e m e t 为代表的信息技术的迅猛发展使人类社会 大步迈入了网络时代。从i n t e r a c t 到w w w ，从大型电力网络到全球交通网络， 从生物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治、社 会关系网络等，可以说，人们已经生活在一个充满着各种各样的复杂网络的世界 中。人类社会的网络化是一把“双刃剑”j 它既给人类社会生活带来了一定的负 面冲击，如传染病和计算机病毒的快速传播以及大面积的停电事故等。因此，人 类社会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认 识。长期以来，通信网络、电力网络、生物网络和社会网络等分别是通信科学、 电力科学、生命科学和社会学等不同学科的研究对象，而复杂网络理论所要研究 的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。近年 来复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络行为 之间的关系。要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述 网络的统一工具。这种工具在数学上称为图( g r a p h ) 任何一个网络都可以看作 是有一些节点按某种方式连接在一起而构成的一个系统。具体网络的抽象图表 示，就是用抽象的点表示具体网络中的节点，并用节点之间的连线来表示具体网 络中节点之间的连接关系。 7 硕士毕业论文第二章预备知识 2 2 1 七桥问题( s e v e nb r i d g e sp r o b l e m ) 几何图形在欧几里得( e u c l i d ) 时代就是数学研究的重要对象之一。实际网 络的图表示方法可以追溯到1 8 世纪伟大的数学家欧拉( e u l e r ) 对著名的 “k o n i g s b e r g 七桥问题”的研究。k o n i g s b e r g 是东普鲁士( 现俄罗斯) 的一个城 镇，城中有一条横贯城区的河流，河中有两个岛，两岸和两岛之间共架有七座桥， 传说当地居民常常议论这样一个有趣的问题：一个人能否在一次散步中走过所有 的七座桥，而且每座桥只经过一次，最后返回原地? 这个问题看起来似乎相当简 单，但长期以来小镇上没有一个人能走出这样一条路径。 1 7 3 6 年，欧拉仔细地研究了这个问题。l 欧拉用点表示岛和陆地，两点之 间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥 问题化成判断连通网络能否一笔画的问题。他不仅解决了此问题，且给出 了连通网络可一笔画的充要条件是它们是连通的，且奇顶点( 通过此点弧的 条数是奇数) 的个数为0 或2 。如图所示。 了 1 经过研究后，他是这样解决问题的：除了起点以外，每次当一个人由一 座桥进入一块陆地( 或点) 时，他( 或她) 同时也由另一座桥离开此点。 所以每行经一点时，计算两座桥( 或线) ，从起点离开的线与最後回到始 点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成 欧拉对七桥问题的抽象和论证思想，开创了数学中的一个分支一图论 ( g r a p ht h e o r y ) 的研究。因此，欧拉被公认为图论之父，而上图也被称为欧 拉图。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的 研究在某种程度上是一脉相承的，即网络结构与网络性质密切相关。 2 2 2 规则网络 粗略地说，网络是节点与连线的集合。如果节点按确定的规则连线， 硕士毕业论文第二章预备知识 所得到的网络就称为规则( r e g u l a r ) 网络。例如，将节点排成一条直线，假定 每个节点与它最近邻的k = 2 k = 4 个节点连线，我们就得到一维规则无限网。若 将节点排成一个圈，让它们首尾相连，仍然假定每个节点与它最邻近的4 个节点 相连，我们就得到了一维规则有限网。除此以外，还有二维规则无限网、二维规 则有限网、高维规则网等。在规则网络中，每个节点具有相同的度数。 下面给出几个特殊的规则网络。 在一个全局耦合网络( g l o b a l l yc o u p l e dn e t w o r k ) 中，任意两个节点之间都 有边直接相连。因此，在具有相同节点数的所有网络中，全局耦合网络具有最小 的平均路径长度k = l 和最大聚类系数= l 。虽然全局耦合网络模型反映了许 多实际网络具有的聚类和小世界性质，但该模型作为实际网络的局限性也是很明 显的：一个有个点的全局耦合网络有( 一1 ) 2 条边，然而大多数实际网络都 是很稀疏的，它们的边的数目至多是d ( ) 而不是d ( 2 ) 。 一个得到大量研究的稀疏规则网络模型是最邻近耦合网络( n e a r e s t n e i g h b o r c o u p l e dn e t w o r k ) ，其中每一个节点只和它周围的邻居节点相连。具有周期边界 条件的最近邻耦合网络包含个围成一个环的点，其中每个节点都与它左右各 刚2 个邻居点相连，这里k 是一个偶数。对于较大的k 值，最近邻耦合网络的 聚类系数为 c：3(k-2)一3(2-5t)nc 一4 ( k - 1 ) 4 最近邻耦合网络是高度聚类的，但不是一个小世界网络，对于固定的k 值， 该网络的平均路径长度 k 去j 删专) ( 2 - 6 ) 这从一个侧面解释了为什么在局部耦合网络中很难实现需要全局协调的动态过 程( 如同步化过程) 。 另外一个常见的规则网络是星形耦合网络( s t a rc o u p l e dn e t w o r k ) ，它有一个 中心点，其他一1 个点都只与这个中心点连接，而它们彼此之间不连接。星形 网络的平均路径长度为 9 硕士毕业论文第二章预备知识 小2 一黜叫刊 ( 2 7 ) 聚类系数为 = 等州j ) ( 2 - 8 ) 星形网络是比较特殊的一类网络。这里假设如果一个节点只有一个邻居节点，那 么该节点的聚类系数的定义为1 。有些研究文献中则定义只有一个邻居节点的节 点聚类系数为0 。若依此定义，星形网络的聚类系数则为0 。 2 2 3 随机图论 如果节点不是按确定的规则连线，譬如按纯粹的随机方式连线，所得 到的网络就称为随机( r a n d o m ) 网络。2 0 世纪6 0 年代，由匈牙利数学家e r d o s 和r e n y i 建立的随机图理论【l 】( r a n d o mg r a p ht h e o 巧) 被公认为是在数学上开创了 复杂网络理论的系统性研究。 在e r d o s 和r e n y i 研究的随机图模型( 称e r 随机图) 中，任意两个节点之间有 一条边相连的概率都为p 。因此，在一个含个节点的e r 随机图中，边的总数 是一个期望值为p n ( n - 1 ) 2 】的随机变量。由此可以推得，产生一个有个节点 和m 条边的e r 随机图的概率为p m ( 1 一p ) - 1 ) 协m 。 随机图论的一个主要研究课题是当概率p 为多大时，随机图会产生一些特殊 的属性。e r d o s 和r e r l y i 系统的研究了当一o o 时，e r 随机图的性质( 如连通 性等) 与概率p 之问的关系。他们采用了如下定义：当专o o 时，产生一个具 有性质q 的e r 随机图的概率是1 ，那么就称几乎每一个e r 随机图都具有性质 o 。e r d o s 和r e n y i 最重要的发现是e r 随机图具有以下涌现或相变性质：e r 随 机图的许多重要性质都是突然涌现的。也就是说，对于任意给定的概率p ，要么 几乎每一个图都具有某种性质q ，要么几乎每一个图都不具有该性质。e r 随机 图具有以下三个统计特征量： ( 1 ) 度分布：根据随机图演化过程，每个点与其它点的连接都是等概率的，因 此，随机图的度分布p ( 七) 服从二项分布b ( n l ，p ) ，即 硕士毕业论文第二章预备知识 尸( 七) = c 嘉一l p ( 1 一p ) 。卜， 对于充分大的n ，e r 随机图的度分布可以近似为p o i s s i o n 分布： 州= 防卜譬产) 其中平均度是( 后) = p ( n 一1 ) ( 2 ) 平均路径长度：设三职是e r 随机图平均路径长度。直观上，对于e r 随机 图中随机选取的一个点，网络中大约有( 七) 坛个其他的点与该点之间的距离等于 或是非常接近于职。因此，n 芘( 七) k ，即l 歙芘i n n l n k ) 。这种平均路径长 度为网络规模的对数增长函数的特性就是典型的小世界特性。因为i n n 的值随n 增长的很慢，这就使得即使是规模很大的网络也可以具有很小的平均路径长度。 ( 3 ) 聚类系数：考察e r 随机图中的两个节点之间不论是否具有共同的邻居节 点，其连接概率均为p ，因此，e r 随机图的聚类系数是c = p = ( k ) n 1 ，这 意味着大规模稀疏的e r 随机图没有聚类特性。而现实中的复杂网络一般都具有 聚类特性。也就是说，实际的复杂网络的聚类系数要比相同规模的e r 随机图的 聚类系数高的多。 固定随机图的平均度( 七) 不变，则对于充分大的，由于每条边的出现与否 都是独立的，e r 随机图的度分布可用p o i s s i o n 分布来表示： 州= 陟h ) - 譬) 其中，对于固定的七，当n 趋于无穷大时，最后的近似等式是精确成立的。 因此e r 随机图也称为。p 。i s s i 。n 随机图” 2 2 1 。 尽管e r 随机图作为实际复杂网络的模型存在明显的缺陷，在2 0 世纪后4 0 年中，e r 随机图理论一直是研究复杂网络拓扑的基本理论，其中一些基本思想 在目前一些复杂网络理论研究中依然很重要，如b 。l l 。b a s 的著作 2 2 l 。人们可以 从多个角度对e r 随机图进行扩展以使其更接近真实的网络。n e 、砌a i l 【2 3 】介绍 了具有任意给定的度分布的广义随机图( g e n e r a l i z e dr a n d o mg r a p h ) 。给定一个度分 硕士毕业论文 第二章预备知识 布尸亿) ，它表示了网络中度为k 的节点所占的比例。基于这一分布可以按照相同 概率产生多个度序列( d e g r e es e q u e n c e ) 为t o = 1 , 2 ，n ) 的由n 个节点组成的 网络。这些网络模型的集合成为配置模型( c o n f i g u r a t i o nm o d e l ) 。 2 2 4 复杂网络 规则网是秩序的象征，随机网络是混乱的代表，现实网络不太可能是这两个 极端之一。科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而 是具有与前两者皆不同的统计特征的网络。如果结点按某种自组织原则方式连 线，演化成各种不同的网络，称为复杂网络。 有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：一篇是美 国康奈尔( c o r n e 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 】) ；另一篇是美国n 。扛ed 锄e 大学物理系的b 砸b a 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 e 。fs c a l i n gi nr a n d o mn e t w o r k s ) 的文章( 见文献【3 】) 。这两篇文章 分布揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这 些特性的产生机理。 下面我们分布详细介绍小世界网络和无标度网络。 2 2 4 1 小世界网络 小世界网络的基本模型是w s 模型，算法描述如下【2 j ： ( 1 ) 给定规则网：假如我们有一个节点总数为n ，每个节点与它最邻近的k = 2 k 个节点相连的一维有限规则网。通常要求n k 1 ： ( 2 ) 改写1 日连线：以概率p 为规则网的每条旧连线重新布线，方法是将该连线 的一个端点随机的放置到一个新位置上，但需要排除自身到自身的连线和重复 连线。 1 2 硕士毕业论文第二章预备知识 翔岬潮翻心彪 o0 恭 謦o _ 参p 簟1 辆a 臻蜘哺粥细明嗍 在w s 模型中，当p = 0 时，对应于完全规则网络，p = l 时则对应于完全随 机网络。通过调节p 的值可以控制从完全规则网络到完全随机网络的过渡。w a t t s 和s t r o g a t z 说明小世界网络在p 值较小的一个范围内同时具有大的聚类系数和短 的平均路径，称为小世界现象或效应( e f f e c t ) 。许多现实的网络都具有这种小世 界效应。 但是，w s 小世界模型构造算法中的随机化过程有可能破坏网络的连通性。 改写旧连线机制，w s 模型有可能出现孤立的集团，而且不便于理论分析。 n e w l r l a i l 和w 撕s 【2 4 】提出了一个改进后的模型，通过用“随机化加边，取代w s 小世界模型中的“随机化重连而得到。具体构造算法如下： ( 1 ) 给定规则网：假如我们有一个节点总数为n ，每个节点与它最邻近的k = 2 k 个节点相连的一维有限规则网。通常要求n k l ； ( 2 ) 新增随机网：对规则网的个节点，以概率肚2 在任意两个节点之间连线， 但不改动规则网的原有连线，也不允许自身到自身的连线和重复连线。 在n w 小世界模型中，p = 0 对应于原来的最近邻耦合网路，p = l 则对应于 全局耦合网络。n w 模型实际上是规则网和随机网的叠加，其中增加的捷径总数 仍近似为p x x e 。在理论分析上，n w 小世界模型比w s 小世界模型简单。对 于很小的p 和很大的改进的模型与w s 模型基本等价。 小世界网络模型反映了朋友关系网络中的一种特性，即大部分人的朋友都是 和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是 硕士毕业论文 第二章预备知识 住得较远的甚至是远在异国他乡的朋友，这种情形对应于w s 小世界模型中通过 加入连线产生的远程连接。 下面介绍小世界网络模型的一些统计性质。 1 、度分布 在基于“随机化加边”机制的n w 小世界模型中，每个节点的度数至少为 规则网的度数k ，而增加的捷径是以概率p k n 连线，当后k 时，一个随机选 取的节点的度数为七的概率为 尸 ，= ( 2 k ) ( 鲁厂( 一等) 肛“r _ 譬p 母， 当k 。ll 为求解率方程，假定n ko ) t 依概率收敛到尸 ) ，代入( 2 2 4 ) 式得： 尸 ) 妄= 所( k - 1 ) t p 瓦( k - 广1 ) - k t p ( k ) + ( 2 - 2 5 ) ( 2 2 5 ) 式简化为差分方程： 。 + 2 妒 ) = o 1 ) p ( k 1 ) + 2 巧嘶 ( 2 2 6 ) 当k m 时，因为既= 0 ，递推求解( 2 2 6 ) 式得 m ) = 丽( k - 1 ) p ) = - 1 耵x k - 2 x k - 3 ) 雌- 3 ) ( 2 2 7 ) 一直计算到k = 历+ 3 ，于是有 尸 ) = 面2 m 研( m + 丽1 ) 2 朋2 七一3 ( 2 - 2 8 ) 对小度数，上式中的等式是精确结果，但它不是幂率，只有对大的k 才是幂率。 2 3 5 主方程方法 d o r o g o v t s e v 、m e n d e s 和s a m u k h i n 【2 5 】提出了主方程方法( m a s t e r - e q u a t i o n 2 0 硕士毕业论文第二章预备知识 a p p r o a c h ) 。这种方法研究所以节点在f 时刻的度数为k 的概率，从而得到网络的 度分布。 在b a 模型中，对固定的，第i 步加入的节点的度数砖o ) 是一个随机变量。 令尸 ，i ，f ) 表示f 时刻加入的节点在f 时刻的度恰好为k 的概率( 这是在允许重复 连线下讨论的，将其限定到b a 模型) 。采用m h 阮) 假设：忽略初始节点，一 个新节点与朋条连线加入网络将使得节点i 的度增加1 的概率是m n ，= k 2 t ，得 到下述主方程： 盹口+ 1 ) 2 百k - 1 尸，f ，嘶一丢) 舷啦) ( 2 - 2 9 ) 主方程的边界条件是尸伍，t ，f ) = 屯，将主方程改写为： ，等( 善慨) 川m 川) ) = k 一- l z ：，肛u 力+ ( 一劫喜慨r ) 即 r 川) 一p g ，r ) 】+ p g 1 ) 一瓯= 等p g _ l ，r ) 一喜p ，( 2 - 3 0 ) 假定尸 ) 存在，补充假设l i m ( p ( k ，t + 1 ) 一尸 ，f ) ) = 0 ，令fj 得： 。 尸g ) 一= 孚尸 一1 ) 一喜p o ) ( 2 _ 3 1 ) 经简化可得到与( 2 2 6 ) 相同的差分方程 + 2 ) 尸 ) = 一1 ) p ( k 一1 ) + 2 万 ( 2 3 2 ) 2 3 6 马氏链方法 s h i ，c h e na n dl i u 【3 9 】提出了马氏链方法( m a r k o vc h a i na p p r o a c h ) 。 令尼，o ) 表示第i 步加入的节点在在，时间步的度数，将它看成是一个随机过 程。对b a 模型，过程尼，o ) 在第，+ 1 时间步的取值只依赖于第t 时间步的取值， 而与以前各步取值无关，因此尼，o ) 是非齐次马氏链。参数空间t = p ，i + 1 ，i + 2 ) ， 状态空间q - - m ，m + l ，m + 2 。采用垅兀( 墨搬设，k = 脚，m + l ，m + 2 ，m + t i 时，有转移概率： 硕士毕业论文 第二章预备知识 f 1 一k 2 t ，= k p ( k , o + 1 ) = 啦，o ) = 七) = t o ，其他 i k 2 t ，= k + 1 当后 m + t - i 时，因为尸纯o ) = 后) = 0 ，约定： p g ，o + 1 ) = ，l 七，o ) = 七) = i 。1 , ，l ，= ：k 七+ l 对于，= f ，i + 1 ，i + 2 ，上述条件概率可以写成矩阵形式 o + 1 ) = ( 2 3 3 ) ( 2 3 4 ) 1 一m | 丑m | 2 t 1 - ( m + 1 ) 2 t 妇+ 1 ) 2 t 1 一如+ f i ) 2 t 似+ r i ) 2 t l0 ( 2 3 5 ) 令 五( f ) = p 承：o ) = 聊+ 刀 ，以= 0 , 1 ，2 ，z g ) ：