（计算机应用技术专业论文）因特网拓扑结构复杂性研究.pdf

硕士学位论文 m a s t e r st h e s l s 中文摘要 复杂网络的研究正方兴未艾，特别是小世赛网络( s i i l a l l w o r l d ) 和无标度 ( s c a l e f r e e ) b a 网络模型的提出，引发了复杂网络研究的热潮。小世界网络既具 有与规则网络类似的聚类特性，又具有与随机网络类似的较小的平均路径长度。 而无标度网络的连接度分布具有幂律形式且幂律分布没有明显的特征长度，并具有 在真实复杂网络中观察到的“富者愈富”的演化特征。人们相继研究了各种现实世 界中复杂网络的统计特征，如人际关系网络、经济网络、航空网络和科学家合作网 络等等。统计性质显示这些网络都具有小世界和无标度网络的特征。 因特网作为现实世界中重要的复杂网络之一，一直是研究的热点，特别是对因 特网拓扑结构的复杂性研究，先后获得了许多因特网拓扑结构的统计性质。并在研 究的基础上提出了一些相应的因特网拓扑结构模型。对理解因特网的动力学行为和 有效的利用和管理因特网提供了科学的基础。 本文首先介绍了复杂网络研究提出的主要模型小世界和无标度模型及其统计 性质，然后介绍了因特网拓扑结构复杂性研究的一些重要结果。接着，基于对因特 网路由器级拓扑演化特征的观察，提出了基于路由器级因特网拓扑结构的一个简单 的加权网络模型一一加权局域世界网络演化模型，分析了模型演化网络的度、强度 和权重的概率分布特征，结果显示，该模型演化网络的节点度、强度和权重具有从 指数到幂函数律分布过渡的非平凡网络演化特征。通过网络仿真，数据模拟验证了 分析结果。最后与因特网的簇系数和相关性等统计特性进行了比较，证实了因特网 拓扑生长过程中局部演化的特征。为进一步研究精确的加权因特网路由器级拓扑结 构模型奠定了基础。 关键词：复杂网络，因特网拓扑结构，小世界，无标度，路由器级 硕士学住论文 m a s t e r st h e s i s a b s t r a c t 1 1 l er e s e a r c ho nc o m p l e xn e t w o r k si n c r e a s e l y d e v e l o p sr e c e n t l y e s p e c i a l l ya f t e r p r o p o s e dt h em o d e l j n go fs m a l l w o r l da i l ds c a l e 一打e en e t w o r k s ，m o r ea l l dm o r cr e s e a r c h s f o c u so nt h ec o m p l e xn e t w o r k s t h es m a l l - w o r l dn e 咐o r k sh a v en o to l l l yi h es a m eh j 曲 c l u s t e f i n gc o e f f i c i e n ta st h en o i l a ln e 咐o r k s ，b u ta l s ot h es a m es m a l la v e r a g ep a t h l e n g t l la st h er 孤d o mn e 似o r k s 。t h ed e 掣e ed i s t r j b u t i o no fs c a l e 一丘e en e t w o r k sp r e s e n t s t h ep o w e r l a wa n dh a sn o t t h ep a n i c u l a rs c a l ec h a r a c t e r i s t i c m e a n w h i l c ，“a l s oc a n e x p l a i t h e “r j c hg e t sr i c h e r ”p h e n o m e n o no b s e e di nm a t l yr e a l l i f ec o m p l e xn e 时o f l 【s t h es t a t i s t i cc h a r a c t e r i s t i c so fm a n yr e a l l i f ec o m p l e xn e t w o r k sa i r e a d yd i s c u s s e d ， e c o n o m yn e t w o r k s ，w o r l d - w i d ea i r p o f tn e 抑o r k sa n ds d e n t i f i c l l a b o f a t i o nn e 觚o r k s a n ds oo n t h es t a t i s t i cc h a m c t e r i s t i c si n d j c a t et h a tm e s er e a l l i f en e t w o r k sh a v eb o t h s m a 儿w o r l da n ds c a l e f r e ef 色a t u r e s i n t e m e tt h ei m p o n a n tr c a l l j f cc o m p l e xn e 咐o r k si st h eh o tt 叩i ci nr e s e a r c ho f c o m p l c xn t w o r k s ，e s p c c i a l l yr e s e a r c ho nc o m p l e xo fk t e m e tt 0 1 ) 0 l o g y t h e 砖a r em a n y s t a t i s t i cc h a r a c t e r i s t i c sa n dm o d e l sw e l l i n gu pi nt h i sa r e a ，w h i c hp r 0 v i d et h es c i e n t i f i c b a s e so fu s j n ga i l dm a n a g i i l gm ei n t e m e t i nt h i sp a p e r ，f j r s t ，w ej n t r o d u c et h em a i nm o d e l sa i l dt 王1 0 s eo fs t a t i s t i cc h a r a c t e r i s t i c s o fc o m p l e xn e t w o r k si n c l u d i n gs m 宙1w o d dn e t w o r k sa n ds c a l ef r e en e t w o r k s s e c o n d ， w ei n t r o d u c et h em a j nr e s u l t so fr e s e a r c h so fi n t e m e tt o p o l o g y t h e nf o rm o s tn e “v o r k s i l l e n g i n e e r i i l ga n dt e c h n o l o g y t l l ei n t e r p l a yo fs y s t e md y n 珊i c s ，d a t at m f f i c s a d n e t w o r kt o p o l o g yi sc r i t i c a lt ot l l en e “v o r ke v o l u t i o na n dp e r f b 皿1 a n c ee v a l u a t i o n an e w m o d e li sp r o p o s e df o rd e s c r m i n gt h e 鲈o w t ho fl o c a l 一w o r l dw e i g h t e dc o m p l e xn e t w o i k s n j sm o d e lc o m b i n e st b en e wv e r t j c e sa n dn e we d g e sw j t ht h ed y n a m j c a je v o l u t i o no f t h ew e i g h t s1 0 c a l ly ，t h e r e b yg e n e r a t i n gag r o w i n gn e t w o r kw j t hm a n ys t a t i s t i c a l p r o p e r t i e so b s e e df r o mr e a l - w o r l dn e t w o r ke x a m p l e s i np a n i c u l a r ，t h em o d e ly i e l d s n o n t t j v i a l t j m ee v o l u t i o no fv a r i o u sv e r t e xp r o p e 币e s ，i n d u d i n gs u c ha se x p o n e n t i a la n d s c a l e - f r e ed i s t r j b u t i o n so fw e i g h t s ，s t r e n g t h sa n dd e g r e e s f i n a l l y ，w ec o m p a r et h e c i u s t e r i n gc o e f ! f i c i e n ta i l dc o r r e l a t i o no fr o u t e rl e v e l i n t e m e tt o p o l o g yw i t ht h o s eo fo u r m o d e lr e s u l t i n gi n v a l i d a t i n gt h e1 0 c a le v o i v i n gf e a t u r ei n t h ep r o c e s so fi n t e m e t t o p 0 i o g ，r 伊0 w j n 吕 k e yw o r d s ： c 0 m p l e xn e 似o r k s ，i n t e m e tt o p o l o g y ，s m a l l - w o r i d ，s c a l e - 行e e ， r o u t e rl e v e l 硕士学住论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名 喜；同1 日期：加矸年f 月吾日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名： 私 日期：2 硎年6 月 导师签名 q 扩叩v 叭 3 日 日期：刎年占月子日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回丞迨塞埕交后进压；旦坐生；旦二生；旦三生筮壶! 作者签名： 彭；l 研1 日期：加6 年月髫日 糊签名：轴 日期：厕年彳月g 日 硕士学住论文 m a s t e r st h e s l s 自然界和人类社会中中存在的大量复杂系统都可以通过各式各样的网络加 以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的， 其中节点用来代表真实系统中不同的个体，而边则用来表示个体之间的关系， 通常是当两个节点之间具有某种特定的关系时连一条边，反之则不连边。有边 相连的两个节点在网络中被看作是相邻的。例如，计算机网络可以看作是自主 工作的计算机通过通信介质如光缆、双绞线、同轴电缆、无线信道等相互连接 形成的网络。类似的还有电力网络、社会关系网络、交通网络、因特网等等。 通常把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做 网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构 比较适用于描述真实的系统呢? 这个问题的研究经历了三个阶段。开始时，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它 看起来像是格子体恤衫上的花纹，又如最近邻环网，它总是会让你想到一群手 牵着手、围着篝火跳圆圈舞的姑娘。到了2 0 世纪5 0 年代末，数学家们想出了 一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定 的事情，而是根据一个概率决定。这样生成的网络叫做随机网络，它在接下来 的4 0 年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几 年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网 络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的 网络。这样的一些网络被科学家们叫做复杂网络( c o m p l e xn e m o r k s ) ，对于它 们的研究标志着第三阶段的到来。遗憾的是，就目前而言，复杂网络还没有精 确严格的定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以 下几层意思：首先，它是大量真实复杂系统的拓扑抽象。其次，它至少在感觉 上比规则网络和随机网络复杂，因为我们可以很容易地生成规则和随机网络， 但就目前而言，还没有一种简单方法能够生成完全符合真实统计特征的复杂网 络。最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研 究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。 硕士学住论文 m a s t e r st h e s i s 1 9 9 8 年，w a t t s 和s t r o g a t z 通过以某个很小的概率p 切断规则网络中原始 的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络 之间的网络( w s 网络) ( 见文献 1 ) ，它同时具有大的簇系数和小的平均距离， 因此既不能当作规则网络处理，也不能被看作是随机网络。随后，n e w m a n 和 w a t l s 给出了一种新的网络的构造方法( 见文献 2 ) ，在他们的网络( n w 网 络) 中，原有的连边并不会被破坏，平均距离的缩短源于以一个很小的概率在 原来的规则网络上添加新的连边。1 9 9 9 年，b 锄m s i 和b e n 给出了构造无标 度网络的演化模型( 见文献 3 ) ，b a m m s i 和b e n 把真实系统通过自组织生 成无标度的网络归功于两个主要因素：生长和优先连接，而他们的网络模型( b a 网络) 正是模拟这两个关键机制设计的。 随机网络 在过去4 0 多年里，科学家惯于将所有复杂网络看作是随机网络。这一思想 源于两位匈牙利数学家的研究，他们是卓越的e r d o s 以及他的密切合作者r e n y i 。 1 9 5 9 年，为了描述通信和生命科学中的网络，e r d o s 和r e n y i 提出，通过在网 络节点间随机地布置连结，就可以有效地模拟出这类系统。这种方法及相关定 理的简明扼要，导致了图论的复兴，数学界也因此出现了研究随机网络的新领 域。 随机网络理论有一项重要预测：尽管连结是随机安置的，但由此形成的网 络却是高度均匀的，也就是说，绝大部分节点的连结数目会大致相同。实际上， 随机网络中节点的分布方式将遵循钟形的泊松分布。连接数目比平均数高许多 或低许多的节点，都十分罕见。有时随机网络也称作指数网络，因为一个节点 连接女个其他节点的概率，会随着t 值的增大而呈指数递减。 小世界网络 1 9 6 7 年，美国哈佛大学的社会心理学家m i l 舯m 寄出了数百封信给内布拉斯 加州的公众，并请求他们把信转交给某位相识的人，条件是对方必须是最有可能 把信再转给波士顿一位股票经纪人手里的人。为了跟踪每一条不同的传送路径， m i l g r a m 请求参与者在转寄信件的同时，也给他寄一张明信片。结果，m i l 铲a m 发 现，信件到达最终收信人之前平均要经过6 个人之手。人与人之间存在所谓“六 度分离”的说法就来源于这个实验。 硕士学位论文 m a s t e r s t h e s i s 虽然m i l 掣a m 的结果很难说是定论，因为绝大部分的信件并未到达最终收信 人手里。不过科学家最近发现，其他网络也具有这种“小世界”的特性。例如， 细胞内的任意两种化学物质，几乎都能通过三个化学反应组成的路径连结起来。 在万维网上，虽然页面数高达3 0 亿，但一般只要经过1 9 个连结，就可以从一个网 页到达另一个。 “六度分离”在学术上称为“小世界现象”或“小世界效应”。小世界效 应的精确定义还在讨论中，目前一个较合理的解释是：若网络中两点间的平均 距离随网络大小( 网络中节点数呈对数增长，即l l n ，当网络中节点数 增加很快时，变化相对缓慢，则称该网络具有小世界效应。这里的平均距离 具有广泛的含义，例如在前面提到信件传递实验中，平均距离就是平均传递次 数6 。当然还有一些网络呈现出不同的值。美国的科学家们把好莱坞所有老 的电影演员拿来做实验，比如说一个演员是一个节点，两个演员他们合作在同 一部电影演出，那么，通过所有演员分析表明，两个演员之间的平均距离介乎 于3 至4 之间。以因特网上的信息链接为例，因特网的信息量在1 9 9 9 年统计 大概是1 0 亿的数量级。美国一些物理学家就设计了一种软件，通过这个软件对 因特网做数据采集分析发现，因特网中的平均距离是1 9 个链接。也就是说， 你在因特网上随机任意取两点，不断地点这上面的超级链接，按1 9 次鼠标就能 到达另一点，这就是因特网小世界特征。再从因特网的路由连接来看，因特 网路由器的数量已经是数以几千万计，但是平均两个路由器之间的距离也就是 l o 左右。为什么不同的网络有不同的平均路径? 这就是关于网络小世界的特 征揭示问题。在这里笔者强调的并不是这些网络节点平均距离是6 、3 、1 9 或 者1 0 的差异，而是在不同类型的实际网络中，它们所表现出来的一种惊人的 相似特性。事实上，不管是人类网络还是因特网，网络当中的数量是以1 0 亿来 计，对于一个有几十亿节点的网络来说，这些差异是微不足道的，重要的是分 析不同的网络之间为什么存在共同小世界的特性。 无标度网络 大脑，是由轴突相连结的神经细胞网络，而细胞本身，又是由生化反应相 连结的分子网络。社会也是一个网络，它由友情、家庭和职业关系彼此连结。 在更大的尺度上，食物链和生态系统可以看作由物种所构成的网络。科技领域 的网络更是随处可见：因特网、电力网和运输系统都是实例。就连在文章中也 硕士学位论文 m a s t e r st h e s l s 是用以向读者传递思想的语言，也是一种藉由语法相互串连在一起的文字网络。 尽管网络是如此重要和普遍，但科学家对它的结构和属性却知之不多。在 复杂的基因网络中，故障节点是如何相互作用而引发癌症的? 在特定的社会和 通信系统中，疾病和电脑病毒如何快速传播而导致流行? 某些网络即便大部分 节点失效，还能维持运行，原因何在? 最近的研究开始找到这些问题的答案。过去的几年中，不同领域的研究者 发现，很多网络都是由少数一些具有众多连结的节点所支配的，包括万维网、 细胞代谢系统，以及好莱坞的演员网络在内。包含这种重要节点( 或称集散节 点) 的网络，我们通常称之为”无标度”( s c a l e f r e e ) 网络。表l 是一些无标度 网络的典型例子。 事实上。科学家研究的网络越多，发现的无标度结构也越多。这些发现引 发了一个重要的问题：为什么像细胞和因特网这样本质上不同的系统，却具有 相同的结构并遵从相同的规律? 这些不同的网络不仅都是无标度的，而且还有 着一个有趣的共同点：由于某些未知的原因，幂次定律中旷项中的n 值，通常 介于2 3 之间。 在无标度网络中，有些集散节点甚至具有数不清的连结，而且不存在代表 性的节点。这种网络还具有可预期的行为特性：例如对意外故障具有惊人的承 受力，但面对协同式攻击时则很脆弱。 这些发现极大地改变了我们对复杂外部世界的认识。集散节点的存在，让 我们认识到了以前的网络理论尚未涉及的问题：各种复杂系统具有相同的严格 结构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、 语言和社会。更进一步，认识这些法则，会帮助我们解决一系列重要问题，包 括开发更好的药物、防止黑客侵人互联网、阻止致命流行病的传播，等等。 很多复杂系统拥有共同的重要特性： 网络中的节点不断的生长或者死去。如1 9 9 0 年整个万维网只有一个网页， 而到今天它的网页数已经超过了3 0 亿。大约3 0 年前，整个因特网只有几个路 由器，随着新的路由器与网络原有的路由器相连结，如今路由器的数量已经高 达百万。在新的节点加入时，老节点获得连结的机会也比较高。而且并非所有 的节点都是平等的。 大部分节点只有少数几个连结，而某些节点却拥有与其他节点的大量连结。 4 勰。 这些具有大量连结的节点称为“集散节点”，所拥有的连结可能高达数百、数 干甚至数百万。这一现象称为集散节点的“马太效应”或者“富者愈富”。由此 看来，这一特性似乎能说明网络是无标度的。无标度网络具有某些重要特性。 例如它们都可以承受意外的故障，但面对蓄意攻击却很脆弱。了解这些特性， 可能导致许多领域出现新的应用。例如，电脑科学家可能据此设计出更有效的 策略，以保护因特网免受电脑病毒的侵害。 表l 无标度网络的例子( 见文献 4 ) 网络节点连接 组织代谢参与消化食物以释放能量的分子参与相同的生化反应 好莱坞演员出演同一部电影 因特网路由器光纤及其它物理连接 蛋白质调控网络协助调控细胞活动的蛋白质蛋白质之间的相互作用 研究合作科学家合作撰写论文 航空机场航线 万维网网页 连接地址 因特网拓扑结构 因特网从它诞生的那一天起，其规模就不断的增长，特别是现在，更是以 指数速度高速增长。当今因特网的“面貌”已经远离其原型a r p a n e t ，依其 高度的复杂性，可以将其看作一个由计算机、路由器和物理链路构成的“生态 系统”。虽然因特网是在人类的需求的基础上逐渐发展起来的，但却没有人能 够说清楚这个庞然大物看上去到底是个什么样子，运转得如何。因特网的复杂 性决定了其拓扑结构的复杂性，而因特网拓扑复杂性研究及其建模就是试图从 这个复杂纷纭的网络世界中，探求其中蕴含着哪些还不为我们所知的规律。如 路由器级的因特网拓扑结构，自治域级的因特网拓扑结构，万维网的拓扑结构 等等，对他们的研究都将使我们更好的利用和发展因特网。发现因特网拓扑的 内在机制是认识因特网的必然过程，是在更高层次上开发利用因特网的基础。 然而，因特网与生俱来的异构性、动态性、分布性和发展的非集中性以及如今 庞大的规模都给因特网复杂性研究和拓扑建模带来巨大挑战。 现实世界中许许多多的复杂网络都是具有小世界或无标度特征的复杂网 络：从生物体中的大脑结构到各种新陈代谢网络、从因特网到w w w ( w o r l d w i d e 硕士学位论文 m a s t b r st h e s i s w c b ) 、从大型电力网络到全球交通网络、从科研合作网络到各种政治、经济、 社会关系网络等等，数不胜数。各种网络的研究目前在世界上受到了高度的重 视，形成了日益高涨的热潮，已成为一个极其重要而且富有挑战性的前沿科研 方向。 论文的主要贡献与内容安排 本文的主要目标是基于路由器级因特网拓扑结构的演化统计特征，提出一 种简单的加权局域世界网络演化模型。本文运用连续场理论对该模型的概率分 布特征进行了解析，通过网络数值仿真对解析结果进行了验证，并与路由器级 因特网拓扑结构的统计特征进行了比较。在已有的加权网络模型和局域世界网 络模型的基础上，我们拟进行以下工作： 1 。结合加权网络模型和局域世界网络模型，基于加权的路由器级因特网拓 扑结构及其统计特征，提出一种简单的加权局域世界网络演化模型。 2 运用连续场理论对该模型的度、强度和权重分布概率和演化进行解析证 明，并给出相应的表达式。 3 通过仿真来进行网络模拟，对分析结果给予验证。并对模型和因特网路 由器级拓扑结构的簇系数和相关性的统计结果进行比较分析。 论文随后各章的内容安排如下： 第一章介绍论文所涉及到的内容的相关的网络拓扑理论知识，主要是网络 拓扑基本理论和基本的网络模型的静态特性。主要介绍了规则网络、随机网络、 小世界网络和无标度网络。 第二章则介绍了因特网拓扑结构的复杂性研究，主要是对因特网拓扑结构， 特别是自治域级拓扑结构的数据统计研究结果，幂律特征和各种度量。及在此 基础上提出的拓扑模型和拓扑生产算法。 第三章首先介绍了加权局域世界网络模型提出的背景和相关的工作。其次 详细介绍了该模型的算法，然后运用连续场理论对网络的度、强度和权重的概 率分布和演化的解析分析，最后对模型和因特网路由器级拓扑结构的簇系数和 相关性的统计结果进行了比较分析。 第四章总结全文，讨论本文所提出的加权局域世界网络演化模型的优点和 局限性，并指出今后的研究方向。 顶士学位论文 m a s t e r st h e s i s 第一章网络拓扑基本模型及其性质 要理解网络结构与网络行为之间的关系并进而考虑改善网络的行为，就需 要对实际网络的拓扑结构特征有很好的了解并在此基础上建立合适的网络拓扑 结构模型。在w a t t s 和s t r o g a t a z 关于小世界网络以及b a r a b d s i 关于无标度网络 的开创性工作之后( 见文献【1 ，3 】) ，人们对来自不同领域的大量实际网络的拓 扑特征进行了广泛的实证性研究。在此基础上，人们从不同的角度出发提出了 各种各样的网络拓扑结构模型( 见文献【5 6 】) 。本章介绍几类基本的模型【7 ， 包括规则网络、随机图、小世界网络、无标度网络等等。 1 1 规则网络 规则网络是人们最先对复杂系统拓扑结构的认识。我们首先来看三种规则 网络。全局耦合网络( g l o b a l l yc o u p l e dn e t w o r k ) ，它的任意两个点之间都有边 直接相连( 图1 f a l ) 。因此，在具有相同节点数的所有的网络中，全局耦合网络 具有最小的平均路径长度三，= 1 和最大的聚类系数c 矗= 1 。虽然全局耦合网络 模型反映了许多实际网络具有的聚类和小世界性质，但该模型作为实际网络模 型的局限性也很明显的：一个有个点的全局耦合网络有一1 妣条边，然 而大多数大型实际网络都是很稀疏的，他们的边的数目一般至多是d ( 聊而不是 0 ( 2 ) 。 固 心谚 叼 隆 、 【b 】 【c l 图l 几种规则网络( a ) 全局耦合网络，( b ) 最近邻耦合网络，( c ) 星形网络 硕士学位论文 m s t e r st h e s l s 最近邻耦合网络( n e a r e s t - n e i 曲b o rc o u p l e dn e t w o r k ) 是一个得到大量研究 的稀疏的规则网络模型，其中每一个节点只和它周围的邻居节点相连。具有周 期边界条件的最近邻居耦合网络包含个围成一个环的点，其中每个节点都与 它左右个剧2 个邻居点相连，k 是个一个偶数( 图1 ( b ) ) 。对较大的世值，该网 络的平均路径长度为 c 扩黼一； 因此，这样的网络是高度聚类的。然而，最近邻耦合网络不是一个小世界，相 反，对固定的值，该网络的平均路径长度为 。一。寿一m ( 一* ) 这可以从一个侧面帮助解释为什么在这样的一个局部耦合的网络中很难实现需 要全局协调的动态过程( 如同步化过程) 。 星形耦合网络( s t a rc 0 u 口l e dn e t w o r k ) 是另外一个常见的规则网络，它有 一个中心点，其余的一1 个节点都只与这个中心点连接，而它们彼此之间不 连接( 图1 ( c ) ) 。星形网络的平均路径长度为 k - 2 - 耥一2 ( 叫 星形网络的聚类系数为 ，= 等一1 ( 叫 在计算星形网络的聚类系数时，中心节点的聚类系数为零，而其它每一个节点 的聚类系数为1 。这里假设如果一个节点只有一个邻居节点，那么该节点的聚 类系数定义为l 。有些研究文献中则定义只有一个邻居节点的节点的聚类系数 为o ，依此定义的话，星形网络的聚类系数为0 。 1 2 随机图 在发现规则网络并不能很好的解释复杂系统中的网络拓扑之后，与完全规 则网络相反的时完全随机网络得到了研究，一个典型的模型是e r d 6 s 和r e n y i 于4 0 多年前开始研究的e r 随机模型( 见文献 7 ) 。 硕士学位论文 m a s t e r st h e s i s o o o o o o o o o i a 】p = 0 l b lp = 0 1 【c lp = 0 1 5 【d lp = 0 2 s 图2 随机图的演化示意图( a ) 给定的1 0 个孤立点，( b ) ( d ) 分别以连接概率，= 0 1 ， p = 0 1 5 和p = 0 2 5 生成的随机图 假设有大量的纽扣( 1 ) 散落在地上，以相同的概率p 给每对纽扣系 上一根线。这样就会得到一个有 ，个点，约删一1 ) 2 条边的e r 随机图的实 例( 图2 ) 。 随机图理论的一个主要研究课题是： 当概率卢为多大时，随机图会产生一些特殊的属性? e r d f s 和r 6 n v i 系统地研究了当 ，一o o 时e r 随机图地性质( 如连通性等) 与概率p 之间地关系。他们采用了如下定义： 如果当一。o 时产生具有性质q 地e r 随机图地概率为1 ，那么就称几 乎每一个e r 随机图都具有性质q 。 e r d 6 s 和r 6 n y i 的最重要的发现是e r 随机图具有如下的涌现或相变性质： e r 随机图的许多重要的性质都是突然涌现的。也就是说，对于任一给定的 概率p ，要么几乎每图都具有某个性质q ( 比如说，连通性) ，要么几乎每一 个图都不具有该性质。 例如对于上述纽扣网络，如果你捡起一个纽扣，那么将有多少个纽扣也会 被跟着拎起来昵? 结果显示，如果概率p 大于某个临界值p 。一( 1 n v ) ，那么几 乎每一个随机图都是连通的，也就是说，你随机地捡起一个纽扣都会拎起地上 9 硕士学位论文 m a s t e r st h e s l s 几乎所有地纽扣。 e r 随机图的平均度是 1 ) 。当p 较小时( o p 1 ) ，重新连线后得到的网络与原始的规则网络的局部属性差 别不大，从而网络的聚类系数变化也不大( c p ) 一c ( 0 ) ) ，但其平均路径长度却 下降的很快( 0 ) 上( 0 ) ) ( 图4 ) 。这类既具有较短的平均路径长度又具有较 高的聚类系数的网络就称为小世界网络。 w s 小世界模型构造算法中的随机化过程有可能会破坏网络的连通性。另 一个研究较多的小世界模型是由n e w m a i l 和、v a t t s 稍后提出的( 见文献 2 ) ， 我们称为n w 小世界模型。该模型是通过用“随机化加边”取代w s 小世界模 型构造中的“随机化重连”而得到的( 图3 ( b ) ) 。具体的构造算法如下： 1 ) 从规则图开始：考虑一个含有个点的最近邻耦合网络，它们围成一 个环，其中每个节点都与它左右相邻的个 汜节点相连，k 是偶数。 2 ) 随机化加边：以概率p 在随机选取的一对节点之问加上一条边。其中， 硕士学位论文 m a s t e r st h e s i s 任意两个不同的节点之间至多只能由一条边并且一个节点不能有边与自身相 连。 o 国 oo ( 6 ) ( b ) 图3 小世界网络模型( a ) w s 小世界模型，( b ) n w 小世界模型 图4w s 小世界模型的聚类系数c p ) 和平均路径长度上0 ) 随重连概率p 的变化 关系( 注：这里对两个值做了归一化处理) 在n w 小世界模型中，p = o 对应于原来的最近邻耦合网络，p = 1 则对应 于全局耦合网络。在理论分析上，n w 小世界模型要比w s 小世界模型简单一 点。当口足够小足够大时，n w 小世界模型本质上等同于w s 小世界模型。 小世界模型反映了朋友关系网络的一种特性，即大部分人的朋友都是和他们住 在同一条街上的邻居或在同一个单位工作的同事。另一方面，有些人也有一些 住得较远的，甚至是远在异国他乡的朋友，这就是在w s 小世界模型中通过重 新连线或在n w 小世界模型中通过加入连线产生的远程连接。 硕士学位论文 m a s t e r st h e s i s 1 3 。2 小世界网络模型的统计性质 聚类系数 w s 小世界网络的聚类系数为( 见文献 8 ) = 黼”p ) 3 n w 小世界网络的聚类系数为( 见文献 9 ) c ”硒 平均路径长度 迄今为止，人们还没有关于w s 小世界模型的平均路径长度工的精确解析 表达式。利用重正化群方法可以得到( 见文献 2 ) ( p ) 孕，( 脚2 ) 其中，也) 为一普适标度函数且满足 川= 篙茄： n e w m a n 等人基于均场方法给出了如下的近似表达式( 见文献 1 0 ) m 孺杀t a j 壶 但目前为止还没有，( “) 的精确显式表达式。 度分布 在基于“随机化加边”机制的n w 小世界模型中，每个节点的度至少为k 。 因此当七世时，一个随机选取的节点的度为的概率为 p = ( 。羔) 鲁】“。【- 一鲁】“2 而当七 如时，度为七的节点几乎不存在。因此，这类网络也 称为均匀网络或指数网络( e x p o n e n i j a ln e t w o r k ) 。近年在复杂网络研究上的另 一个重大的发现就是许多复杂网络，包括因特网、w w w 以及新陈代谢网络等 的连接度分布函数具有幂律形式。由于这些网络的节点的连接度没有明显的特 征长度，故称为无标度网络， 为了解释幂律分布的产生机理，b a r a b d s i 和a i b e r f 提出了一个无标度网络 模型( 见文献 3 ) 。他们认为以前的许多网络模型都没有考虑到实际网络的如 下两个重要特性： 1 ) 增长( g m w t h ) 特性：即网络的规模时不断扩大的。例如每个月都会有 大量的新的科研文章发表，而w w w 上则每天都有大量新的网页产生。 2 ) 优先连接( p r e f e r e n t j a la t t a c h m c n t ) 特性：即新的节点更倾向于与那些 具有较高连接度的“大”节点相连接。这种现象也称为“富者更富( r i c hg e t r i c h e r ) ”或“马太效应( m a t t h e we 舭c t ) ”。例如，新发表的文章更倾向于引用 1 4 顾士学住论文 m a s t e r st h e s i s 一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新 浪、雅虎等著名的站点。 基于网络的增长和优先连接特性，b a 无标度网络模型的构造算法如下( 图 5 ) ： 1 ) 增长：从一个具有聊。个节点的网络开始，每次引入一个新的节点并且 连到m 个已存在的节点上，这里聊m o 。 2 ) 优先连接：一个新节点与一个已经存在的节点i 相连接的概率兀f 与节 点i 的度舡之间满足如下关系 r l 4 南 n j j o 在经过f 步后，这种算法产生一个有= f + m o 个节点、脚f 条边的网络。 一+ 3 - 飞一风一+ 黔 l 图5 b a 无标度网络的演化( m = m o = 2 ) 。初始有两个节点，每次新增加的一个节点按“富 者愈富”的优先连接机制与网络中已存在的两个节点相连 1 4 2b a 无标度网络的统计性质 平均路径长度 b a 无标度网络的平均路径长度为： 。! 堡盟 l 0 9 1 0 9 r 这表明该网络也具有小世界特性( 见文献 1 1 1 2 ) 。 聚类系数 b a 无标度网络的聚类系数为( 见文献 1 3 ) c ，筹【k ( 孚) 一熹 学 这表明与e r 随机图类似，当网络规模充分大时b a 无标度网络不具有明显的 聚类效应。不过，b a 无标度网络的聚类系数比e r 随机图要大。 度分布 目前对b a 无标度网络的度分布的理论研究主要有三种方法：连续场理论 ( e o n 妇u u m 弧e 甜y ) ( 见文献 3 ) 、主方程法( 见文献 1 4 ) 和速率方程法( 见 文献 1 6 ) 。这三种方法得到的渐进结果都是相同的。其中，主方程法和速率方 程法是等价的。下面介绍主方程法得到的结果。 定义p ， 。f + 1 ) 为在 时刻加入的节点f 在f 时刻的度是f 的概率。 在b a 模型中，当一个新节点加入到系统中来时，节点l 的度增加1 的概率为m 兀f 盯丑，否则该节点的度保持不变。由此得到如下递推关系式 玳f + 1 ) 一等p 以山) 邯一志 而网络的度分布为 。您髀舰力) 它满足如下的递推方程 州：跨聊q 如1 i 矗 拈 从而求得b a 网络的度分布函数为 删- 揣砌2 一 这表明b a 网络的度分布函数可由幂律函数近似描述。 需要指出的是，对b a 无标度网络模型的构造及其理论分析的严格性等还 存在一些争议( 见文献 1 1 ) 。 介数 节点n 的介数等于经过它的最短路径的条数。由b a 模型的节点连接方式， 硕士学位论文 m a s t e r st h e s i s 及其统计量的特性，其介数分布不同于随机图的较均匀的分布，也基本符合幂 函数律分布( 见文献【5 】) 。 1 4 3 鲁棒性与脆弱性 现在假设给定一个网络，每次从该网络中移走一个节点，这也就同时移走 了与该节点相连的所有的边，从而有可能使得网络中其它节点之间的一些路径 中断。如果在节点f 和节点f 之间有多条路径，中断其中的一些路径就可能会使 这两个节点之间的距离办增大，从而整个网络的平均路径长度也会增大，而 如果节点l 和，之间的所有路径都被中断，那么这两个节点之间就不再连通了。 如果在移走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络的 连通性对节点故障具有鲁棒性( 见文献 1 5 ) 。 在文献 1 7 中比较了e r 随机图和b a 无标度网络的连通性对节点去除的 鲁棒性。该文献考虑了两类节点去除策略：一是随机故障策略，即完全随机地 去除网络中的一部分节点，二是蓄意攻击策略，即从去除网络中度最高的节点 开始，有意识地去除网络中一部分度最高的节点。假设去除的节点数占原始网 络总节点数的比例为疗可以用最大连通子图地相对大小s 和平均路径长度f 与 ，地关系来度量网络的鲁棒性。研究发现，e r 随机图和b a 无标度网络之间存 在及其显著地差异。无标度网络对随机节点故障具有极高地鲁棒性：与随机图 相比，最大连通子图的相对大小在相对高得多的，时才下降到零而其平均路径 长度的增长则要缓慢的多( 见文献 1 7 ) 。无标度网络的这种对随机故障的高度 鲁棒性来自域网络度分布的极端非均匀性：绝大多数节点的度都相对很小而有 少量节点的度相对很大。当，较小时，随机选取得节点都是度很小的节点，去 除掉这些节点对整个网络的连通性不会产生大的影响。然而，正是这样非均匀 性使得无标度网络对蓄意攻击具有高度的脆弱性：只有有意识地去除网络中极 少量度最大地节点就会对整个网络地连通性产生大地影响( 见文献 1 7 ) 。在文 献 1 7 中形象地比较了随机网络和无标度网络地鲁棒性。可以看到，即使随机 去除网络中的大量节点，无标度网络仍然可保持基本的连通性，而随机去除同 样多的节点则可使一个同样规模的随机网络分成多个孤立的子网，但蓄意去除 少量度最高的节点就可破坏无标度网络的连通性。 以因特网为例，因特网的前身是2 0 世纪6 0 年代后期由美国国防部高级研 究计划署( a rp ：a ) 研制的a p p a n e t 。其主要的目的之一就是为了使得在一些 1 7 硕士举住论文 m a s t e r st h e s l s 子网和网关发生故障的情况下网络还能维持基本的通信工作。如今因特网已经 发展成为一个规模巨大的网络，并在人类社会生活中起着越来越重要的作用。 而因特网上每天都在发生着各种各样的故障并经常受到黑客的攻击。因此，因 特网是否能保持它的功能无疑是一个重要的课题。b e n 、j e o n g 和b a r a 酗s i 在 上述文章中研究了两个实际网络对随机故障和蓄意攻击的鲁棒性和对蓄意攻击 的脆弱性是无标度网络的一个基本特征，其根源在于无标度网络中的度分布的 不均匀性。事实上，近些年不同