（控制理论与控制工程专业论文）基于自治系统的internet拓扑结构建模研究.pdf

哈尔滨理t 大学t 学硕十学位论文 基于自治系统的i n t e m e t 拓扑结构建模研究 摘要 i n t e m e t 作为当今人类社会信息化的标志，其规模在以指数速度高速增长 的同时，“面貌 已与原型阿帕网大相径庭，依其高度的复杂性，可以将其看 作一个由计算机构成的“生态系统 。虽然i n t e r n e t 是由人类亲手建造的，但 却没有人能说出这个庞然大物看上去到底是个什么样子，运作得如何。i n t e m e t 拓扑建模研究就是探求在这个看似混乱的网络之中蕴含着哪些还不为我们所知 的规律。而且，i n t e r n e t 与生俱来的异构性、动态性、发展的非集中性以及如 今庞大的规模都给拓扑建模带来巨大的挑战，i n t e r n e t 拓扑建模至今仍然是一 个开放性的问题，在计算机网络研究中占有重要地位。 本文在深入研究目前已有网络拓扑生成器的基础上，对w a x m a n 随机型拓 扑生成器进行了改进，并提出了一种基于自治系统的综合i n t e r n e t 拓扑建模方 法，主要从以下几个方面展开： 1 分析了目前主流的i n t e m e t 拓扑模型，包括e r 、w a x m a n 、t i e r s 、 t r a n s i t s t u b 和幂律模型等，从节点度分布、连通性、层次性、鲁棒性等方面探 讨了各个模型的优缺点。 2 构造了一种基于k - 均值聚类法的随机型拓扑生成器，使网络节点均匀 且疏密得当，根据节点的重要性不同，设置了不同的连接度，在一定程度上增 强了网络拓扑图的连通性。 3 针对i n t e m e t 网络具有层次性、幂律性的特点，提出了一种基于自治系 统的综合i n t e m e t 拓扑模型，该模型把幂律分布规律融入到层次算法中去，解 决了原来的层次拓扑模型不满足幂律分布规律的问题。 这种基于自治系统的综合i n t e r n e t 拓扑模型，综合了以前三种模型的优 点，根据每一层网络的重要性不同而采用不同的节点分布方式，既保证了节点 之间的连通性和稳定性，又体现了i n t e m e t 的层次性，因而，能较好的模拟真 实网络的拓扑结构。 关键词i n t e m e t ；拓扑生成器；自治系统；拓扑模型 哈尔滨理工人学工学硕上学位论文 r e s e a r c ho ni n t e r n e tt o p o l o g ym o d e l i n gb a s e do n a u t o n o m o u ss y s t e m a b s t r a c t i n t e r a c t1 5t a k e n 勰t h es y m b o lo fh u m a ns o c i e t yi n f o r m a t i o n i z a t i o n ，w h i l ei t s s c a l ef a s tg r o w t hb yi n d e xs p e e d ，i t sa p p e a r a n c eh a sb e e nw i d e l yd i v e r g e n t 、衍血 p r o t o t y p ea r p a n e t ，a c c o r d i n gt o i t s h i g hc o m p l e x i t y ，m a yr e g a r da sa “e c o s y s t e m ”w h i c hc o n s t i t u t e db yt h ec o m p u t e r a l t h o u g hi n t e m e ti sc o n s t r u c t e d b yh u m a n i t yp e r s o n a l l y ，n o b o d yc a ns a yo u tt h ea p p e a r a n c eo ft h ec o l o s s u s ，h o w t oo p e r a t e i n t e r n e tt o p o l o g ym o d e l i n gr e s e a r c h e sa b o u tt h em l e sr e s e m b l i n gi nt h e c h a o t i cn e t w o r kw h i c hh a sb e e nn o tk n o w nf o ru s a n di n t e r n c tb o r n si s o m e r i s m ， d y n a m i c ，n o n - c o n c e n l r i e i t yo fd e v e l o p m e n ta sw e l la st h ep r e s e n th u g es c a l eb n n g h u g ec h a l l e n g e st ot h et o p o l o g ym o d e l i n g n eh a t e r n e tt o p o l o g ym o d e l i n gi ss t i l l a l lo p e nq u e s t i o nu n t i ln o wa n dh o l d st h ei m p o r t a n tp o s i t i o ni nt h ec o m p u t e rn e t w o r k r e s e a r c h i nt h ef o u n d a t i o no fr e s e a r c ha b o u tt h ep r e s e n tn e t w o r kt o p o l o g yg e n e r a t o r s d e e p l y ，t h i sa r t i c l eh a sm a d ei m p r o v e m e n t st ot h ew a x m a nt o p o l o g yg e n e r a t o r ， a n dp r o p o s e do n ek i n do fs y n t h e s i si n t e m e tt o p o l o g ym o d e l i n gm e t h o db a s e do n a u t o n o m o u ss y s t e m , e x p a n d i n gf r o mt h ef o l l o w i n ga s p e c t s ： 1 a n a l y s i z e dt h em a i n s t r e a mi n t e m e tt o p o l o g ym o d e la tp r e s e n t ，i n c l u d i n g e r ，w a x m a n ，t i e r s ，t r a n s i t - s t u ba n dt h ep o w e r - l a wm o d e l ，a n ds oo n ，f r o m t h ea s p e c t so fn o d ed i s t r i b u t i o n ，c o n n e c t i v i t y ，h i e r a r c h y ，r o b u s t n e s sd i s c u s s e dt h e a d v a n t a g e sa n dd i s a d v a n t a g e so f e a c hm o d e l 2 c o n s t r u c t e do n ek i n do fr a n d o mt o p o l o g yg e n e r a t o rb a s e do nk - m e a n s c l u s t e r i n ga l g o r i t h m 1 r 1 1 i st o p o l o g yg e n e r a t o rh a sm a d et h en o d e sm o r eu n i f o r m ， a c c o d i n gt o d i f f e r e n ti m p o r t a n c e so ft h en o d e s ，m a n i f e s t e dt h ed i f f e r e n tn o d e c o n n e c t i o nd e g r e e ， e n h a n c i n gt h en o d ec o n n e c t i v i t ya ta c e r t a i ne x t e n t 3 i nv i e wo ft h eh a t e r n e tn e t w o r kh a sc h a r a c t e r i s t i c so fh i e r a r c h i c a la n d p o w e r - l a w ，o n ek i n do fs y n t h e s i si n t e m e tt o p o l o g ym o d e lb a s e do na u t o n o m o u s i i 哈尔滨理t 大学- 丁学硕十学位论文 s y s t e mh a sb e e np r o p o s e d t i l i sm o d e li n t e g r a t e st h ep o w e r - l a wd i s t r i b u t i o nr u l et o t h el e v e la l g o r i t h m ，s o l v i n gt h eq u e s t i o no fo r i g i n a ll e v e lt o p o l o g ym o d e lc a n t s a t i s f yt h ep o w e r - l a wd i s t r i b u t i o nr u l e t i l i sl ( i n do fs y n t h e s i si n t e m e tt o p o l o g ym o d e lb a s e do na u t o n o m o u ss y s t e m ， s y n t h e s i z e dt h ea d v a n t a g e so fb e f o r e h a n dt h r e ek i n d so fm o d e l s ，s e l e c t i n gd i f f e r e n t n o d ed i s t i l b u t i o nm e t h o d sa c c o r d i n gt oe a c hn e t w o r k sd i f f e r e n ti m p o r t a n c e ， g u a r a n t e e dt h en o d e sc o n n e c t i v i t ya n ds t a b i l i t y ，a n dm a n i f e s t e dt h ei n t e m e t h i e r a r c h i c a l ，s oc a ns i m u l a t er e a ln e t w o r kt o p o l o g yw e l l k e y w o r d si n t e m e t ，t o p o l o g yg e n e r a t o r ，a u t o n o m o u ss y s t e m ，t o p o l o g ym o d e l i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于自治系统的 n t e m e t 拓 扑结构建模研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和 集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字：万潍白队日期：乃叫年 月乙日 i i j 哈尔滨理工大学硕士学位论文使用授权书 基于自治系统的i i l t e r n e t 拓扑结构建模研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理 工大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部 或部分内容。 本学位论文属于 保密1 3 ，在年解密后适用本授权书。 不保密团。 ( 请在以上相应方框内打) 作者签名： 导师签名： 虚人钍 高中久尚寸久 月乙铂 月己自 年 年 夕7 白 冷 泐 h 期 期 哈尔滨理工大学工学硕上学位论文 1 1 研究的目的及意义 第1 章绪论 近年来，大规模的复杂i n t e m e t 网络拓扑分析研究引起了计算机及物理、 数学等多个领域研究人员的兴趣。然而，i n t e m e t 网络自身具有复杂性和多变 性，直接将其作为实验对象进行研究和分析变得十分困难。因此，人们希望根 据真实网络数据和关键特征对i n t e m e t 网络拓扑进行模型抽象，以拓扑模型代 替真实i n t e m e t 网络作为实验对象进行研究分析，达到通过拓扑建模认识 i n t e m e t 基本特性并指导实际网络建设的目的。 2 0 世纪9 0 年代以来，i n t e m e t 在世界范围内迅速发展，到1 9 9 6 年大约有 1 2 8 8 万多台主机接入i n t e m e t ，2 0 0 1 年约有1 0 9 5 7 多万台主机接入i n t e m e t ，到 2 0 0 7 年约有1 ，5 亿台主机接入i n t e m e t 。随着计算机网络技术的发展和接入 i n t e m e t 主机数量的大幅增加，网络规模急剧膨胀，网络的拓扑结构也越来越 复杂，获得完整、准确的i n t e r n e t 拓扑结构变得越来越困难。网络的复杂性、 业务的多样性和接入的随机性使其结构不断的变化，从网络安全、网络管理及 网络研发各个方面都越来越需要深入了解i n t e m e t 整体的拓扑结构，分析其结 构行为，以提出优化网络配置的合理建议。因此探测i n t e r n e t 拓扑结构成为了 目前的一个研究热点。 随着i n t e m e t 越来越广泛地被人们所认识，人们对网络的研究也在逐步的 深入。i n t e m e t 拓扑图为大范围开发、利用i n t e m e t 提供了一个有力的工具。网 络研究者可以利用拓扑生成器生成的网络拓扑图进行网络仿真实验，但在目前 的研究中，还没有形成统一的参数集来全面评估i n t e m e t 拓扑图。因而，研究 者只能尽可能使用更多参数来分析和实验，希望能使拓扑图更好地“逼近”实 际i n t e m e t 拓扑。对i n t e m e t 拓扑研究及拓扑图生成尤其是自治系统级拓扑研究 已经成为学术界、企业界所普遍关心的重要问题之一。目前对i n t e r n e t 拓扑研 究的需求是来自各方面的，既有网络管理、应用研究也有网络安全等方面的需 要，因而，开展i n t e m e t 拓扑研究是具有十分重要的实际意义的。 1 2i n t e m e t 拓扑建模的研究内容 i n t e r n e t 拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、 哈尔滨理工大学工学硕j _ 学位论文 统计学、数据挖掘、可视化以及数学建模等多个研究领域。i n t e m e t 拓扑建模 研究内容可归结为4 个问题： ( 1 ) i n t e r n e t 网络拓扑数据获取：如何获取一份完整而且准确的i n t c r n e t 网 络拓扑数据是一项困难而复杂的工作。由于i n t e m e t 庞大而且复杂，在现有的 技术条件下获取一份完整的拓扑数据几乎是不可能的。目前来说，虽然己经提 出了多种方法，但怎样获得一份更加完整的i n t e m e t 网络拓扑数据仍然是研究 领域中需要进一步解决的问题。 ( 2 ) i n t e r n e t 网络拓扑特征发现：i n t e r n o t 虽然是庞大而复杂的，但它自身仍 然存在着某些规律和特征等待我们去探索。在过去的几年里，i n t o m e t 网络拓 扑特征发现一直是i n t e m e t 网络拓扑研究领域中的热点问题，通过研究人员的 不断努力，一些新奇的网络拓扑特征逐渐地探索出来。 ( 3 ) i n t o r n o t 网络拓扑建模：i n t e m o t 网络拓扑建模是利用已经发现的拓扑特 征把i n t e m e t 的拓扑结构描述和刻划出来。 ( 4 ) i n t c r n c t 网络内部关系分析：当我们得到一幅i n t e r n e t 网络拓扑图后， 如何理解和认识图内节点关系也是目前i n t e m e t 网络拓扑研究的热点问题。 前面3 个问题分别对应于3 个研究方向，即拓扑结构测量、拓扑特征发现 和拓扑生成器开发。其中，拓扑结构测量是拓扑建模的基础；拓扑特征发现是 拓扑建模的核心；拓扑生成器就是拓扑模型、算法的软件实现1 。 1 3i n t e m e t 拓扑建模的研究现状 一直以来，不同领域的研究者都对i n t e r n e t 网络拓扑建模进行了大量的研 究工作。对网络理论研究者来说，其建模目的是根据所获得的真实网络拓扑数 据进行网络模拟，从而分析预测新的路由协议等对不同层面i n t e r a c t 网络连通 性的影响，以及拓扑变化对网络性能的影响，并最终改善网络技术、提高网络 服务性能；对非网络理论研究者，尤其是对数理学领域的研究人员，其对 i n t e m e t 网络拓扑建模的研究出发点是探索普遍存在的规则原理。例如，数理 学者希望发现小范围网络模型与大规模网络模型之间的必然联系，研究复杂网 络领域的普遍规律卜“。不同领域的研究方法和目的差异造成i n t e r n e t 网络拓扑 建模可能存在不同的模型生成算法和相关度量指标，在具体建模过程中，要根 据研究需要进行选择；但是总体说来，无论何种领域的研究者，其建模研究的 共同思路是一致的。i n t e m e t 网络拓扑建模按照层次的不同，可分为自治系统 ( a u t o n o m o u ss y s t e m ，a s ) 级拓扑建模与路由器级拓扑建模。 2 哈尔滨理工人学工学硕士学位论文 1 3 1 自治系统级拓扑建模研究现状 i n t e m e t 网络自治系统级拓扑研究也经历了发展的过程。从最初的i n t e r n e t 网络拓扑研究由于缺乏数据，只能进行经验假设，到现在已经可以针对相对完 整的数据进行统计分析，并可对各种假设进行验证。从1 9 9 5 年开始，大规模 的i n t e m e t 拓扑测量工作逐渐展开，到目前为止，已经收集到了大量的拓扑数 据。这些拓扑数据相对完整，为i n t e r n e t 网络拓扑研究者提供了有利的实验数 据支持。i n t e m e t 网络拓扑的建模工作也取得了长足的进展，从相对简单的随 机模型到复杂的幂律模型，其结果都越来越接近真实的i n t e m e t 。对于节点间 关系的理解更是有了质的突破，从原来对关系的一无所知到现在对关系进行定 义和区分。所有这些都说明了i n t e m e t 网络拓扑研究在过去的十几年里取得了 一些成果。 最早的网络拓扑模型是w a x m a n 于1 9 8 8 年提出的一种平面随机模型 w a x m a n 模型一，这个模型一直沿用了很多年。1 9 9 6 年，d o a r 提出了t i e r s 层 次模型p 1 ，该模型刻划了i n t e m e t 所具有的层次特征。1 9 9 7 年，z e g u r a 等人提 出了另一种层次模型咄n s i t s t u b 模型州。层次模型来自对i n t e r n e t 结构所 具有的层次特征的认识，在同一层上的节点出度接近，不同层间节点出度差别 很大，对同一层上的节点布置借用w a x m a n 模型方法。1 9 9 9 年，f a l o u t s o s 等 人发现i n t e m e t 拓扑结构中存在的幂律( p o w e r - l a w ) 关系占极为重要的地位。 幂律说明在i n t e m e t 中既不存在w a x m a n 模型中那样的“平等”，也不像t i e r s 和t r a n s i t s t u b 模型那样“等级森严，而是具有一种松散的层次性。幂律同 时说明i n t e r n e t 具有高度非均一性，即少数节点具有很高的出度，而大量节点 具有较小的出度。同时，幂律的发现也给出一个启示：i n t e r n e t 中某个属性的 平均值不能准确地刻划这一属性，应该尝试用某个指数来进行刻划。幂律的发 现将i n t e r n e t 拓扑与一些生物学、社会学中的复杂网络联系起来，使其成为无 尺度网络( s c a l e f r e e ) 的一个实例，在i n t e m e t 拓扑研究与系统学研究之间架起 了一座桥梁。至从2 0 0 0 年以来，研究人员开发了许多遵循幂律的拓扑生成算 法p 一1 以及拓扑生成器b “，为i n t e m e t 拓扑建模提供了有力的支持。 目前，对拓扑模型、拓扑生成算法和拓扑生成器含义的界定比较模糊，研 究过程中也常将前两者的软件实现与专门的拓扑生成器拿到一起来比较，或者 将生成算法也称为拓扑模型。造成这一情况的原因是，一些生成算法涉及到了 i n t e r n e t 的内在机制，如e s f ( e x t e n ds c a l ef r e e ) ；而一些拓扑生成器又包含了一 些i n t e m e t 细节特征，如n e m 。这三个概念既相互区别又有交叉，一般来说， 哈尔滨理t 大学t 学硕十学位论文 拓扑模型是用数学语言对i n t e m e t 宏观拓扑特征进行刻画，并不一定要提出如 何构造这一特征；生成算法是描述如何产生一幅具有某个模型特征的拓扑图， 不需要软件化；拓扑生成器要实现依据已有生成算法来产生具有某些i n t e m e t 特征的拓扑图，需要编程实现，因而拓扑生成器的开发需要从生成图应用的角 度加以考虑。 1 3 2 路由器级拓扑建模研究现状 由于技术水平、安全考虑等各种原因，现有的i n t e m e t 路由器级拓扑发现 方法无法保证测量目标集合的完备性，这种真实路由器级网络拓扑数据的不完 整性和不完备性极大地影响了后继的拓扑建模研究工作“。因此，目前对于路 由器级的拓扑建模研究仍比较少，该方向的拓扑建模研究已成为i n t e r n e t 拓扑 建模研究中的主要问题之一，相应的分析理论还不够成熟。 目前，关于路由器级拓扑建模的研究成果大都集中在对路由器级拓扑结构 是否同样存在幂律分布特性的讨论上，出现最早的是文献【1 4 】对p a m i o t - g r a d 数据集川中存在幂律分布特性的论证，相关研究包括m a g o n i 等人叫通过3 个 不同规模的路由器级拓扑实例验证了幂律分布特性；b r o i d o 等人1 则基于 s k i t t e r 所获取的数据讨论了路由器级拓扑的度分布。 在幂律分布特性被验证以后，无标度模型曾被一度认为可同样适用于路由 器级拓扑建模。文献 1 8 】首先指出这种不考虑设计因素的生长模型不适合于描 述i n t e r n e t 拓扑，应该寻找具有优化设计特点的生长模型，应该权衡资源消耗 等因素；文献 1 9 】认为成本、性能、结构优化等因素在路由器级i n t e r n e t 拓扑 建模过程中可能具有极为重要的影响，并指出应该以此为理论基础来解释幂律 特性的生成原理。基于文献 1 9 】的启发，“等人p 提出基于网络性能优化设计 的路由器级拓扑建模方法，即启发式优化拓扑模型，简称h o t ( h e u r i s t i c a l l y o p t i m a lt o p o l o g i e s ) 模型；文献【2 0 】论证说明各i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 所部 署路由器的自身性能和i s p 的经济考量是影响路由器级拓扑的最重要因素，并 且验证了仅基于节点度分布的无标度模型不符合真实的路由器级拓扑结构。这 种启发式优化的建模思想为路由器级拓扑建模指出了新的发展方向“，即从随 机原则到设计原则的转变。 在现有的路由器级拓扑建模中，随着h o t 模型的提出，已更多地开始考 虑能够反映实际网络行为特征的度量指标，如与路由器性能相关的链路带宽、 与反映网络路由器实际部署的节点间距离等等，如文献 2 2 1 q hc i s c o 提出的层 4 哈尔滨理t 大学t 学硕卜学位论文 次设计模型( 1 e v e ld e s i g nm o d e l ) 等，但目前仍不够成熟，其典型性与适用性都 需要进一步研究分析。 1 4 本文研究的主要内容 本文通过对w a x m a n 随机型拓扑生成器的探讨和分析，发现其缺点和不 足。采用了k - 均值聚类法分布节点的方式，对w a x m a n 随机型拓扑生成器进 行了改进，取得了满意的效果，更好的模拟了i n t e r n e t 拓扑模型。并且通过分 析目前存在的拓扑模型各自的优缺点，提出了一种基于自治系统的综合 i n t e r n e t 拓扑模型建模方法，把幂律分布规律融入到层次算法里去，解决了目 前的层次拓扑模型不满足幂律分布规律的问题。 本文重点讨论和研究的内容包括： 1 首先介绍了刻画复杂网络的几个统计性质，然后详细介绍了几种基本 的网络拓扑模型，如规则网络、随机网络、小世界网络、无标度网络和局域世 界演化网络，并简要地分析了它们的统计性质。 2 分析了目前主流的i n t e m e t 拓扑模型，包括e r 、w a x m a n 、t i e r s 、 t r a n s i t s t u b 、幂律模型等，从节点度分布、连通性、层次性、鲁棒性等方面探 讨了各个模型的优缺点。 3 在分析现有的w a x m a n 随机型拓扑生成器不足的基础上，构造了一种 基于k 均值聚类法的随机型拓扑生成器，使网络节点均匀且疏密得当，根据 节点的重要性不同，设置了不同的连接度，在一定程度上增强了网络拓扑图的 连通性。 4 根据i n t e m e t 网络具有层次性、幂律性的特点，提出了一种基于自治系 统的综合i n t e r n e t 拓扑模型。该模型将网络分为三层，分别采用了不同的节点 连接方式，综合了已有模型的优点，既保证了节点之间的连通性和稳定性，又 体现了i n t e m e t 的层次性，因而能较好的模拟真实网络的拓扑结构。 哈尔滨理1 二大学工学硕士学位论文 第2 章网络拓扑的统计性质及其基本模型 2 1 网络的统计性质 物理学对网络拓扑的研究重在其统计性质，对这些统计性质的描述和理解 是我们进行复杂网络相关研究的第一步。 2 1 1 网络的分类 网络由一系列节点和与之相连的边组成，如果网络中任意节点对( f ，) 和 ( j ，f ) 对应同一条边，则该网络为无向网络( u n d i r e c t e dn e t w o r k ) ，否则称为有向 网络( d i r e c t e dn e t w o r k ) ；如果每条边都赋予相应的权值，那么该网络就成为加 权网络( w e i g h t e dn e t w o r k ) ，否则称为无权网络( u n w e i g h t e dn e t w o r k ) 。当然， 无权网络也可以看作是每条边的权值都为l 的等权网络咿1 。本文所讨论的都是 无权无向的网络，并且假设没有重边和自环，即任意两个节点之间至多只有一 条边，且没有同一个节点为起点和终点的边。 2 1 2 平均路径长度 传输延迟是影响网络性能、信息传递的重要因素，而距离和直径是度量传 输延迟的重要参数。但网络距离和直径都无法对网络的总体特征进行评价，因 此需要引入网络的平均路径长度参数来度量。网络中两个节点f 和歹之问的距 离d 。定义为连接这两个节点的最短路径的边数。网络中任意两个节点之间的最 大值称为网络的直径( d i a m e t e r ) ，记为d ，即 d 2 肾略 ( 2 _ 1 ) l ， 。 网络的平均路径长度三定义为任意两个节点之间的距离的平均值，即 = _ l ! d 。 ( 2 2 ) 主n ( n - 1 ) 其中，为网络节点数。网络的平均路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) ，它描述了网络中节点间的分离程度，即网络有多 小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长 度比想象的小得多，称之为小世界效应”1 。 6 哈尔滨理工人学工学硕一 = 学位论文 2 1 3 聚类系数 聚类系数用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会 网络中，你朋友的朋友可能也是你的朋友，或者你的两个朋友可能彼此也是朋 友。其计算方法为假设节点i 通过k 条边与其它k 个节点相连接，如果这些节点 都相互连接，它们之间应该存在k ( k 一1 ) 2 条边，而这些节点之间实际存在的 边数只有e 的话，则它与k ( k 一0 2 之比就是节点i 的聚类系数，即 g = 面2 e 面( 2 - 3 ) 网络的聚类系数就是整个网络中所有节点的聚类系数的平均。显然，只有在全 连通网络中每个节点都与其余所有的节点相连接，聚类系数才能等于1 ，一般 均小于1 。在完全随机网络中，co cn ，然而实证结果却表明大部分大规模 真实网络中的节点倾向于聚集在一起，尽管聚类系数c 远远小于1 ，但都远比 。1 大。 2 1 4 度和度分布 图论中节点i 的连接度k ；为节点连接的边的总数目，在无向网络中节点连 接度和节点出度意义相同。所有节点的度的平均值称为网络的平均度，定义为 。网络中节点的度分布用分布函数p ( k ) 来表示，表示一个任意选择的节 点恰好有k 条边的概率，也等于网络中度数为k 的节点的个数占网络节点总个 数的比值。网络的平均度 表示为 = 一1y 屯 ( z - 4 ) n 2 1 5 介数 介数分为节点介数( n o d eb e t w e e n e s s ) 和边介数( e d g eb e t w e e n e s s ) ，节点介 数衡量了通过网络中该节点的最短路径的数目，反映了节点在网络中的枢纽 性，节点介数越大，说明这个节点的枢纽性越强，删除这样的节点会造成大量 节点对之间的最短路径变长；边介数定义为在网络的所有最短路径中，通过某 条边的最短路径的条数，类似地，边介数也同样反映了该边在网络中的枢纽 性。 哈尔滨理工人学工学硕l 学位论文 2 2 网络的基本模型 在w a t t s 和s t r o g a t z 关于小世界网纠2 习以及b a r a b d s i 和a l b e r t 关于无标度 网络瞄1 的开创性工作之后，人们对来自不同领域的大量实际网络的拓扑特征进 行了广泛的实证性研究。在此基础上，人们从不同的角度出发提出了各种各样 的网络拓扑结构模型2 7 1 ，包括：规则网络、随机网络、小世界网络、无标度网 络和局域世界演化网络等。 2 2 1 规则网络 规则网络是人们对复杂网络拓扑结构的最初认识，我们首先来看三种规则 网络。全局耦合网络( g l o b a l l yc o u p l e dn e t w o r k ) ，它的任意两个点之间都有边直 接相连，如图2 1a ) 所示，在具有相同节点数的所有的网络中，全局耦合网络 具有最小的平均路径长度l 。= 1 和最大的聚类系数c 。= l 。虽然全局耦合网络 模型反映了许多实际网络具有的聚类特性和小世界性质，但该模型作为实际网 络模型的局限性也是明显的：一个有个点的全局耦合网络有n ( n 一1 ) z 条 边，然而大多数大型实际网络都是很稀疏的，不可能完全连接。它们的边的数 目一般至多是o ( 忉而不是d ( 2 ) 。 o 涨 图2 - l 几种规则网络 a ) 全局耦合网络：b ) 最近邻耦合网络；c ) 星形网络 f i g 2 - 1s e v e r a lk i n d so fr e g u l a rn e t w o r k s a ) g l o b a l l yc o u p l e dn e t w o r k ：b ) n e a r e s t - n e i g h b o rc o u p l e dn e t w o r k ：c ) s t a rc o u p l e dn e t w o r k 最近邻耦合网络( n e a r e s t n e i g h b o rc o u p l e dn e t w o r k ) 是一个得到大量研究的 稀疏的规则网络模型，其中每一个节点只和它周围的节点相连。具有周期边界 条件的最近邻耦合网络，由围成一个环的个点组成，其中每个节点都与它左 右定2 个邻居点相连，k 是一个偶数，如图2 1b ) 所示。对较大的k 值，该网 络的聚类系数为 哈尔滨理工人学工学硕士学位论文 巳= 砥3 ( k 面- 2 ) 三( 2 - 5 ) 因此，这样的网络是高度聚类的。然而，最近邻耦合网络却不是一个小世界网 络，因为它的平均路径长度为 l ，= 三一专)(2600(iv 0 0 ) 。2 石一 专) ( 2 。) 可见，随着网络规模的增大，局部耦合网络的平均路径长度线性增大。 星形耦合网络( s t a rc o u p l e dn e t w o r k ) 是另外一种常见的规则网络，它有一 个中心点，其余的一1 个节点都只与这个中心点连接，而它们彼此之间互不 相连，如图2 1c ) 所示。星形网络的平均路径长度为 k - 2 - 耥一2 ( ) ( 2 - 7 ) 星形网络的聚类系数为 c 埘：了n - i - - l ( j ) k “z 8 ) 乙蛐2 ：- 1 i v _ j o ， 有些研究文献则定义只有一个邻居节点的聚类系数为0 ，依此定义的话，星形 网络的聚类系数则为0 。 2 2 2 随机网络 在发现规则网络并不能很好地解释复杂系统中的网络拓扑之后，与完全规 则网络相反的是完全随机网络得到了研究，一个典型的模型是e r d o s 和r e n y i 于4 0 多年前开始研究的e r 随机网络模型m 叫。 假设有大量的纽扣散落在地上，以相同的概率p 给每对纽扣系上一根线。 这样就会得到一个有个点，约叫( 一1 ) 2 条边的随机图，如图2 2 所示。 o o o o o a ) v = o b ) v = 0 ic ) l 归o 15d ) l r 。0 2 5 图2 - 2 随机图的演化示意图泸1 0 ) f i g 2 - 2r a n d o md i a g r a m se v o l u t i o ns c h e m a t i cd i a g r a m ( 肛l0 ) e r d o s 和r e n y i 系统地研究了当专时，e r 随机图的性质与概率p 之 9 间的关系。e r d o s 和r e i l 妒最重要的发现是e r 随机图的许多重要的性质都是突 然涌现的。也就是说，对于任一给定的概率p ，要么几乎每一图都具有某个性 质q ，要么几乎每一个图都不具有该性质。例如对于上述纽扣网络，如果捡起 一个纽扣，那么将有多少个纽扣也会被跟着拎起来呢? 结果显示，如果概率p 大于某个临界值p ，o c i n n n ，那么几乎每一个随机图都是连通的，也就是 说，你随机地捡起一个纽扣都会拎起地上几乎所有的纽扣。 e r 随机图的平均连接度是 _ p ( n 1 ) p n 。设艘是随机图的平均 路径长度。直观上，对于e r 随机图中随机选取的一个点，网络中大约有 k 个其它的点与该点之间的距离等于或非常接近于f p 。因此 n o c l n ，即e 膏o cl n i n 。这种平均路径长度随网络规模的对数增 长的特性就是典型的小世界特征。l n 的值随增长的很慢，这就使得即使是 规模很大的网络也可以具有很小的平均路径长度。 e r 随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均 为p 。因此，e r 随机图的聚类系数是c = p = n 1 ) 。当p 较小时( 0 p 1 ) ，重新连线后得到的网络与原始 的规则网络的局部属性差别不大，从而网络的聚类系数变化也不大 ( c ( p ) c ( 0 ) ) ，但其平均路径长度却下降的很快( l ( p ) ( 2 ) 聚类系数 w s 小世界网络的聚类系数为 c ( 加黼”p ) 3 ( 2 - 1 2 ) n w 小世界网络的聚类系数为 c ( p ) = 硒面3 ( 而k - 瓦2 ) 而 ( 2 - 1 3 ) ( 3 ) 度分布 对于基于“随机化重连”机制的w s 小世界网络，当k 之k 2 时可得如下 公式 州= 删r n - - o ”力, p ( x 2 ) - 黑p 嘣，2 ( 2 川) 而当，k k 2 时p ( k ) = 0 。 在基于“随机化加边”机制的n w 小世界模型中，每个节点的连接度至少 为k 。因此k k 时，一个随机选取的节点的度为k 的概率为 h 七，= ( ：k ) ( 等) 卜置( 一等) 肛“f c 2 彤， 而当，k 时，度为k 的节点几乎不存在。因此，这类 网络也称为均匀网络或指数网络( e x p o n e n t i a ln e t w o r k ) 。近年在复杂网络研究上 的另一个重大的发现就是许多复杂网络，包括因特网、新陈代谢网等的连接度 分布函数具有幂律形式。由于这些网络节点的连接度没有明显的特征长度，故 称为无标度网络。 哈尔滨理t 大学丁学硕l ：学位论文 为了解释幂律分布的产生机理，b a r a b d s i 和a l b e r t 提出了一个无标度网络 模型，称为b a 模型。他们认为以前的许多网络模型都没有考虑到实际网络的 如下两个重要特性： ( 1 ) 增长特