（系统分析与集成专业论文）基于序钝化的演化网络模型.pdf

签 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅：学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签胡越参燧名： i i i 姓名：周明琛 导师：许新建 学科专业：系统分析与集成 上海大学理学院 二零一零年四月 一令一令，牛四月 i v i ：海人学顺l ：学垡笙塞 一一一 _-_-_-_-_-_-_-_-_-_-_一一一一 一 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 y f o rt h ed e g r e eo fm a s t e ri ns c i e n c e r a n k - d e p e n d e n t d e a c t i v a t i o ni nn e t w o r k e v o l u t i o n m d c a n d i d a t e ： m i n g c h e n z h o u s u p e r v i s o r ：x i n j i a n x u m a jo 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 v 海人学顺i ：学位论义 摘要 近年来，复杂网络方面的研究成果f 1 渐丰富，网络科学已经形成很多具体的 研究方向。特别地，网络的演化机制不断创新，考虑的条件越来越贴近真实网络， 学者们从不同的角度对网络的演化进行了模拟实验，从中发现了很多真实网络所 具备的良好性质，进而对真实网络进行了很好的诠释。 一 目前网络演化机制中的两大新进展，是钝化机制，网络节点并不是始终保 持积极态，例如科学家引文网络中，科学家的科研生命周期总是有限的；二是排 序机制，网络演化中新进节点择优选择旧节点时，往往很难获得旧节点的绝对信 息，而相对信息却是很容易获得的。 本文综合考虑了上述两大机制。首先，针对无权网络，我们对积极态节点的 排序是按节点加入网络的时刻来排序( 即按节点的年龄排序) ，尺( f ) = t 。然后按 序值的大小来钝化节点，钝化概率为h ( r ，) = 七。我们重点研究了网络的度 a k j 分布、聚类系数、最近邻平均度、网络的直径和最短路径长度等结构参量。在口= 0 时，我们得到度分布为幂律分布，而在口= n 时，我们得到度分布为指数分布。局 部聚类系数为c ( k ) 一七一。此外根据所得到的最近邻平均度( 七肼) 的数值模拟结果， 我们发现了该模型呈现负的度相关性。而平均最短路径长度l 和网络直径d 这两 个量都随着网络的尺度n 的增长而线性增长，这有点类似一维晶格。也就是说， 钝化模型中没有显示出小世界的属性。然而模型的链式结构并不意味着平均最短 路径长度l 和网络的直径d 的值一定很大。在我们的模型中，平均最短路径长 度l 和网络直径d 相对于网络的尺寸n 而言都仍然是小的。特别是当口= 0 时， 这种效果更为明显。 其次，针对加权网络，我们对积极态节点的排序是由权重的大小来决定的， 再按序值的大小来钝化积极态节点，钝化概率为n ( r ) ，( 口+ r ) 。我们重点研 究了该模型的度与强度的分布。类似地，在口= 0 时，我们得到度及强度分布为 幂律分布，而在口= n 时，我们得到度及强度分布为指数分布。 关键词：复杂网络，权重网络，排序，钝化 海人学f i ! j ! f j 学位论义 a b s t r a c t r e c e n t l y ，t h es t u d yo fc o m p l e xn e t w o r ki n c r e a s i n g l yg e t sr i c h t h e n e t w o r ks c i e n c eh a sf o r m e dm a n ys p e c i f i cr e s e a r c hd i r e c t i o n s ，w h i c hh e l p s c i e n t i s t sc o n s t a n t l ye x p l o r en e ww a y st os i m u l a t es y s t e m si nt h er e a l w o r l d c u r r e n t l y ，t h e r ea r et w on e wd e v e l o p m e n t si nn e t w o r ke v o l u t i o n o n e i st h ed e a c t i v a t i o nm e c h a n i s m n o d e so fn e t w o r k sc a n n o ta l w a y sm a i n t a i n t h e1 i v i n gs t a t e ，f o ri n s t a n c e ，i nt h es c i e n t i s tc i t a t i o nn e t w o r k ，t h e r e s e a r c h1 i f ec y c l eo fs c i e n t i s ti sa l w a y sl i m i t e d t h eo t h e ri st h er a n k m e c h a n is m h o wd i dn e wn o d e s1i n ko l do n e sa c c o r d i n gt op r e f e r e n t i a l a t t a c h m e n tm e c h a n i s m ? t h ea b s o l u t ei m p o r t a n c e ( o rp o p u l a r i t y ) o fa no b j e c t i so f t e nd i f f i c u l to r i m p o s s i b l ef o rs t r a n g e r st om e a s u r ei ns o c i a l n e t w o r k s i n s t e a d ，i ti sq u i t ec o m m o nt oh a v eac l e a rk n o w l e d g ea b o u tt h e r e l a t i v ev a l u e so ft w oo b j e c t s t h e r e f o r e ，t h i sp a p e rt a k e si n t oa c c o u n t t h ea b o v et w om e c h a n i s m sa n ds t u d i e se v o l v i n gn e t w o r k sb a s e do na r a n k d e p e n d e n td e a c t i v a t i o n f i r s t ，i nc a s eo fu n w e i g h t e dn e t w o r k s ，w er a n ka l la c t i v en o d e s a c c o r d i n gt ot h e i ra g e s w ed e a c t i v eo n eo f a c t i v en o d e sa c c o r d i n gt ot h e i r r a n k sd u r i n ge v o l u t i o n t h er e s u l t i n gn e t w o r ks h o w ss e v e r a lg o o df e a t u r e s ( 1 ) w h e nae q u a l s0 ，t h ed e g r e ed i s t r i b u t i o ni sp o w e r l a w ，w h i l eae q u a l s n ，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 ( 2 ) t h ec l u s t e r i n g c o e f f i c i e n to ft h ep r e s e n tm o d e li sl a r g e rt h a no n e d i m e n s i o n a lr e g u l a r l a t t i c e s b e s i d e s ，t h el o c a lc l u s t e r i n gs c a l e sa sc ( 七) 一k f o rl a r g ek ( 3 ) t h ed e c a yo ft h e a v e r a g ed e g r e e o fn e a r e s t n e i g h b o r s ( k ) c h a r a c t e r i z e st h ed i s a s s o r t a t i v em i x i n gp a t t e r n ( 4 ) t h ea v e r a g es h o r t e s t p a t hl e n g t ha n dt h ed i a m e t e rg r o wl i n e a r l yw i t ht h en e t w o r ks i z e s e c o n d l y ，f o rw e i g h t e dn e t w o r k s ，w er a n kn o d e sa c c o r d i n gt ot h e i r s t r e n g t h e sa n dd e a c t i v eo n eo f a c t i v en o d e sa c c o r d i n gt ot h e i rr a n k s w h e n ae q u a l s0 ，t h ed e g r e ed i s t r i b u t i o na n ds t h r e n g t hd i s t r i b u t i o na r ea l l p o w e r l a w ，w h i l eae q u a l sn ，t h e yd i s p l a ye x p e n o n t i a l k e yw o r d s ：c o m p l e xn e t w o r k ，w e i g h t e dn e t w o r k ，r a n k ，d e a c t iv a t i o n v l i 1 1 研究背景及意义1 1 2 论文主要的研究内容以及论文安排3 第二章复杂网络研究概述 2 1 现实世界中的网络4 2 1 1 社会网络4 2 1 2 信息网络4 2 1 3 生物网络5 2 2 描述复杂网络结构的常用参量5 2 2 1 度分布6 2 2 2 聚类系数6 2 2 3 平均路径长度l 7 2 3 复杂网络模型简介7 2 3 1 三大经典网络模型7 2 3 1 1e r 随机网络7 2 3 1 2 小世界网络8 2 3 1 3 无标度网络1 0 2 3 2b b v 权重网络模型1 1 2 4 复杂网络研究的历史、现状及其发展1 3 2 4 1 复杂网络研究简史1 3 2 4 2 复杂网络研究现状1 4 2 4 3 复杂网络研究发展1 5 第三章基于序钝化的演化网络模型及其结构特征 3 1 复杂网络中有关钝化、排序的思想1 6 3 2 基于钝化机制的演化网络模型1 7 3 2 1 基于节点度老化的网络钝化模型17 v i i i 街人学坝i j 学位论义 3 2 2 基于节点权重老化的网络钝化模型1 8 3 2 3 基于序钝化的演化网络模型的构造1 9 3 3 基于序钝化的演化网络模型的结构特征2 0 3 3 1 度分布2 0 3 3 2 聚类系数2 5 3 3 3 最近邻平均度2 8 3 3 4 特征长度2 8 第四章基于序钝化的演化网络模型在权重网络下的推广 4 1 加权网络下基于序钝化的演化网络模型的推广3 1 4 2 相关结构特征3 l 4 2 1 度分布3 2 4 2 2 强度分布4 1 第五章总结和展望 5 1 总结4 4 5 2 展望4 5 参考文献4 6 作者在攻读硕士学位期间公开发表的论文4 8 致谢4 9 海人学顺i ：学位论义 1 1 研究背景及意义 第一章：引言 地球上任意两个人之间经过多少个朋友才能相互认识? 力| 维网( w w w ) 上从一 个页面到另一个页面平均需要点击多少次鼠标? 层出不穷的计算机病毒是如何在 互联网( i n t e r n e t ) 上传播的? 各种传染病( 艾滋病、非典型肺炎和禽流感等) 是如何在人类和动物中流行的? 为什么流言蜚语会散布得很快? 全球或地区性金 融危机是如何发生的? 局部故障是如何触发大面积停电事故的? 大城市的交通堵 塞问题是如何引起的? 的确很多现实生活中的些问题尽管看上去各不相同，但每 一个问题中都涉及很复杂的网络，包括w w w 、i n t e r n e t 、社会关系网络、经济网络、 电力网络、交通网络、神经网络等等。更为重要的是，越来越多的研究表明，这 些看上去各不相同的网络之间有着许多惊人的相似之处。现实世界中各类处于运 行状态的大规模复杂系统，其所处的外部环境均存在诸多无法确定的干扰因素， 而每一个体系自身又具有自组织调整、抗干扰的功能。无论是自然界还是人类社 会，不确定性是一个普遍存在的因素。所谓“天有不测风云 就是这个意思。这 种不确定性的存在，使人类的社会活动更富有挑战性，使人生更具有戏剧性色彩。 复杂网络自身因素及外部因素间的相互作用被繁乱的实际现象所遮掩，让人们一 时无法认清其本质面目。 长期以来，通信网络、电力网络、生物网络和社会网络等分别是通信科学、 电力科学、生命科学和社会学等不同学科的研究对象，而复杂网络理论所要研究 的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。从2 0 世纪末开始，复杂网络研究j 下渗透到数理学科、生命学科和工程学科等众多不同 的领域，对复杂网络的定量与定性特征的科学理解，已成为网络时代科学研究中 一个极其重要的挑战性课题 1 ，2 。 那么伴随着复杂网络理论的研究逐渐兴起，其主要研究手段是从真实系统结 构中抽象出基于点边结构的网络模型，并在其基础上进行解析及仿真分析，这样 就为研究大规模网络的特性开辟了一条可行的道路。著名学者w a t t s 和b a r a b a s i 等人分别在 n a t u r e 3 ，( ( s c i e n c e ) ) 4 上发表了揭示复杂网络重要特性 “小世界”及“无标度 两大特性的重要论文后，掀起了复杂网络的研究热潮。 因为他们的杰出工作奠定了复杂网络研究的基础，这以后针对各类真实网络的统 计性质的研究以及对网络功能与行为的研究逐渐成为包括数学、生物学、物理学 以及信息科学等学科的研究热点。经过科学家们多年的努力，在这一领域产生了 很多新的成果，对我们的现实生活产生了积极的影响。 沟人学顺i j 学位论文 但由于现实中的网络是由大量不同的个体组成的，且个体存在不同的相互作 用，因此研究现实中网络的结构又是一个很复杂的问题。一般而言，网络系统的 复杂性体现在以下几个方面 5 。 ( 1 ) 结构的复杂性：网络连接结构看上去错综复杂、极其混乱( 图1 ) 。而 且网络连接结构可能是随时间变化的，例如，w w w 上每天都不停地有页面和链接的 产生和删除。此外，节点之间的连接可能具有不同的权重或方向。例如，神经系 统中的突触有强有弱，可以是抑制的也可以是兴奋的。 图1 一个相互联系复杂的网络 ( 2 ) 节点复杂性：网络中的节点可能是具有分岔和混沌等复杂非线性行为的 动力系统。例如，基因网络和j o s e p h s o n 节阵列中每个节点都具有复杂的时间演化 行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中 细胞分裂的生化网络就包含各种各样的基质和酶。 ( 3 ) 各种复杂性因素的相互影响：实际的复杂网络会受到各种各样因素的影 响和作用。例如，耦合神经元重复地被同时激活，那么他们之间的连接就会加强， 这被认为是记忆和学习的基础。此外，各种网络之间也存在密切的联系，这使得 对复杂网络的分析变得更为困难。例如，电力网络的故障可能会导致i n t e r n e t 流 量变慢、金融机构关闭、运输系统失去控制等一系列不同网络之间的连锁反应。 2 0 世纪9 0 年代以来，以i n t e r n e t 为代表的信息技术的迅猛发展使人类社会大 步迈入了网络时代。从i n t e r n e t 到w w w ，从大型电力网络到全球交通网络，从生物 体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治、社会关系 2 ：海人学帧i ：学位论义 网络等，可以说，人们已经生活在一个充满着各种各样的复杂网络的世界中。人 类社会的网络化是一把“双刃剑”：它即给人类社会生产与生活带来了极大的便 利，提高了人类生产效率和生活质量，但也给人类社会生活带来了一定的负面冲 击，如传染病和计算机病毒的快速传播以及大面积的停电事故等。因此，人类社 会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。经 过十多年的发展，网络科学已经形成了很多具体的研究方向，其中很重要的一个 研究方向就是网络演化的机制与模型的构建。国内外许多学者在这方面的研究花 费了大量心血，他们的研究工作表明，合理的演化机制的设计对于网络模型真实 刻画现实世界具有重要作用。在这方面从最一开始的b a 模型中的偏好连接机制一 直发展到今天的钝化、排序等演化机制。从复杂网络的角度来研究系统的结构可 以使我们方便地从整体上了解系统的结构特性和演化机理。特别地，在生物、计 算机和疾病传播等许多学科的发展中，了解网络的拓扑结构已知多是一个很重要 的问题。目前，人们越来越广泛地认识和研究复杂网络，并且复杂网络的相关理 论已经对我们的生产和生活产生了指导意义。 1 2 论文主要的研究内容以及论文安排 本论文是以我攻读硕士学位期间承担课题的工作为基础，综合考虑了序的钝 化并研究他们对网络演化造成的影响。生成的网络所具有的统计性质与许多真实 系统中所观察的结果相一致。进一步对在权重网络进行了推广。 论文的内容将做如下安排： 第一章中主要介绍了研究背景、目的和意义，并提出本文的研究问题以及论 文安排。 第二章中首先介绍了我们现实生活中的网络世界；其次简单介绍了复杂网络 的一些常用结构参数；第三介绍了一些典型的复杂网络模型；第四回顾了复杂网 络研究的过程、现状和发展。 第三章中首先系统介绍了复杂网络演化机制方面的研究动态。主要包括了复 杂网络中有关偏好、钝化和排序的思想。然后介绍了几种基于钝化机制的演化网 络模型，进而介绍了基于序钝化的演化网络模型的构造。在此基础上我们分析了 本模型下的相关结构特征。主要从度分布、聚类系数、最近邻的平均度、网络的 最短路径长度和网络直径等角度来研究网络的结构。 第四章中将基于序钝化的演化网络模型推广至权重网络，并在此基础上讨论 了度分布及强度分布。 第五章中主要总结了整个研究过程中我的收获，以及对相关问题未来研究的 展望。 i ：j f 乎人学硕i ：学位论义 第二章复杂网络研究概述 2 1 现实世界中的网络 从古至今，其实人们都生活在网络的世界里，只不过随着人文、科技、经济 的发展，“网络 一词才慢慢被人们所察觉，网络给人们带来的变化是巨大而深 刻的。两千零三年八月十四日，美国纽约市中心突然发生大面积停电，整个纽约 顿时陷入黑暗之中。与纽约同时遭遇停电危机的还有地处美国东部的底特律、波 士顿和克利夫兰等几大城市，与这些城市同网的渥太华、多伦多也无法逃过一劫。 除了电网，我们还经常接触到公路网、通信网。两千零八年一月，我国南方遭受 大面积雪灾，导致铁路、公路严重受阻，通信网络一度失灵。可以说要想罗列现 实生活中的每一个网络，是一件很困难的事情，这里只就几种网络大致加以分类。 2 1 1 社会网络： 一个社会网络是由一群人以及他们之间的联系或相互关系所组成的【6 ，7 】。个 体之间的朋友关系，公司之间的商业联系，家庭之间的婚姻关系【8 】等等都是社 会网络的经典问题。从学术历史来说，社会学家是最早开始大规模研究现实世界 网络的学者 9 】。 传统的社会网络研究通常受制于诸如数据不精确、主观作用以及样本规模过 小的问题。绝大多数的数据来源于调查问卷或者访问，这种方法不仅消耗劳动力、 数据来源较少而且容易受到受访者主观偏见的影响。一种解决此问题的方法就是 合作网络，将相关研究数据制成一个数据库，需要随时调用。一个很好的例子就 是i m d 网。 2 1 2 信息网络： 经典的信息网络是在学术论文中的引用网络( 又称知识网络) 。大多数的文 章都会引用之前的相关文献，这些引用的关系形成了一个网络，其中节点是学术 论文，论文a 到论文b 的有向线段表示a 引用了b 。这样引用网络的结构反映 了一个节点的信息存储结构因此被称为“信息网络”【1 0 】。显然，引用网络是无 圈的，因为论文只有引用之前已经有的文献，然而之前的文献不可能引用之后的 论文。因此网络中的连线不可能违反时间规律，也就不可能形成圈了。作为一研 究领域，引用网络在数据丰富性、准确性方面很有优势。对于出版大量的研究要 追溯到1 9 2 6 年a l f r e dl o t k a 开创性的“学术成果定律”：单个学者发表作品的数 量服从幂律分布，也就晚个人撰写了k 篇论文的坐着数量按照一个常数k ， 4 海人学坝f j 学位论义 ( t 2 为常数) 衰减的。 另一个非常重要的信息网络是万维网，同时又含有信息的网页组成的，这些 网页是通过超链接联系起来的【1 1 】。与引用网络不同，万维网是可以含圈的，网 络中没有对于网页的次序进行排序，因此也就不会限制网络出现闭环的可能性。 自从1 9 9 0 年代首次出现以来，万维网已被深入地进行研究，其中的有影响力的 代表人物有：a l b e r te ta l 1 2 ；k l e i n b e r ge ta l e l 3 ；b r o d e re ta l 1 4 。 2 1 3 生物网络： 许多生物系统通常可以用网络来表示。也许最经典的生物网络例子就是新陈 代谢网络【1 6 】，它是由新城代谢过程中的反应物和生成物所组成的，如果一个新 陈代谢反应存在，并且知道其反应物和生成物，那么就可以用一个有向连接连接 他们。j e o n ge ta l 1 5 ；f e l lw a g n e rs t e l l i n ge ta l 1 6 在对新陈代谢网络的统计特征 研究中做出了巨大的贡献。另一个重要的生物网络是基因调控网络，它是由基因， 蛋白质以及有向线段来组成的，网络中的节点代表蛋白质，有向线段表示这个节 点对于其他节点蛋白质生成物的依存性。事实上，基因调控网络是最早的进行大 规模模拟实验的动态系统之一。 2 2 描述复杂网络结构的常用参量 对于任何理论来说，对于研究对象给出确切的定义显得十分重要。那么复杂 网络的定义是什么? 一般来说我们可以从以下两个角度来对它进行定义： ( 1 ) 图论角度的定义： 设有节点结合y = “，v 29 + - o ，) 和连线集合e = e l9 e 29 - + + 9 巳) ，通常由n 节点和 m 条连线来连接这些节点，连线可以是有方向的也可以是没有方向。大型网络可 以抽象的用一个图来表示，即：g = ( v ，d ，其中v ( g ) 表示该网络节点的集合， e ( g ) = ( “，v ) l u ，l ，矿( g ) ) 表示网络的边集合。 ( 2 ) 矩阵角度的定义： 常用与网络对应的图的邻接矩阵a 来表示：如果节点i 与节点j 存在着连线， 那么矩阵上相应位置上a 。我们用1 来表示，如果不存在连线我们用0 来表示，显 然一个无向图的邻接矩阵具有对称结构。 在研究网络结构的时候，所涉及的拓扑参最是指给定网络g = ( v ，e ) 的网络 海人孛坝i j 学位论义 结构之后，其针对某个节点或整个网络的统计特性。学者们一般来说比较关心的 是如下几种复杂网络统计量，他们在复杂网络的奠基性研究中起到了至关重要的 作用，并且对同后复杂网络研究的开展提供了重要的指引，下面作简要介绍： 2 2 1 度分布p ( k ) ( d e g r e ed i s t r i b u t i o n ) ： 度( d e g r e e ) 是单独节点的属性中简单而有重要的概念。节点i 的度墨定义为 与该节点连接的其他节点的数目。网络中随机选择的一个节点其度为k 的概率。 当网络所有的结点个数n 已知时，又记鼽为网络中度为k 的节点总数，则 p ( 七) ：盟，尸( 七) 可以用节点度的直方图来表示，这个直方图就是网络节点的度 分布。网络中所有节点i 的度忽的平均值称为称为网络的( 节点) 平均度，记为 ( 七) = 奄p ( 后) 。对于对分布的研究十分重要，因为它可以表征网络的许多拓扑结 k l 构。特别地，我们对于度分布呈幂律分布的情况尤为关注。 在物理上，度也往往被称为连通，这和图论中的定义是有所不同的。 2 2 2 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) ： 在社会网络中，人们经常会遇到这样的现象，你的两个朋友很可能彼此也是 朋友，这种属性称为网络的聚类特性 1 7 1 。聚类系数是反应网络的传递性或群集 性。从网络中的任一节点i 出发，我们考察i 的邻居的连接情况，记互为毛个邻 居间实际具有的边数，毛( 墨- 1 ) 为t 个邻居最多可能的边数，而两者之比就是节 点i 的聚类系数值： ) = 蒜 ( 2 2 2 1 ) 而整个网络的聚类系数c 为所有节点c ( f ) 的平均值，即c 2 寺；c ( f ) 。很明显， 0 c l 。从定义可知，当且仅当所有的节点均为孤立节点，即没有任何连接边 时，我们能得到c = 0 ；当且仅当所有的节点完全耦合，即网络是一个全连通网 络时，我们得到c = l 。从c ( f ) 的定义可以看出，他度量的是节点i 的邻居联系的 聚集程度。因此c 可以用来度量整个网络联系的聚集程度。 6 海人学形：学位论文 2 2 3 平均路径长度l ( a v e r a g ep a t hl e n g t h ) ： 网络中两个节点i 和j 之f b j i 驹b e 离以定义为连接这两个节点的最短路径上的 边数。网络中任意两个节点之间的距离的最大值称为网络的直径( d i a m e t e r ) ，记 为d 1 7 ，即d = m a x 办 ( 2 231 ) 沿用图论中的定义，网络中两个节点的距离定义为连接他们最短路径的边数。 整个网络的平均路径长度l 可以定义为网络中所有节点对的距离的算术平均值， 即 = r 二一吒 ( 2 232 ) 主( n + i ) 隆7 平均路径长度度量的是网络的连通性。众多学者一直都再思考对网络平均路径长 度的精确求解，虽未如愿但也有了不少有价值的发现，一个有趣的发现就是，即 便对于网络尺度很大的网络而言，平均路径长度依然相对较小，即便是对于那些 稀疏的网络而言也是如此。这从一个侧面反映出现实世界中的一个特性，即“小 世界效应 ，而“s m a l l w o r l d 模型寓意的来源也正是如此。 2 3 复杂网络仿真模型简介 2 3 1 三大经典网络模型 2 3 1 1e r 随机网络 图论最早起源于十八世纪瑞士人l e o n h a r de u l e r 灵j d x 尺度的高度规则图形的研 究。1 9 5 9 年，匈牙利数学家p a u le r d o s 和a l f i e c lr 吼y i 1 8 发现概率理论在图论的研 究中非常有用，并据此提出了随机图理论。他们首次将随机性概念引入到网络的 研究中来，提出了著名的随机网络模型，简称“e r 模型”。由于网络具有复杂的 结构和未知的组织原则，从而总表现出一定的随机性。因此在早期的工作中，随 机图模型往往被采用。此时，更多的从统计的角度研究图论及其算法。他们指出 可以用两种方法建立随机网络，介绍如下： e r 模型构造方法一：给定n 各节点( 网络中有n 个研究对象，即有n 个节点) ， 那么在这n 个节点之间总共可以存在掣条可能的连接，以概率p 去选择这些 z 连接，那么最后网络中会存在型掣条连接。 z e r 模型构造方法二：在随机图中，实际连接数是一个随机变量，其期望值为 e ( 刀) ：p n ( _ n - i ) 。从n 个节点中任意选择两点，若没有连接则连之，反之重新选 7 i ：海人学坝i j 学位论义 择两点，重复这一过程，直到m 条连接全部用完。则我们得到一个有n 个节点和m 条连接的随机图g ( n ，p ) 的概率为尸( ，p ) = p m ( 1 - p ) 州肛2 一。 通过1 9 6 0 年代e r d o s s n r e n y i 在一系列文献之中的阐述，随机网络的许多特性在 网络规模趋向于无穷时都能够得到解决。当n 很大时度分布函数p ( k ) 服从p o i s s o n 分布；若同时较p 小而大多数节点孤立就会使得网络直径d 很大。当p 逐渐增大 系统节点间联系增大，d 就较小。当p = 1 时网络中所有节点彼此邻近，d = l 。 一般来说，网络节点数n 必须取得足够大以使得z = p ( n 1 ) 是一个常数，在这 一情况下，该网络模型的度分布具有非常明显的泊松分布的形式。事实上，由于 网络中边的存在与否是独立的，因此一个节点含有度为k 的概率是： 7 k o - 2 级= 或p ( 1 - p ) ”气 k ! 最后一个约等式成立是由于二项分布在n 很大的情况下近似于泊松分布的结 果。 进一步的研究表明，在e r 随机网络中，任意节点的连接数目比平均度值高许 多或低许多的节点都极少，随着节点度值的增大，其概率呈指数形式迅速递减， 故随机网络又称为“指数网络 。随机网络的特征可概括为：( 1 ) 平均路径小， ( 2 ) p o i s s o n 度分布。 2 3 1 2 小世界网络( s m a l l - w o r l dn e t w o r k s ) 一个社会网络就是一群人或团体按某种关系连接在一起而构成的一个系统。 这里的关系可以是多种多样的。那么对于地球上的任意两个人而言，借助第三者、 第四者等这样的问接关系来建立起他们两个人的联系，平均需要通过多少人呢? 1 9 6 7 年，美国心里学家s t a n l e ym il g r a m 对社会网络结构进行了研究，设计出了著 名的“传信 实验 1 9 ：从美国k a n s a s 和n e b r a s k a 两座城市开始把一系列可跟踪 标记的信件，尽力传送到生活在b o s t o n 的某个目标人手中。传信方式是通过这些 人的朋友或熟人来传递信件，以期尽可能使信件传送到目标人手中。其途中每位 中间人交接时跟踪记录，最终测算出参与传送人数的统计结果。该实验表明：这 些信件从开始传送到最终到达目标人，平均经过了六次传递，重复了多次这样的 实验也总是得出相近的结果。m i l g r a m 称之为“小世界 ( s m a l l w o r l d ) 现象。 即对于大多数的网络，不管其尺寸有多大，任意两点间总有一条相对较短的路径。 形象的讲，经常出没于聚会场所，原本不相识的两个人聊着聊着会发现他们竟然 都和某一个人是朋友，然后一起发出“这个世界真小”的感叹。小世界的另一个 ：海人学顺i j 学位论文 代名词是所谓的“六度分离 。通过著名的“传信 实验s t a n l e ym i l g r a m 断言在 大多数情况下两个美国人之间一般存在一条不超过6 的“认识”路长( 即通过一个 人与另一个人之间互相认识来构成的路径，在任意两个美国人之间该路径长度一 般不超过6 ) 。 一般图论中的确定型图和完全随机网络不能表现真实网络的一些重要特征。 在现实生活中，大部分实际网络是基于确定型图和完全随机网络之问的。例如万 维网上的网页链接并不像随机图那样完全随机的连接在一起。j 下因为如此，1 9 9 8 年w a t t s 和s t r o g a t z 2 0 引入了一种介于确定型网络和随机网络之间的网络( w s 网络) ，它同时具有大的集群系数和小的平均距离。 w s 模型构造方法如下：从n 个节点的一维环开始，模型的每一个结点均与它最 近的k 个结点相连的规则网络。在此基础上随机化重连边，即顺时针选择节点和它 的最近邻的一条边，以概率p 随机重连网络中的每一条边，即将边的一个端点保 持不变，而另一个端点从网络中其他节点里随机选择，如果选择的节点已经与此 节点相连，则再随机选择别的顶点来重连。并且规定，不能够出现重边和自环的 情况，考虑所有的节点直到一圈结束。接着考虑节点与它的次近邻节点之间的边， 规则如前，以几率p 随机重连这些边，然后继续这一过程，在每一圈结束后都向 a r 五， 外考虑更远一些的邻居，直到原来点阵中的每一条边都被考虑过了。整个图有竿 z 矿 条边，所以重连过程将在绕这个环会圈后结束。 2 显然在p = 0 的情况下，该模型即为原先的规则网络；而在p = 1 时即为上面的 e r 随机网络；当0 p ( k ) 时，度为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 以及新陈 代谢网络等的连接度分布函数都是具有幂律形式的。由于这类网络的节点的连接 没有明显的特征长度，故称为无标度网络 2 3 。 在网络演化机制的设计方面，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 t r i c h e r ) 或叫“马太效应( m a t t h e we f f e c t ) 一例如，新发表的文章更倾向于 引用一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向 知名网站。 b a 模型的构造方法如下： ( 1 ) 初始阶段：初始节点数量为的全连通网络。 ( 2 ) 增长阶段：在每一个时间点上，增加一新节点，并且使其与m 个旧节点 相连。 ( 3 ) 偏好连接( p r e f e r e n t i a la t t a c h m e n t ) ：新节点n 与旧节点i 相连的概率 l o 海人学硕i ：学位论文 为兀删2 轰，这晕分母是为了满足概率的归谁。 显然，在时间点t 时，网络中有n = m o + f 各节点和m f 条连线。令见。是网络 中有n 个节点时的p k ，爿1 5 么每一连续时i 刚点上n p t 的增量刚以表述如卜： ( 刀+ 1 ) p + 。一= j 1 ( 七一1 ) 。一互1 ( 七 所) ( 肘1 ) p k 卅i 一印如= 1 一互1 唧m ( 尼= m ) 为了得到稳定解，我们必须考虑这一情形：见川= 见，。= 见，这样一来，我 们可以将上式整理为： 见= 圭( 七一1 ) 见一。一j 1 印。 ( 七 所) 见= l i 1 慨 ( 七= 埘) 因此，可以得到度分布为：见2 话型磊莩蔬2 石干2 m 丽( m + 1 ) 显然度分布为p o ck - 3 ，即b a 模型度分布满足指数为3 的幂律分布。 2 3 2 b b v 网络演化模型 2 4 在b b v 网络模型之前，人们对很多现实网络，如生物网络、互联网、万维 网等的刻画与理解只是停留在对网络拓扑结构的研究，而未能考虑那些可以更 加真实刻画网络的因素节点之间相互作用的强度( 边的权重) 。那么这些 模型一般都呈现出复杂的拓扑结构性质，如小世界性质和无标度行为。而我们 知道在生态网络 2 5 ，2 6 中捕食者与被捕食者之间的相互作用是有差异的，代谢 网络中的代谢反应 2 7 之间也是有不同的，社会网络中人与人之间的联系程度 与重要性也是有变化、有差异的。类似的，诸如网络通信量、航空网络运输量 都是这类网络研究中很关键的数量。有趣的是相关的研究 2 7 ，2 8 3 0 已经证实 权重网络显示出额外的复杂特性，如广度分布、权重的非平凡相关性等，这些 属性是无法仅仅用拓扑结构来加以解释的。2 0 0 4 年m a i nb a r r a t ，m a r c b a r t h e l e m y 和a l e s s a n d r ov e s p i g n a n i 三人出于现实网络的考虑提出了一个基 于权重网络下的演化模型，即b b v 模型。 通常权重网络可以由一个权重矩阵来刻画，它表示节点i 与j 之问连边 ：海人学顾i ：学位论义 的权重，i 与j 取值为1 到n ，n 为网络的尺度。若= 0 则表示节点i 与j 之 间无连接，若网络为对称网络则有= 。此外节点的强度定义为= ， 其中j 矿( f ) 表示节点i 的所有最近邻。 b b v 模型的具体构造如下： ( 1 ) 初始节点数为0 的全连通网络，边权为w o 。 ( 2 ) 每个时间步长上新节点n 按照连接概率兀。，= 毒 与先前已经存在 l s | 的m 个节点相连。新边的权重为w o 。 ( 3 ) 每条新边的产生将会引起权重增量万，此权重增量万将按公式 嘞专嘞+ 嘞被分配到节点i 与其最近邻j 之间的边勺上，其中= 万詈。 如图2 所示。其实对这条规则还有不同的理解，例如p a n d y a 3 1 将其加以修改 丸嘞专嘞w 轰。 l + w 矿6 lu 图2 新边n i 所引起的权重增量万将在节点i 的出边中按规则嘞一嘞+ ，其中 w u = w _ 口或规则嘞一+ 万豪进行分配。而节点i 的