（系统分析与集成专业论文）基于双向选择机制的适应度驱动的演化网络.pdf

上海人学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：鏊扭遗日期：塑! ：墨r 。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) i i 期：丝! ! ! 丛 上海大学理学硕士学位论文 基于双向选择机制的 适应度驱动的演化网络 姓名：张柳明 导师：许新建 学科专业：系统分析与集成 上海大学理学院 2 0 10 年4 月 上海大学硕士学位论文 ad i s s e r t a t i o ns u b m i t t e dt os h a n g h a iu n i v e r s i t yf o rt h e d e g r e eo fm a s t e ri ns c i e n c e f i t n e s s d r i v e nn e t w o r k sba s e do n t h em u l t i s e l e c t i o nr u l e m d c a n d i d a t e ：z h a n gl i u m i n g s u p e r v i s o r ：x ux i n j i a n m a j o r ：s y s t e m sa n a l y s i sa n di n t e g r a t i o n s c i e n c ec o l l e g e ，s h a n g h a iu n i v e r s i t y a p r i l 2 0 1 0 上海大学硕士学位论文 摘要 复杂网络往往具有复杂的拓扑结构和动力学行为，当今对于复杂网络的研 究己成为复杂性研究的一个热点。现实世界的许多系统都可以用复杂网络来描 述。研究复杂网络在当今社会的很多领域都有着广泛的应用和重要的意义。 实证研究表明许多现实网络都具有小世界和无标度的特性，特别是无标度 特性是复杂网络研究的一个重大发现。为了解释这一性质，科学家们提出了基 于增长和偏好连接的演化网络模型，其中最为典型的是著名的b a r a b a s i _ a 1 b e r t 无标度演化网络模型。 在偏好连接下，有两类典型的机制。一类是度偏好连接，即节点的度越大， 获得边的概率越大，被称为“富者更富 。另一类机制则是“适者更富”，即节 点获得边的能力与节点的内在适应度有关。在度驱动的机制下，目标节点总是 被动地和新节点相连；而在适应度驱动的机制下，网络两个节点间连边的概率 还与节点的适应度有关，从而就形成了“双向选择”机制。 本论文结合“适者更富”和“双向选择”两种机制，提出了一种新的演化 网络模型，即基于双向选择机制的适应度驱动的演化网络模型。该模型每个节 点都赋予了一个相应的适应度x ，其值取自于一个给定的适应度分布函数p ( x ) 。 在演化过程中，要么以概率p 增加1 个新点进入网络，其具有适应度y ，根据 双向选择机制的连接概率函数f ( x ，y ) 偏好选择网络中的1 个节点并进行连接； 要么以概率1 - p ，也以同样的连接概率函数f ( x ，y ) 偏好连接网络中已有的2 个 节点。我们分别从理论和数值两个方面计算了模型的度分布，发现其呈单调递 减趋势。当适应度是均匀分布的时候，度分布遵从指数衰减行为；当适应度分 布不均匀的时候，度分布是幂律衰减的。进步，我们模拟了模型的聚类系数 和平均最短路径长度，发现该模型体现了较好的小世界特性。 关键词： 复杂网络；无标度网络；适应度。 v 上海大学硕上学位论文 a b s t r a c t c o m p l e xn e t w o r k so f t e nh a v ec o m p l e xs t r u c t u r e sa n dd y n a m i c s r e c e n t l y , r e s e a r c hi nc o m p l e xn e t w o r kh a sb e c o m eah o ts p o ti nt h es t u d yo fc o m p l e x i t y t h e r e a l - w o r l ds y s t e m sa l w a y sc a nb ed e s c r i b e d b y c o m p l e xn e t w o r k s s t u d y i n g c o m p l e xn e t w o r k sh a sp r o v i d e du sw i t hw i d e l ya p p l i c a t i o n si nm a n ya r e a so ft h e s c i e n c e t h er e s e a r c h e ss h o wt h a tm a n yr e a ln e t w o r k sh a v et h es m a l l - w o r l da n d s c a l e f r e ep r o p e r t i e s e s p e c i a l l y , t h eb e h a v i o ro ft h es c a l e f r e ec o m p l e xn e t w o r ki sa m a j o rd i s c o v e r y i no r d e rt oe x p l a i nt h i s ，t h es c i e n t i s t sh a v es u g g e s t e dn e t w o r k m o d e l se v o l v e db a s e do ng r o w t ha n dp r e f e r e n c e t h em o s tt y p i c a lm o d e li st h ew e l l k n o w nb a r a b a s i a l b e r ts c a l e f r e en e t w o r k i np r e f e r e n t i a la t t a c h m e n t ，t h e r ea r et w ot y p i c a lm e c h a n i s m s o n ei s d e g r e e p r e f e r e n c e t h el a r g e rd e g r e eav e r t e xh a s ，t h eh i g h e rp o s s i b i l i t yi tw i l lg e tn e w e d g e s ，w h i c hi st h es o - c a l l e d ”r i c h g e t r i c h e r ”t h eo t h e ri st h e ”f i t t e r - g e t r i c h e r ” m e c h a n i s m ，w h i c hm e a n st h a tt h en o d e sa b i l i t yt og e tt h ee d g ei sr e l a t e dt ot h e v e r t i c e si n t r i n s i cf i t n e s s i nt h ed e g r e e - d r i v e nm e c h a n i s m ，t h ee x i s t e dv e r t e xi s a l w a y sc o n n e c t e dt ot h en e wv e r t e xp a s s i v e l y i nt h ef i t n e s s - d r i v e nm e c h a n i s m ，t h e l i n k i n gp r o b a b i l i t yb e t w e e nt h et w ov e r t i c e si sr e l a t e dt ot h et h e i rf i t n e s s e s ，w h i c hi s c a l l e d ”m u l t i s e l e c t i o n ”r u l e c o m b i n i n gt h e ”f i t t e r - g e t r i c h e r ”m e c h a n i s ma n d ”m u l t i s e l e c t i o n ”r u l e ，w e p r o p o s et h ef i t n e s s - d r i v e nn e t w o r k sb a s e do nt h em u l t i - s e l e c t i o nr u l e i nt h i sm o d e l ， av e r t e xi sa s s i g n e daf i t n e s sx ，d r a w nf r o mag i v e np r o b a b i l i t yd i s t r i b u t i o nf u n c t i o n p ( x ) d u r i n gn e t w o r ke v o l u t i o n ，w i t hr a t epw ea d dav e r t e xo ff i t n e s sya n dc o n n e c t t oa ne x i s t e dv e r t e xo ff i t n e s sxs e l e c t e dp r e f e r e n t i a l l yt oal i n k i n gp r o b a b i l i t y f u n c t i o nf ( x ，y ) w h i c hd e p e n d so nt h ef i t n e s s e so ft h et w ov e r t i c e si n v o l v e d a n dw i t h r a t e1 - p ，w ec r e a t ea ne d g eb e t w e e nt w o a l r e a d ye x i s t e dv e r t i c e sw i t l lf i t n e s s e sxa n d y ，w i t hap r o b a b i l i t ya l s op r e f e r e n t i a lt ot h ec o n n e c t i o nf u n c t i o nf ( x ，y ) w ec a l c u l a t e v i 上海大学硕士学位论文 t h ed e g r e ed i s t r i b u t i o nt h e o r e t i c a l l ya n dn u m e r i c a l l y f o re v e r yf i x e dx ，t h ed e g r e e d i s t r i b u t i o no ft h e g e n e r a t e dn e t w o r ki sr i g h t - s k e w e d i nc a s eo fh o m o g e n e o u s f i t n e s s e s ，t h ed e g r e ed i s t r i b u t i o nf o l l o w sa ne x p o n e n t i a l ，w h i l ef i t n e s s e sd i s t r i b u t e h e t e r o g e n e o u s l y , t h ed e g r e ed i s t r i b u t i o nd e c a y s 嬲s c a l e - f r e e s i m u l a t i o n so ft h e c l u s t e r i n gc o e f f i c i e n ta n da v e r a g es h o r t e s tp a t h - l e n g t hr e f l e c tt h e s m a l l w o r l d c h a r a c t e r i s t i c so ft h ep r e s e n tm o d e l k e y w o r d s ：c o m p l e xn e t w o r k s ；s c a l e f r e en e t w o r k s ；f i t n e s s v i l 上海大学硕士学位论文 目录 第一章绪论1 1 1 课题来源l 1 2 课题研究的目的和意义1 1 3 国内外研究状况2 1 3 1 国外研究状况2 1 3 2 国内研究状况3 1 4 论文的主要研究内容4 第二章复杂网络的基本概念5 2 1 复杂网络介绍5 2 1 1 网络与图论5 2 1 2 复杂网络的结构6 2 2 复杂网络的基本参数6 2 2 1 度和度分布一6 2 2 2 聚类系数7 2 2 3 路径和平均最短路径长度7 2 3 复杂网络模型概述8 2 3 1 规则网络。8 2 3 2 随机网络9 2 3 3 小t 日= 界网络1 1 2 3 4 无标度网络1 4 第三章适应度驱动的相关网络建模1 7 3 1 适应度驱动网络的基本概念1 7 3 2 基于适应度驱动的b a 修1 模型1 8 3 3 基于双向选择机制的适应度驱动的静态网络1 9 3 4 基于半双向选择机制的适应度驱动的演化网络2 0 上海大学硕士学位论文 第四章基于双向选择机制的适应度驱动的演化网络模型2 4 4 1 模型2 4 4 2 度分布2 5 4 3 数值模拟结果2 8 第五章结论与展望3 6 5 1 结论3 6 5 2 展望3 7 参考文献3 8 作者在攻读硕士学位期间公开发表的论文4 3 致谢4 4 上海人学硕士学位论文 1 1 课题来源 第一章绪论 本课题来源于国家自然科学基金项目。 1 2 课题研究的目的和意义 进入2 0 世纪8 0 年代后，由于科技水平得到了迅速发展，人类在各个领域 的研究都取得了重大的突破。特别是计算机和互联网的崛起，推动了信息革命 的迅猛发展，也促使社会大步迈入了日新月异的网络新时代。 这个时代特征体现在我们生活的各个方面。现实世界中的许多系统都可以 用复杂网络来描述，如社会网络中的科研合作网 1 、社会关系网 2 ，3 、信息 网络中的万维网 5 、科研引用网 6 、生活中的电力网 7 - 9 、航空网 1 0 ，1 1 、 生物网络中的代谢网 1 2 与蛋白质网络 1 3 等，我们已经生活在一个充满着各 式各样的复杂网络的世界之中。 另一方面，日益加速的社会网络化要求人类对各种复杂网络的结构和性质 有更清楚的认识和驾驭。从2 0 世纪9 0 年代开始，复杂网络的研究逐步形成了 一个自我完备的学科，甚至被称为“网络的新科学 1 4 ，1 5 。 复杂网络的研究正在逐渐打破各学科之间的壁垒，成为一门大范围学科的 新兴领域。以前被认为互不相交的研究学科，而今天已被许多的复杂网络的理 论分支所包揽。复杂网络的基本理论正渗透到从数理科学到生命科学、工程科 学甚至社会科学等众多不同的领域中去。所以，复杂网络的研究已经成为了近 年来全世界在不同学科领域中的科学家们的研究热点。 正如著名的物理学家霍金曾讲过：二十一世纪是复杂性的世纪。现实网络 系统的复杂性主要体现在三个方面：首先，网络的结构非常复杂，对网络节点 间的连接，至今仍没有很清晰的概念；其次，网络是不断演化的，网络节点不 断地增加，节点之间的连接在不断地增长，而且连接之间存在着多样性；第三， 网络的动力学具有复杂性，每个节点本身可以是非线性系统，伴随着分岔和混 上海大学硕士学位论文 沌等非线性动力学行为而且在不停地变化。 复杂网络的研究是复杂性理论研究的重要一部分。作为研究复杂性科学和 复杂系统的有力工具，复杂网络为研究复杂性提供了全新的视角。复杂网络借 助于图论和统计物理的一些方法，可以用来捕捉并描述系统的演化规律( 结构) 和整体行为( 功能) ，这是研究复杂网络的目的，也是复杂网络研究蓬勃发展的 主要原因。 然而，这种全球网络化时代的复杂网络就如一把双刃剑。它既给人们带来 了很多的方便和利益，如电话手机和电子邮件通信以及g p s 交通导航等，极大 地提高了人类的生产效率和生活品质，但在另一方面也有它的弊端，它给人类 生活和社会活动带来了不少新的麻烦，如传染病和计算机病毒的快速传播，以 及大面积停电事故等。 所以，如今对复杂网络的定性与定量特征的认识和理解已成为网络新科学 研究中一个共同而又极其重要的挑战性课。同时，复杂网络理论已经在许多方 面展现出广泛、潜在的应用价值。所以复杂网络的研究对当今社会的进步具有 重要意义。 1 3 国内外研究状况 1 3 1 国外研究状况 国外研究对复杂网络的拓扑结构研究经历了如下的阶段： 从1 8 世纪起，数学家e u e l r 对七桥问题的抽象和论证思想，开创了数学中图 论的研究 1 6 ，1 7 ，e u e l r 也因此被称为“图论 之父。 2 0 世纪5 0 年代末期，匈牙利数学家p a u le r d o s 和a l f r e dr e n y 首次将随机性 引入网络的研究，提出了著名的随机网络模型( e r 模型) 1 8 ，1 9 。在2 0 世纪的后 4 0 年中，e r 随机图理论一直是研究各种网络的基本理论，其中的一些基本思想 在目前的复杂网络研究中仍很重要。 1 9 6 7 年美国社会心理学家m i l g r a m 通过“小世界试验”提出了“六度分离推 断 。随后，一些数学家也对此进行了严格的证明。如今，小世界特性已在许多 网络中得到了证实。1 9 9 8 年，w a t t s 和s t r o g a t z 在e r 模型基础上，对比真实网络 2 上海大学硕士学位论文 提出了小世界模型( w s 模型) ，实现了从完全规则网络到完全随机图的过渡，该 模型既具有规则网络的高聚类性，又具有类似随机网络的小的平均路径长度 2 0 。由于w s d , 世界模型构造算法中的随机化过程有可能破坏网络的连通性。 1 9 9 9 年n e w m a n 和w a t t s 提出了n w t , 世界模型 2 1 ，它用“随机化加边”代替了w s 小世界模型构造中的“随机化重连”。当p 足够小和n 足够大时，n w d , 世界模型本 质上等同于w s d , 世界模型 2 2 ，2 3 。 1 9 9 8 年，b a r a b a s i 和a l b e r t 发现了实际网络的两个重要特征：增长性和优先 连接性，提出了无标度网络模型( b a 模型) 2 4 ，揭示了复杂网络的度分布具有 幂律形式，开辟了人们对于复杂网络系统认识的新天地。其后几年中，各行各 业的研究者们在许多不同的领域中，都发现了网络的无标度特性，其表现出的 特性是：大多数的节点只与一两个少数节点相连接，但有少数节点却被大量的 连接。 1 3 2 国内研究状况 在国内，也有大量的研究者从事复杂网络的研究工作，并且取得一定的突 破。国内学者对国外复杂网络理论研究的介绍较早的是2 0 0 2 年汪小帆发表的一 篇文章 2 5 ，文中回顾了近年来国外复杂网络研究所取得的重要成果，其中包 括平均最短路径长度、聚类系数、度分布等网络度量，i n t e r n e t 、w w w 和科学合 作网络等现实系统，规则网络、随机网络、小世界网络、无标度网络等网络模 型，以及复杂网络上的同步等。此后，吴金闪等人 2 6 从统计物理学的角度总 结了复杂网络的主要研究结果，对无向网络、有向网络和加权网络等三种不同 网络统计性质研究的现状分别作了综述，对规则网络、完全随机网络、小世界 。网络和无标度网络等网络机制模型进行了总结，并对网络演化的统计规律、网 络上的动力学性质的研究进行了概括。 2 0 0 5 年，周涛等围绕小世界效应和无标度特性等复杂网络的统计特征及复 杂网络上的物理过程等问题，概述了复杂网络的研究进展。刘涛等 2 7 从平均 最短路径长度、聚集系数、度分布等复杂网络的统计性质，小世界网络和无标 度网络等网络模型等层面简述了复杂网络领域的相关研究。史定华 2 8 从对网 络节点度和度分布的理解入手，对网络分类、网络的演化机理和模型及结构涌 上海大学硕士学位论文 现等方面取得的进展进行了总结。 总的来说，这些介绍都突出了对复杂网络上的统计性质、复杂网络经典模 型的阐释和描述，对复杂网络理论在国外研究进展的有了较全面的介绍。 1 4 论文的主要研究内容 本论文是以作者攻读硕士学位期间承担课题的工作为基础，在第一章中阐 述了课题研究的来源、目的、意义以及国内外研究的现状。第二章介绍了复杂 网络的基本概念和其典型的网络模型。第三章叙述了适应度驱动的相关网络建 模和基于适应度驱动的演化网络分析。第四章提出了基于双向选择机制的适应 度驱动的演化网络模型，并且进行了数值模拟结果。最后第五章总结全文并给 出展望。 4 上海大学硕士学位论文 第二章复杂网络的基本概念 2 1 复杂网络介绍 在数学上我们可以用图论中精确简洁的符号和语言来描述复杂网络。图论 的研究最早起源于1 8 世纪瑞士著名数学家e u e l r 的哥尼斯堡七桥问题。图论不 仅为数学家和物理学家提供了描述网络的语言和研究的平台，而且其结论和技 巧已经被广泛地移植到复杂网络的研究中。为了能够方便准确地表达复杂网络 的统计性质，有必要先介绍一些图论和网络的基本知识 2 9 。 2 1 1 网络与图论 网络g = v ，e ) 作为图论的概念是指一个点集v g ) 和一个边集e g ) 组成的一 个图，如图2 1 1 1 。其中v g ) 中元素称为节点或顶点( v e r t e x ) ，e g ) 中元素 称为边( e d g e ) 。且e g ) 中的每条边有v g ) 的一对节点 u ，v ) 与之对应。记顶点 数n = l v l ，边数为e = i e i 。如果e g ) 中任意的节点对( u ，v 和 v ，u ) 对应同一条 边，则该网络称为无向网络，否则为有向网络。如果e g ) 中所有边的长度均为 1 ，即l 。j = l ，则称网络为无权网络，否则为加权网络。从统计物理学的角度 来看，网络是一个包含了大量个体以及个体之间相互作用的系统，是描述系统 现象及其内部关系的图。 图2 1 1 1 一个具有8 个点和1 0 条边的简单网络图。 上海大学硕上学位论文 2 1 2 复杂网络的结构 那么，现在我们可以从数学的角度来理解一个复杂网络的结构 3 0 ，3 1 。一 个复杂网络可以用一幅图来表示。每一幅图或网络都是由两个基本元素组成的： 节点和边。可以这样理解：网络节点为系统元素，边为元素间的互相作用。例 如一个节点可以代表互联网上的一台计算机、神经网络中的一个细胞、社会网 络中的一个人等等，而一条边可以代表互联网上的一条光纤、神经网络中的一 根经络、社会网络中的社会关系等等。所以，现实世界中的许多复杂系统都可 以用一个复杂网络或者一幅图来描述。 由于节点和边之间存在不同的联结方式，就具有不同的拓扑结构并且可以 具有非常不同的特性和行为，因而需要用不同的复杂网络模型来描述。 2 2 复杂网络的基本参数 在复杂网络的研究过程中，人们发现网络的拓扑结构在决定所研究系统的 动力学中起着重要的作用，网络的拓扑结构主要由其三个基本的几何参数描述， 即度分布、聚类系数、平均最短路径长度。 2 2 1 度和度分布 度( d e g r e e ) ：网络中任意一个节点的度通常定义为该点具有的连接边的个 数。它是网络研究中最基本的量。例如，有6 条连接边的节点的度就是6 。度 在不同的网络中所代表的含义也不同，如在社会网络中，度可以表示个体的影 响力和重要程度，度越大的个体，其影响力就越大，在整个组织中的作用也就 越大，反之亦然。 度分布( d e g r e ed i s t r i b u t i o n ) 则是表示节点度的概率分布情况，可以用函 数p ( k ) 表示，它指的是节点有k 条边连接的概率，即网络中随机挑选一个点其 具有k 条连接的几率为p ( k ) 。它是网络研究的一个重要统计特征。对网络中所 有点进行统计，即可得到整个网络的度分布。 6 上海大学硕士学位论文 2 2 2 聚类系数 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 也称为成团系数。网络中的一个集团 是指由一系列的点组成的一个集合，其中的任一个点和该集合中的其它的点都 连通。聚类系数是指网络集团化的程度，即考察连接在一起的集团各自的近邻 之中有多少是共同的近邻。它是用来刻画所关心的某个节点它的直接邻居节点 之间也互相连接的稠密程度，定义为0 到1 之问的一个实数值。假如，某个节 点i 有k ；个最近邻，那么在这些最近邻中最多可能存在k ；( k 。- 1 ) 2 条连接，用 e ；表示这些最近邻的点之间实际存在的连接，则点i 的聚类系数定义为： c ；： 星i：堡 1 k i ( k i 1 ) 2k i ( k i - 1 ) 再例如，假定某节点a 的度为5 ，即它有5 个邻居节点；如果这5 个邻居都 互不相连，则节点a 的聚类系数为0 ，但如果这5 个邻居全都互相连接，则节点a 的聚类系数为1 。 整个网络的聚类系数定义为它所有节点聚类系数的平均值，即对网络中所 有的c ；取平均值，就可以得到整个网络的聚类系数c ，它描述了网络中点与点 集结成团的趋势。 2 2 3 路径和平均最短路径长度 路径( p a t hl e n g t h ) ：两个节点之间的路径可以有许多不的定义，其中最简 单也最常用的就是它们之间最短连边的条数，也称为最短路径长度。如果两点 之间不存在通路，起路径长度记为n 。所以，在无向、无权网络中，任意两点i ， j 之间的最短路径长度l 定义为从点i 到点j 所有连接两点的通路中所经过 其他顶点最少的一条或几条路径所包含的连接的个数。例如，假定节点a 和节点 b 直接相连，那么它们的距离是1 ；如果它们连接的最短路径要通过另一个节点 c ，那么它们的距离就是2 。 平均最短路径长度( a v e r a g es h o r t e s tp a t h l e n g t h ) ：一个网络的平均最 短路径长度则定义为该网络上所有存在的节点距离的平均值： 上海大学硕：l 学位论文 r 一1 1 2 + 3 + + 厶。+ 乞3 + 乞4 + + 厶。+ 。- - 乞2 除了上面三个最重要的参数，网络还有其它参数，如介数及其分布、最大 连通分支的规模分布、混合模式、度相关性、模块性等。具体详细的内容可以 参考相关文献 3 2 - 4 6 。 2 3 复杂网络模型概述 我们要对不同的复杂网络进行描述和研究，首先要对它们建立相应的数学 模型。对网络模型作严格分类是相当困难的。但大致上复杂网络可以划分为三 大类型：首先是规则网络和随机网络：这两种极端类型的网络能明确地定义， 其中规则网络包括全连接网络，环形、链形、星形网络以及格点和分形图等非 常规则的确定性网络，而随机网络则指按照某种明确的统计规律生成的网络， 主要是经典的随机图模型及其派生出来的相关模型。其他一般性的网络模型只 能笼统地归到第三类了，是介于规则和随机网络模型之间的、有一定的规则但 也有一定的随机性的所有其他网络。这是一个很大的类别，其中包括相当重要 的小世界网络和无标度网络、以及加权网络和演化网络等等。 以下将分别介绍规则网络、随机网络、小世界网络和无标度网络。 2 3 1 规则网络 规则网络是最简单、但也是研究历史最长的一类网络，可以追索至1 j 1 7 3 6 年 e u l e r 的七桥问题 1 6 ，1 7 ，甚至更早。在很长一段里，人们认为真实系统各因素 之间的关系可以用一些规则网络表示。除了像全连接网络，环形、链形、星形 网络以及格点和分形图等非常规则的确定性网络之外，用得最多的规则网络是 由n 个节点组成的广义近邻网络，网络中每个节点只与它最近的k 个节点连接。 在规则网络中，每个节点具有相同的度和聚类系数。通常节点的度分布为 6 函数，即p ( k ) = 6 ( k k ) ；节点聚类系数为c ：3 ( k - 2 d ) ( d 为网络维数) ，其中 4 ( k d ) 每个节点只与它最邻近节点的聚类系数比较高，集聚程度较高，平均最短路径 长度也比较长。一维规则网络的平均最短路径长度l 较大，与节点数成线性比 上海大学硕上学位论文 例关系，即d n 2 k 。 2 3 2 随机网络 随机图( r a n d o mg r a p h ) 的数学理论始于1 9 5 9 年匈牙利数学家p a u le r d o s 和a l f r e dr e n y i 的一篇经典论文e 1 8 ，并发现概率统计理论在图论的研究中非 常有用，并据此提出了e r 随机图理论 1 9 3 ，应用于网络则称为随机网络模型 ( e rm o d e l ) 。由于网络具有复杂的结构和未知的组织原理，从而总表现出一定 的随机性。因此在早期的工作中，随机图模型往往被采用。此时，更多的从统 计的角度研究图论及其算法。 e r 模型构造方法一：选定尺寸为n 的网络( 网络中有n 个研究对象，即有 n 个节点) ，那么在这n 个节点之间总共可以存在n ( n 一1 ) 2 条可能的连接，以 概率p 去选择这些连接，那么最后网络中会存在p n ( n 1 ) 2 条连接。如图2 3 1 所示，在尺度为1 0 的网络中，以概率0 1 去选择连接，则网络中最后出现的连 接数大概为0 1 1 0 ( 1 0 - 1 ) 2 = 5 。 e r 模型构造方法二：在随机图中，实际连接数是一个随机变量，其期望值 为e ( n ) = p n ( n - 1 ) 2 。从n 个节点中任意选择两点，若没有连接则连之，反之重 新选择两点，重复这一过程，直到m 条连接全部用完。则我们得到一个有n 个 点和m 条连接的随机图g ( n ，p ) 的概率为p ( n ，p ) = p l ( 卜p ) n ( n - i ) 2 - m 。 p = ( ) p = 0 15 图2 3 2 1n = i o ，不同概率p 的随机图演化过程。 以下我们以第一种定义为主讨论随机图的几何性质，其结论对于第二种定 义也是成立的。在有n 个节点的随机图里面，某一个节点i 的度为k ；的概率分 布服从一个二项式分布： 9 上海大学硕士学位论文 p ( k f = 七) = c 。k 一p ( 1 一p ) 1 一， 这是因为在剩余的n 一1 个点中任意选择k 个点和点i 相连的时候总共会有c ：。 种选择，被随机选择的这k 个点都必须和点i 相连，其总的概率为p 。，此时网 络中其它的所有点则都不能和点i 相连，其总的概率为( 1 - p ) h 吨。当卜 时，( 2 3 2 1 ) 式可以化为： 雕) = 以1 刊n - i - k 等p 训= 等e 埘 ， 近似为一个泊松分布。图2 3 2 2 给出了n = 1 0 0 0 0 ，p = 0 0 0 1 随机网络的度分布 与相同期望值的泊松分布，二者符合得很好。 随机图的平均最短路径长度可以用下式来描述 ， i n n i n ( n ) i n ( p n ) i n 如果我们考虑随机图中的一个节点和它的最近邻的节点，那么它的最近邻 中任意两节点相连的概率就等于在整个网络中我们任意选择两点时，这两点相 连的概率。因此，随机网络的聚类系数可以写出： 如p = 鲁， 从上式我们可以看到，随机网络的聚类系数c 就等于网络中任意的点与点之间 的连接概率p 。 图2 3 2 2n = 1 0 0 0 0p = 0 0 0 1 的e r 图的度分布图。 总之，随机网络的节点度服从p o i s s o n 分布，因而比较“均匀”，即大部分 l o 上海大学硕士学位论文 的节点度相差不多，并且它具有较小的平均最短路径长度和较小的聚类系数。 e r 随机网络模型在提出后、直到2 0 世纪9 0 年代，在近4 0 年时间里逐步发展 成了- i - j 博大精深的数学分支。无明确设计原则的大规模网络主要用这种简单 而易于被多数人接受的随机图的拓扑结构来描述，即认为大规模网络的形成过 程中，节点间的连接是完全随机的。期间，一些数学家对随机图进行了非常好 的研究，衍生出不少变种，也成为了描述各种复杂网络的主要工具。通过严格的 数学证明，得到了许多近似和精确的结果 1 9 ，2 0 。 2 0 世纪9 0 年代末以后，由于现代大型高速计算机数据处理和运算能力的 飞速发展，人们对各种复杂网络进行了大规模的仿真试验，结果发现现实世界 中绝大多数的网络既不是完全规则的、又不是完全随机，而是具有其他统计特 征的网络，于是提出了一些更符合实际的网络模型，其中小世界网络和无标度 网络模型十分成功地描述了许多现实中的复杂网络。 2 3 3 小世界网络 图2 3 3 1 s t a n l e ym i l g r a m 的传信试验 1 9 6 7 年，美国心理学家s t a n l e ym i l g r a m 对社会网络结构进行研究，设计出 著名的“传信”试验，如图2 3 3 1 。该试验证明：这些信件从开始传送到最终 到达目标人，平均传送了六次传递，重复多次试验也总是得出相近的结果。 m i l g r a m 称之为“小世界 ( s m a l lw o r l d ) 现象，即对于大多数的网络，不管其 上海大学硕士学位论文 尺寸有多大，任意两点间总有一条相对较短的路径。 1 9 9 8 年，美国c o r n e l l 大学理论和应用力学系的博士生w a t t s 及其导师 s t r o g a t z 提出了介于规则晶体和完全随机图之间的单参数的小世界网络模型 ( w sm o d e l ) 2 0 ，该模型可以较好的体现社会网络的小世界和大集团两种现象。 所以，具有小的平均最短路长度和高的聚类系数的网络被称为小世界网络。 小世界网络模型的演化如下： ( i ) 初始条件：从一个含有n 个点的规则图开始，所有的节点连接成一个 环，每个节点都与它左右相邻的各k 2 节点连接，且k 是偶数。 ( i i ) 随机化重连：以概率p 随机地重新连接网络中的每条边，即将边的一 个端点保持不变，而另一个端点取为网络中随机选择的一个节点。但任意两个 不同的节点之间至多只能有一条边，且每个节点都不能有与自身相连的边，即 网络中无重边和圈。 由上述模型的算法可知，当p = o 时对应于完全规则网络，而当p = l 时对应 于完全随机网络，通过调节概率p 的值就可得到从规则网络到随机图网络的过 渡网络，如图2 3 3 2 所示。 概概胍 图2 3 3 2w s 模型的随机连线过程图 w a t t s 和s t r o g a t z 由此开创性论文的发表掀起了小世界网络和小世界模型 的研究高潮。 下面介绍小世界网络模型一些拓扑特征：度分布、平均最短路径长度和聚 类系数。 当k 兰k 2 时，小世界网络的度分布为： p(k)=删”力p(k2)-n丽(pk2)k-(r12rtm e 倒，2 1 2 上海大学硕士学位论文 r 图2 3 3 3 w s 模型的度分布图，其中k = 4 ，n = 1 0 0 0 0 ，p 取各种值。 图2 3 3 3 给出了w s 模型当n = 1 0 0 0 0 、k = 4 时的度分布，呈单峰形状即在 = k 处的几率最大，所以小世界网络相对来讲是一个均匀的网络，其中的节 点的度可以近似地认为是相同的。 利用重正化群和序列展开方法，可得到w s 小世界网络的平均最短路长度 为： 蝌加詈厂( 脚) ， 其中d 为网格的维数，函数f ( u ) 满足一下关系： w s 小世界网络的聚类系数为： c ( 加黼”p ) 3 对于小世界网络，其平均最短路径长度和聚类系数均可表示成概率p 的函 数，如图2 3 3 4 ，显示了网络的平均最短路径长度和聚类系数随着重连边概率 p 的变化关系。由此图可知，当p 增加时，其平均最短路径长度下降很快，而 其聚类系数下降地很慢。 l x ，t 、，| 刍mc ( ，f1l i i “ ， 上海大学硕十学位论文 图2 3 3 4w s 模型的平均最短路径长度l 和聚类系数c 与重连几率p 的关系。 2 3 4 无标度网络 由于e r 模型和w s 模型的度分布与许多现实网络都不相符，用它们来描述 这些现实网络，具有很大的局限性，因此科学家们寻求了另一种模型，来更好 地描述这些现实网络。 1 9 9 9 年，美国b a r a b a s i 教授和他的博士生a l b e r t 从统计物理的观点出发 2 4 ，通过追踪万维网的动态演化过程，发现了许多复杂网络都具有的一种大 规模的高度自组织特性，其中网络的节点度服从幂律分布：k 一，其中k 是节点度 变量，而r 是一个与标度无关的常数，并把具有幂律度分布的网络称为无尺度网 络( s c a l e f r e en e t w o r k ) 。形成这种无标度网络的两个要点是节点增长性和择 优连接性。具体的演化过程图如图2 3 4 1 。下面介绍无标度网络的演化过程的 具体算法： ( i ) 增长性：网络开始于m o 个孤立的节点，在每个演化时间里，有一个新的 节点加入到网络中，且此节点与原来的m ( i i l 0 ) 个节点相连。 ( i i ) 择优连接性：新节点与原来的节点相连接的概率与节点的度成j 下比， 即设节点i 的度为k 。，则新节点与它相连的概率为： 丌( p 2 轰 1 4 上海大学硕： ：学位论文 在时刻t 时，网络中含有n = t + l l l 0 个节点和m t 条边。 勺 飞莎刁驿 曝曝鼹纭氏 图2 3 4 1b a 模型的演化过程图m o ：2 使用平均场方法，假设网络中节点的度k 是连续的，则择优连接概率可认 为是关于k ；连续变化的，则有： o d k - - - r t - = a1 - i ( k j ) = a k i i 考虑到乃= 2 r o t ，且每一个时间步度的变化为k = m ，则有a = m ，从而有： 8 k t k t 百一万 考虑节点i 在时刻t ；的度为k ；( t ；) ，则上式的解为： t ( r ) = 肌( 号) l ，2 ， 由于每一个时间步内只增加一个新的节点，则时刻t ；的概率分布函数为： 即护去， 从而 脚心”警= l _ 讹警斗而m 丽2 t ， 因此，无标度网络的度分布为： 孵盟o 幽k = 筹m t 古， 一 。+ 露y 由此式可知，无标度网络的度分布服从幂律分布，且幂律指数为：7 = 3 ，且它 独立于m 。即b a 模型的度分布与网络尺度无关，遵从p o w e r - 1 a w 规律。度分布 上海大学硕士学位论文 图，如图2 3 4 2 。 k 图2 3 4 2b a 网络的度分布图，其中网络尺寸n = 1 0 0 0 0 0 之后，a l b e r t 和b a r a b a s i 在b a 模型中引进了小世界的那种随机重新连接边 的机制，得到