（概率论与数理统计专业论文）一类择优增长系统的度分布.pdf

摘要 本文利用马氏链方法及技巧研究一类择优增长系统，严格证明度 分布的存在性、无标度性，并给出它的精确解。全文由六部分组成， 具体结构如下： 第一章，绪论部分。简要介绍研究背景、研究现状及本文的基本 框架。 第二章，预备知识。介绍本文所涉及的理论知识，主要包括：从 规则图到随机图论进而到复杂网络的演化史；网络的度量特征；三种 典型的复杂网络( 小世界网络，无标度网络及可导航网络) ，网络度 分布的几种求解方法。 第三章，核心结果。研究一种特殊的择优增长模型：投球模型， 该模型由不同规模的盒子组成，经每时间步，系统中分别到达一个盒 子和一个球。新球以概率卜p 落入新盒子，落入旧盒子中的概率与旧 盒子中的球数成正比。笔者认为，前人利用主方程法求解该模型的度 分布仍有值得商榷之处。笔者根据马氏链方法和技巧严格证明度分布 的存在性、无标度性，并求出其精确解。本章最后给出度分布的计算 机模拟结果。 第四章，第三章的推广之一。将投球模型推广至球成批到达的一 般情形。经每时间步，系统中分别到达一个盒子和m 个球。这m 个球 相互独立的依概率p 落入旧盒子，并且落入旧盒子中的概率与旧盒子 中的球数成正比；依概率q 全部落入新盒子。笔者根据马氏链方法和 i 技巧严格证明在此情形下，系统稳态度分布的存在性、无标度性，并 给出它的精确解。 第五章，第三章的推广之二。将投球模型推广至球成批到达的一 般情形。经每时间步，系统中分别到达一个盒子和所个球。其中s 个球 相互独立的依概率p 全部落入旧盒子中，依概率卜p 全部落入新盒。 其余m s 个球必然落入新盒中。小球落入旧盒子中的概率与旧盒子中 的球数成正比。笔者根据马氏链方法和技巧严格证明在此情形下，系 统稳态度分布的存在性、无标度性，并给出它的精确解。 第六章，总结与展望。总结本文主要工作，探求其不足之处及可 拓展空间。 关键字：择优增长系统，度分布，无标度性，马氏链 a b s t r a c t t h i sp a p e rm a i n l yd e v o t e st os t u d y i n gac l a s so fp r e f e r e n t i a lg r o w t h s y s t e m s b a s e do nt h em a r k o vc h a i nt h e o r y , t h ea u t h o rg e t st h er i g o r o u s p r o o ff o rt h ee x i s t e n c eo ft h es t e a d y s t a t ed e g r e ed i s t r i b u t i o na n dd r i v e s t h ee x a c ta n a l y t i cf o r m u l a so ft h ed i s t r i b u t i o n ，t h e np r o v e st h es y s t e mh a s s c a l e f r e ep r o p e r t y t h ef u l lt e x ti sc o m p o s e do fs i xp a r t s ，t h ec o n c r e t e s t r u c t u r ei sa sf o l l o w s ： c h a p t e ro n ei n t r o d u c e st h eb a c k g r o u n da n de x i s t i n gw o r ko ft h e g r o w t hs y s t e ma sw e l la st h ef r a m e w o r ko ft h ep a p e r c h a p t e rt w oi n t r o d u c e st h ee l e m e n t a r yt h e o r i e sw h i c ha r en e e d e di n t h ep a p e r , m a i n l yi n c l u d e ：n e t w o r km e a s u r ec h a r a c t e r i s t i c s ；t h ee v o l v e d h i s t o r yo fc o m p l e xn e t w o r kw h i c hb e g i n sw i t hr e g u l a rn e tt os t o c h a s t i c g r a p ht h e o r yt h e nt oc o m p l e xn e t w o r k ；t h r e ei m p o r t a n ts t r u c t u r ef e a t u r e s i n c o m p l e xn e t w o r k s ( s m a l l w o r l de f f e c t ，s c a l e f r e ep r o p e r t y a n d n e t w o r k sn a v i g a b i l i t y ) ；d i f f e r e n tt o o l so fc o m p u t i n gd e g r e ed i s t r i b u t i o n c h a p t e rt h r e ec o n s i d e r sap r e f e r e n t i a lg r o w t hm o d e lw h e r eb a l l sa n d b o x e sa r eb o t ha d d e do n eb yo n et ot h es y s t e m an e wb a l lc a ne i t h e rj o i n i nt h en e wb o x ( w i t hp r o b a b i l i t yq ) o rj o i ni na na l r e a d ye x i s t i n gb o x w i t hap r o b a b i l i t yp r o p o r t i o n a lt ot h es i z et h e r e o f b a s e do nt h em a r k o v c h a i nt h e o r y , t h ea u t h o rg e t st h er i g o r o u sp r o o ff o rt h ee x i s t e n c eo ft h e s t e a d y - s t a t ed e g r e ed i s t r i b u t i o na n do b t a i n st h ee x a c ts o l u t i o n ，t h e n i i i p r o v e st h em o d e lh a ss c a l e - f r e ep r o p e r t y a tt h ee n d ，t h ea u t h o rg i v e st h e r e s u l to f c o m p u t i n gs i m u l a t i o no fd e g r e ed i s t r i b u t i o n c o n s i d e r i n g t h e r ea r e 聊b a l l sa d d e dt ot h es y s t e ma te a c ht i m es t e p ， c h a p t e r f o u rp r o m o t e st h e p r e f e r e n t i a lg r o w t hm o d e lt o a ng e n e r a l s i t u a t i o n t h emb o x e sc a ne i t h e rjo i ni nt h en e wb o x ( w i t hp r o b a b i l i t y q ) o rd e p e n d e n t l yj o i ni na na l r e a d ye x i s t i n gb o xw i t hap r o b a b i l i t y p r o p o r t i o n a lt ot h es i z et h e r e o ft h ea u t h o rg e t st h er i g o r o u sp r o o ff o rt h e e x is t e n c eo ft h ed e g r e ed i s t r i b u t i o na n do b t a i nt h ee x a c ts o l u t i o n c h a p t e rf i v ep r o m o t e st h ep r e f e r e n t i a lg r o w t hm o d e lt ot h eo t h e r g e n e r a ls i t u a t i o n c o n s i d e r i n gt h e r ea r e mb a l l sa d d e dt ot h es y s t e ma t e a c ht i m es t e p ，m - sb a l l sj o i ni nt h en e wb o x ，sb a l l sc a ne i t h e rj o i ni n t h en e wb o x ( w i t hp r o b a b i l i t y1 一p ) o r d e p e n d e n t l yj o i ni na na l r e a d y e x i s t i n gb o xw i t hap r o b a b i l i t yp r o p o r t i o n a lt o t h es i z et h e r e o f t h e a u t h o rg e t st h er i g o r o u sp r o o ff o rt h ee x i s t e n c eo ft h ed e g r e ed i s t r i b u t i o n a n do b t a i nt h ee x a c ts o l u t i o n c h a p t e rs i xs u m m a r i z e st h em a i n l yw o r ko f t h i sp a p e r , a n dc a r r yo n t h i sr e s u l tt of u r t h e rd i s c u s s e s k e yw o r d s ：p r e f e r e n t i a lg r o w t hs y s t e m ，s t e a d y s t a t ed e g r e e d i s t r i b u t i o n ，s c a l e f r e ep r o p e r t y , m a r k o vc h a i n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名：盘望日期：措旦月鱼日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位沦文。 作者签名：盟导师签名笠咝日期：避年上月丛日 硕十学位论文第一章绪论 第一章绪论 1 1 问题提出的背景与研究现状 1 7 3 5 年欧拉研究著名的七桥问题，开创图论学科。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 ) 【，在数学上开创 了复杂网络理论的系统性研究。近年来在统计物理中出现的小世界网络1 2 】和无标 度网络1 3 j 更是引发了复杂网络的研究热潮。 复杂网络理论研究的是各种看上去不同的复杂网络之间的共性和处理它们 的普适方法。从2 0 世纪末丌始，复杂网络研究已渗透到数理学科、生命学科和工 程学科等众多不同的领域。对复杂网络定量与定性特征的科学理解，已成为网络 时代科学研究中一个极其重要的挑战性课题，甚至被称为网络新科学。人们对复 杂网络的研究主要集中在以下三个领域： 1 网络的生成机制及演化模型，即通过生成机制建立网络模型1 4 。6 j ，模拟 真实的网络； 2 复杂网络的稳定性，研究限制条件对网络几何特性的影响，如复杂网络 承受意外故障和黑客攻击的能力等； 3 复杂网络的动力学行为，这是人们研究复杂网络的主要目的之一，掌握 建立在这些网络上的系统的工作方式和机理，认识复杂系统内部深奥的动力学行 为。 无标度网络模型是2 0 世纪与2 l 世纪之交由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 n t i a la t t a c h m e n t ) 特性：即新的节点更倾向于与那些具有 硕 ：学位论文第一章绪论 较高连接度的“大 节点相连接。这种现象也称为“富者更富( r i c hg e tr i c h e r ) ”或 “马太效应( m a t t h e we f f e c t ) 9 9 0 例如，新发表的文章更倾向于引用一些被广泛 引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名 的站点。基于网络的增长和择优连接特性，b a r a b a s i 和a l b e r t 等人提出了b a 模 型的构造算法【3 j 。 b a 无标度网络的提出，引发了复杂网络和复杂系统的研究热潮。在现实世 界中，一些演化系统拥有择优和增长的特性，却并非网络，如经济系统中个人或 公司的收入、生物物种数量的变化等 4 - 1 1 j 。这些系统是由一些规模不等的团体构 成，每个团体中包含数量不等的个体，团体之间互相独立。当一个新个体进入系 统时，它根据系统中已经存在的团体的规模来选择进入一个特定的团体。 s i m o n l 9 j 分析了这种演化系统的一个简单模型，在这个模型中，增长概率与系统 中团体的规模相关，同时给出了时间相依规模的精确解。l k u l l m a n n ，j k e r t e s z 挖j 在择优增长：一类时i 日j 相依分布的精确解中讨论了一种特殊的增长系统模型， 并利用主方程法求出了时间完全相依的分布函数。然而，笔者认为文 1 2 在利用 主方程求解度分布时，仍有值得商榷之处。本篇硕士论文修正了文1 2 1 中的增长 系统模型，利用马氏链首达概率法严格证明度分布的存在性、无标度性，并给出 它的精确解。 1 2 论文的主要内容与结构 本文利用马氏链方法及技巧研究一类择优增长系统，严格证明度分布的存在 性、无标度性，并给出它的精确解。全文由六部分组成，具体结构如下： 第一章，绪论部分。简要介绍研究背景、研究现状及本文的基本框架。 第二章，预备知识。介绍本文所涉及的理论知识，主要包括：从规则图到随 机图论进而到复杂网络的演化史；网络的度量特征；三种典型的复杂网络( 小世 界网络，无标度网络及可导航网络) ，网络度分布的几种求解方法。 第三章，核心结果。研究一种特殊的择优增长模型：投球模型，该模型由不 同规模的盒子组成，经每时间步，系统中分别到达一个盒子和一个球。新球以概 2 硕士学位论文第一章绪论 率卜p 落入新盒子，落入旧盒子中的概率与旧盒子中的球数成正比。笔者认为， 前人利用主方程法求解该模型的度分布仍有值得商榷之处。笔者根据马氏链方法 和技巧严格证明度分布的存在性、无标度性，并求出其精确解。本章最后给出度 分布的计算机模拟结果。 第四章，第三章的推广之一。将投球模型推广至球成批到达的一般情形。经 每时问步，系统中分别到达一个盒子和m 个球。这m 个球相互独立的依概率p 落 入旧盒子，并且落入旧盒子中的概率与旧盒子中的球数成正比；依概率g 全部落 入新盒子。笔者根据利用马氏链方法和技巧严格证明在此情形下，系统稳态度分 布的存在性、无标度性，并给出它的精确解。 第五章，第三章的推广之二。将投球模型推广至球成批到达的一般情形。经 每时间步，系统中分别到达一个盒子和m 个球。其中s 个球相互独立的依概率p 全 部落入旧盒子中，依概率卜p 全部落入新盒。其余m s 个球必然落入新盒中。小 球落入旧盒子中的概率与旧盒子中的球数成正比。笔者根据利用马氏链方法和技 巧严格证明在此情形下，系统稳态度分布的存在性、无标度性，并给出它的精确 解。 第六章，总结与展望。总结本文主要工作，探求其不足之处及可拓展空问。 3 硕l ：学位论文 第二章预备知识 网络的度量特征 第二章预备知识 广泛的应用前景使得复杂网络的研究备受国内外科学界的密切关注。如今， 复杂网络已经成为了横跨社会科学、自然科学、生命科学和工程科学等领域的重 要研究学科，例如，因特网、万维网【t 引、社会网络( 1 6 , 7 1 、组织网络、公司问商 务关系网络【1 8 】、神经网络、生物网络【1 9 z 引、分布网络如血管分布或邮政运输路 线分布、论文之间相互引述而形成的网络【z “2 2 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 f i c i e n t ) 、和度分布( d e g r e ed i s t r i b u t i o n ) 2 3 】 2 1 1 平均路径长度( a v e r a g ep a t h ie n g t h ) 网络中的两个节点i 和_ ，之间的距离d 打定义为连接这两个节点的最短路径 上的边数，网络中任意两个节点之问的距离的最大值称为网络的直径( d i a m e t e r ) ， 记为d ，即 d = m a xd 盯 ( 2 - 1 ) 网络的平均路径长度l 定义为任意两个节点之间的距离的平均值，即 扛丽1 酗 q 。2 长度也称为网络的特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理， 在上述公式中包含了节点到自身的距离( 当然该距离为o ) 。如果不考虑节点到 自身的距离，则要在上述公式的右端乘以因子( n + 1 ) ( n 1 ) 。在实际应用中， 这么小的差别是可以完全可以忽略不计的。一个含有n 个节点和m 条边的网络 的平均路径长度可以用时问量级为o ( m n ) 的广度优先搜索算法来确定。 2 1 2 聚类系数( c l u s t e ri n g0 0 e f f i c i e n t ) 在你的朋友关系网中，你的两个朋友可能彼此也是朋友，这种属性被称为聚 4 硕士学位论文 第二章预备知识 类特性。一般的，假设网络中一个节点f 有屯条边将它和其他节点相连，这屯个 节点就称为节点f 的邻居。显然，这个节点最多可能有色k i 一1 ) 2 边。而这t 个 节点之间实际存在的边数e 和总的可能的边数屯k i ：1 ) 2 之比就定义为节点f 的 聚类系数g ，即 c i = 2 e i ( k ， ，一1 ) ) ( 2 3 ) 从几何特点上看，上式的一个等价定义为 c ：量盛! 塑垄塑三鱼里塑墼垦( 2 - 4 ) 与点i 相连的三元组的数量 其中，与节点f 相连的三元组是指包括节点f 的三个节点，并且至少存在从节点i 到其他两个节点的两条边。 整个网络的聚类系数c 就是所有节点的聚类系数c ；的平均值。很明显， 0 c l 。c = o 当且仅当所有的节点均为孤立节点，即没有任何连接边；c = i 当 且仅当网络是全局耦合的，即网络中任意两个节点都直接相连。对于一个含有n 个节点的完全随机网络，当n 很大时，c = o ( n 一11 ，而许多大规模的实际网络都 具有明显的聚类效应，它们的聚类系数尽管远小于l 却比o ( n - 1 ) 要大的多。事 实上，在很多类型的网络( 如社会关系网络) 中，你的朋友的朋友同时也是你的 朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当专0 0 时， c = o o ) ，这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上 具有类似于社会关系网络中“物以类聚，人以群分”的特性。 2 1 3 度( d e g r e e ) 与度分布( d e g r e ed is t rib u tio n ) 度( d e g r e e ) 是网络中单独节点的属性值中简单而又重要的概念。节点f 的 度k j 定义为与该节点连接的其他节点的数目。直观上看，一个节点的度越大，就 意味着这个节点在某种意义上越“重要”。网络中所有节点f 的度尼，的平均值( 七) 称 为网络的( 节点的) 平均度。网络中节点的度的分布情况可用分布函数p ( k ) 来 描述，尸( 后) 表示一个随机选定的节点的度恰为k 的概率。 5 硕j j 学位论文第二章预备知识 度分布是复杂网络中的一个重要统计特征量。规则网有着简单的度序列：因 为所有的节点具有相同的度，所以其度分布为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 1 来更好的描述。幂率分 布曲线比p o i s s o n 指数分布曲线下降要缓慢的多。 幂率分布也称无标度分布，具有幂率分布性质的网络也称为无标度网络。在 一个度分布为具有适当幂指数( 通常为2 y 3 ) 的幂率形式的大规模无标度网 络中，绝大部分节点的度相对很低，但存在少数的度相对很高的节点。因此，这 类网络通常称为非均匀网络( i n h o m o g e n e o u sn e t w o r k ) ，而那些度相对很高的节 点称为网络的“集线器”( h u b ) 。例如，美困高速公路网就可以近似的看作是一 个均匀网络，因为不可能有上百条高速公路郜经过同一个城市；而美国航空网可 以看作足一个无标度网络，大部分机场都是小机场，但却存在少量连接众多小机 场的非常大的机场，如芝加哥、达拉斯、亚特兰大和纽约机场。 度分布是复杂网络中的一个重要统计特征量，不同的学者从不同的角度给 出了度分布的精确定义： 定义1 ：在t 时刻从网络中随机选择一个节点，它具有度数k 的概率，记为p ( k ，t ) ， 记为f 时刻网络的瞬时( t r a n s i e n t ) 度分布。当网络演化到无限时，如果极限 l i r a p ( k ，f ) = p q ) 存在，则p ) 称为该网络的稳态( s t e a d ys t a t e ) 度分靠 b a r a b a s i 、a l b e r t 和j e o n g l 2 4 j 首次使用上述定义的度分布，其关键的思想是 随机选择节点而非固定一个节点，因此在平均场方法中假设随机选择的节点f 进 入网络的时间i 是服从( 0 ，t ) 区间上的均匀分布的随机变量。 定义2 ：令。o ) 表示在t 时刻网络中具有度数为后的节点个数，即网络中出现 具有度数为k 的节点的频数，称n 。o ) t 为t 时刻网络的瞬时频率( f r e q u e n c y ) 。 6 硕士学位论文第一二章预备知识 当网络演化到无限时，如果极限! 觋e n t ( t ) t l2 雕) 存在，则尸 ) 称为该网 络的稳态( s t e a d ys t a t e ) 度分布。 k r a p i v s k y 、r e d e n r 和l e y v r a z j 5 1 首次使用上述定义的度分布，原理是根据频 率收敛于概率。 定义3 ：假定尸 ，i ，f ) 表示第f 时刻加入网络的节点在时刻f 有度数k 的概率，称 平均概率m ，f ) 2 了1 善t 尸q _ f ) 为f 时刻网络的平均( a v e r a g e ) 度分布。当网络演 化到无限时，如果极限j 鳃m ，f ) = 尸 ) 存在，则p ) 称为该网络的稳态( s t e a d y s t a t e ) 度分布。 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 】首次使用上述定义的度分布，其本质 在于将所有节点的席分布的平均信定义为网络的度分布。 2 2 复杂网络演化简史 2 2 1 规则图 1 8 世纪伟大的数学家欧拉( e u l e r ) 对著名的七桥问题进行抽象和沦证，开 创了数学中的一个分支：图论( g r a p ht h e o r y ) 。事实上，今天人们关于复杂网络的 研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构与 网络性质密切相关。 网络( n e t w o r k s ) 是节点和连线的集合。如果节点按明确的舰则连线，所得 到的网络就称为规则( 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 ) 中，任意两个节点之间都 有边直接相连。因此，在具有相同节点数的所有网络中，全局耦合网络具有最小 7 硕：b 学位论文 第二章预备知识 的平均路径长度k = 1 和最大聚类系数c = 1 。虽然全局耦合网络模型反映了许 多实际网络具有的聚类和小世界性质，但该模型作为实际网络的局限性也是很明 显的：一个有个点的全局耦合网络有( 一1 ) 2 条边，然而大多数实际网络都 是很稀疏的，它们的边的数目至多是d ( ) 而不是d ( 2 ) 。 一个得到大量研究的稀疏规贝, t j m 络模型是最邻近耦合网络( 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 ) ，其中每一个节点只和它周围的邻居节点相连。具有周期边界 条件的最近邻耦合网络包含n 个围成一个环的点，其中每个节点都与它左右各 k 2 个邻居点相连，这里k 是一个偶数。对于较大的k 值，最近邻耦合网络的 聚类系数为 铲研3 ( k - 2 ) 三( 2 - 5 、) 最近邻耦合网络是高度聚类的，但不是一个小世界网络，对于固定的足值， 该网络的平均路径长度 厶。面n 一( 专o o ) ( 2 - 6 ) 这从一个侧面解释了为什么在局部耦合网络中很难实现需要全局协调的动态过 程( 如同步化过程) 。 另外一个常见的规则网络是星形耦合网络( s t a rc o u p l e dn e t w o r k ) ，它有一个 中心点，其他n 一1 个点都只与这个中心点连接，而它们彼此之间不连接。星形 网络的平均路径长度为 t 埘，= 2 一而2 ( n 两- 1 ) 专2 ( 一o 。) ( 2 7 ) 聚类系数为 e 。= 百n - 1j 1 ( 一) ( 2 - 8 ) 星形网络足比较特殊的一类网络。这早假设如果一个节点只有一个邻居节点，那 么该节点的聚类系数的定义为1 。有些研究文献中则定义只有一个邻居节点的节 点聚类系数为0 。若依此定义，星形网络的聚类系数则为0 。 硕士学位论文第二章预备知识 2 2 2 随机图论 如果节点不是按确定的规则连线，而是按随机方式连线，所得到的网络称为 随机网络。2 0 世纪6 0 年代，由匈牙利数学家e r d o s 和r e n y i 建立的随机图理论【1 】 ( r a n d o mg r a p ht h e o r y ) 被公认为是在数学上开创了复杂网络理论的系统性研究。 在e r d o s 和r e n y i 研究的随机图模型( 称e r 随机图) 中，任意两个节点之间 有一条边相连的概率都为p 。因此，在一个含n 个节点的e r 随机图中，边的总 数是一个期望值为p n ( n - 1 ) 2 的随机变量。由此可以推得，产生一个有n 个节 点和m 条边的e r 随机图的概率为p m 0 一p ) ( 肛1 ) 佗一。 随机图论的一个主要研究课题是当概率p 为多大时，随机图会产生一些特殊 的属性。e r d o s 和r e n y i 系统的研究了当专o o 时，e r 随机图的性质( 如连通 性等) 与概率p 之间的关系。他们采用了如下定义：当专o o 时，产生一个具 有性质q 的e r 随机图的概率是1 ，那么就称几乎每一个e r 随机图都具有性质 q 。e r d o s 和r e n y i 最重要的发现是e r 随机图具有以下涌现或相变性质：e r 随 机图的许多重要性质都是突然涌现的。也就是说，对于任意给定的概率p ，要么 几乎每一个图都具有某种性质q ，要么几乎每一个图都不具有该性质。 e r 随机图的平均度是( 七) = p ( n 1 ) p n ，设朋是e r 随机图平均路径长 度。直观上，对于e r 随机图中随机选取的一个点，网络中大约有( k i l g r 个其他 的点与该点之间的距离等于或是非常接近于肼。因此，no c ( 尼) 锄，即 l 职芘i n n l n ( k ) 。这种平均路径长度为网络规模的对数增长函数的特性就是典 型的小世界特性。因为i n n 的值随n 增长的很慢，这就使得即使是规模很大的 网络也可以具有很小的平均路径长度。 e r 随机图中的两个节点之间不论是否具有共同的邻居节点，其连接概率均 为p ，因此，e r 随机图的聚类系数是c = p = ( k ) n l ，这意味着大规模稀疏 的e r 随机图没有聚类特性。而现实中的复杂网络一般都具有聚类特性。也就是 说，实际的复杂网络的聚类系数要比相同规模的e r 随机图的聚类系数高的多。 o 硕上学位论文第二章预备知识 固定随机图的平均度( k ) 不变，则对于充分大的n ，由于每条边的出现与否 都是独立的，e r 随机图的度分布可用p o i s s i o n 分布来表示： 荆= 陟广譬p 咄) 协9 ， 其中，对于固定的k ，当n 趋于无穷大时，最后的近似等式是精确成立的。 因此e r 随机图也称为“p o i s s i o n 随机图，【2 6 】。 尽管e r 随机图作为实际复杂网络的模型存在明显的缺陷，在2 0 世纪后4 0 年中，e r 随机图理论一直是研究复杂网络拓扑的基本理论，其中一些基本思想 在目前一些复杂网络理论研究中依然很重要，如b 0 1 1 0 b a s 的著作【z 引。人们可以 从多个角度对e r 随机图进行扩展以使其更接近真实的网络。n e w m a n l 2 7 1 介绍了 具有任意给定的度分布的广义随机匡l ( g e n e r a l i z e dr a n d o mg r a p h ) 。给定一个度分布 p 心) ，它表示了网络中度为k 的节点所占的比例。基于这一分布可以按照相同概 率产生多个度序列( d e g r e es e q u e n c e ) 为k i o = 1 , 2 ，n ) 的由n 个节点组成的网 络。这些网络模型的集合成为配置模型( c o n f i g u r a t i o nm o d e l ) 。 2 2 3 复杂网络 规则网是秩序的象征，随机网络足混乱的代表，现实网络不太可能是这两个 极端之一。科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而 是具有与前两者皆不同的统计特征的网络。如果结点按某种自组织原则方式连 线，演化成各种不同的网络，称为复杂网络。 复杂网络的小世界特征、无标度性质和可导航性( s m a l l w o r l de f f e c t ， s c a l e f r e ep r o p e r t ya n dn e t w o r k sn a v i g a b i l i t y ) 是三个非常重要的性质，本节将介 绍相应的耄j l $ 1 j 模型以阐述这些特性的产生机理。 2 2 3 1 小世界模型 美国康奈尔大学理论和应用力学系的博士生w a t t s 及其导师、非线性动力学 专家s t r o g a t z 教授于1 9 9 8 年6 月在n a t u r e 杂志上发表的题为“小世界网络”的 1 0 顾十学位论文 第一章预备知识 集体动力学( c o u e c f i v e d y n a m i c so f s m a l l w o r l f f n e t w o r k s ) 的文章吐开 创性的提出了网络科学中著名的小世界网络概念。 小世界网络的基本模型是w s 模型，算法描述如下【2 】： ( 1 ) 给定规则网：假如我们有一个节点总数为n ，每个节点与它最邻近的k = 2 k 个节点相连的一维有限规则网。通常要求n k21 ： ( 2 ) 改写旧连线：以概率p 为规则网的每条旧连线重新布线，方法是将该连线 的一个端点随机的放置剑一个新位置上，但需要排除自身到自身的连线和重复 连线。 r 目 s r n a l , , m 0n - t 弓 一 z 萝 雾丞 弱苓 9 “1 忑i i 忑忑一9 。 在w s 模型中t 当p = 0 时，对应于完全规则网络p = 1 时则对应于完全随 机网络。通过调节p 的值可以控制从完全规则捌络到完全随机网络的过渡。w a t t s 和s 们脚说明小世界网络在p 值较小的一个范围内同时具有大的聚类系数和短 的平均路径，称为小世界现象或效应( e f f e c t ) 。许多现实的网络都具有这种小世 界效应。 但足，w s 小世界模型构造算法巾的随机化过程有可能破m 、网络的连通性。 改写旧连线机制，w s 模型有可能出现孤立的集四，而且不便1 ：理论分析。 n e w m a n 和w a f t s l 2 8 1 提出了个改进后的模型，通过用“随机化加边”取代w s 小世界模型中的“随机化重连”而得到。具体构造算法如下： ( 1 ) 给定规则网：假如我们有一个节点总数为n 每个节点与它最邻近的k = 2 k 个节点帽连的一维有限衄则网。通常要求n k i ： ( 2 ) 新增随机网：对规则网的n 个节点，以概率础2 在任意两个节点之间连 硕 ：学位论文第一二章预备知识 线，但不改动规则网的原有连线，也不允许自身到自身的连线和重复连线。 在n w 小世界模型中，p = o 对应于原来的最近邻耦合网路，p = 1 则对应于 全局耦合网络。n w 模型实际上是规则网和随机网的叠加，其中增加的捷径总数 仍近似为p n k 2 。在理论分析上，n w 小世界模型比w s 小世界模型简单。对 于很小的p 和很大的n 改进的模型与w s 模型基本等价。 小世界网络模型反映了朋友关系网络中的一种特性，即大部分人的朋友都是 和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是 住得较远的甚至是远在异国他乡的朋友，这种情形对应于w s 小世界模型中通过 加入连线产生的远程连接。 下面介绍小世界网络模型的一些统计性质。 2 2 3 1 1 度分布 在基于“随机化加边”机制的n w 小世界模型中，每个节点的度数至少为 规则网的度数k ，而增加的捷径是以概率p k n 连线，当k k 时，一个随机选 取的节点的度数为k 的概率为 p ，= ( k ) ( 等) 卜石( t 一等) 肛“k 专譬e 唯) c2 邶， 当k k 时，p ( k ) = 0 。 在基于“随机化 重连机制的w s 小世界模型，当k k 2 时有驯 刖= 耐“b h 两( p k 2 ) k - ( x 2 ) - p 嘣_沼 当k k 2 时，尸 ) = 0 。 2 2 3 1 2 聚类系数 w s 小世界网络的聚类系数为【2 9 】 c ( 沪3 4 ( ( k k - 一2 1 ) ) i 、 1 一p ) 3 ( 2 - 1 2 ) n w 小世界网络的聚类系数为 1 2 硕七学位论文第二章预备知识 嘶) = 硒可3 ( 而k - 面2 ) 刁 ( 2 1 3 ) 2 2 3 1 3 平均路，倥长厦 迄今为止，人们没有关于w s 小世界模型的平均路径长度l 的精确解析表 达式，不过，利用重整化方法可以得到如下公式【2 s 】： 0 ) = f ( n k p 2 ) ( 2 - 1 4 ) 其中厂g ) 为一普适标度函数，满足 刷蕊厶“等 协 n e w m a n 等人基于平均场方法给出了如下的近似表达式【3 0 】： 刷丽去a r c t a n 叫壶 c 2 舶， 目前还没有厂b ) 的精确显式表达式。 2 2 3 2 队无标度网络 近年来，经研究发现许多复杂网络包括i n t e n l e t ，力维网【- 1 5 】以及新陈代谢 网络等网络的连接度分布函数具有幂律形式。由于这类网络的节点的连接度没有 明显的特征长度，故称为无标度网络。研究无标度网络，对于防备黑客攻击、防 治流行病和开发新药等，都具有重要的意义。 美国n o t r ed a m e 大学物理系的b a r a b a s i 教授及其博士生a l b e r t 于1 9 9 9 年 一一 1 0 月在s c i e n c e 杂志上发表的题为随机网络中标度的涌现) 1 3 1 ( e m e r e g e n c eo f s c a l i n gi nr a n d o mn e t w o r k s ) 的文章，揭示了复杂网络的无标度性质，他们认为 以前的许多网络模型都没有考虑到实际网络的两个重要特性： ( 1 ) 增长( g r o w t h ) 特性：即网络的规模是不断扩大的。例如，每个月都会有大量 的新的科研文章发表，而w w w 上每天都有大量新的网页产生。 ( 2 ) 优先连接( p r e f e r e n t ；a ia t t a c h m e n t ) 特性：即新的节点更倾向于与那些具 有较高连接度的“大”节点相连接。这种现象也称为“富者更富( r i c hg e tr i c h e r ) ” 1 3 硕i ：学位论文第二章预备知识 或“马太效应( m a t t h e we f f e c t ) ”。例如，新发表的文章更倾向于引用一些被广 泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著 名的站点。 基于网络的增长和择优连接特性，b a r a b a s i 和a l b e a 等提出了一个无标度网 络的模型，简称b a 模型。具体构造算法如下： ( 1 ) 增长：从一个具有m 。个节点的网络开始，每次引入一个新的节点，并且连接 到m 个已存在的节点上，这里m m 。； ( 2 ) 择优连接：一个新节点与一个已经存在的节点f 相连接的概率兀，与节点i 的 度岛、节点的度数乃之间满足如下关系：兀r2 轰 经过f 步之后，这种算法产生了一个具有n = f + m 。个节点、m t 条边的网络。 b a r a b a s i 等人关于无标度网络开创性文献的贡献是：1 提出了一个简洁的模 型，其中增长和择优机理抓住了复杂网络自组织演化的核心思想；2 提出了一种 整体性网络度的概念，采用随机选取的节点度作为节点异质网的代表；3 提出一 套平均场理论方法，使得确定与随机能够有机结合得到正确结果。 2 2 3 2 1 度分布 b a 模型的度分和【3 5 ，1 3 ，2 5 1 为 p ) = 面2 m 而( m + 刁1 ) 2 聊2 矿 ( 2 1 7 ) 这 兑明b a 网络的度分布函数可由幂指数为3 的幂律函数近似描述。 2 2 3 2 2 平均路径长度 b a 无标度网络的平均路径跃度为【3 l _ 3 ：】 j 里生，这表明该网络也具有小世界特性。 ( 2 ，1 8 ) l o g l o g n 2 2 3 2 3 聚类系数 b a 无标度网络的聚类系数为【3 3 】 硕士学位论文第二章预备知识 c 咖斟 i ( 等) 一熹 学 协 这与e r 随机图类似，当网络规模充分人时