（计算机软件与理论专业论文）as级internet宏观拓扑特征演化分析及核数建模.pdf

东北大学硕士擘位论文摘要 a s 级i n t e m e t 宏观拓扑特征演化分析及核数建模 摘要 i n t e r n e t 作为一个典型的复杂网络实例，关于其宏观拓扑结构特征的分析及建模的 研究是目前受到学术界广泛关注的热点问题，对网络的应用、发展以及下一代网络建设 都具有重要意义。近年来人们在该领域取得了长足的进展，发现了许多隐藏在网络内部 的特征规律。但目前的相关研究工作或是数据统计的空间量级较小，或是数据分析时间 跨度较短，或是度量方法较为简单，所以需要做更为全面的迸一步的研究。 本文研究工作基于c a i d a ( t h ec o o p e r a t i v ea s s o c i a t i o nf o ri n t e m e td a t aa n a l y s i s ) s k i t c e r 项目授权的海量数据，数据采集时间为2 0 0 2 年1 月至2 0 0 6 年6 月。文中详细统 计了a s ( a u t o n o m o u ss y s t e m ，自治系统) 级i n t e r a c t 拓扑的多种宏观特征，进一步分析了 网络连通性与幂律特征，对网络的代表性拓扑特征值进行时序分析，并统计了节点的生 存周期，分析了其时效规律。给出 n t e m e t 长时间跨度下，拓扑演变的平坦化趋势，分 析了维持网络连通性及幂律性的主要因素，并给出了分析结果在提高网络传输性能及病 毒预防方面的应用。 。 论证了核数对度量拓扑层次性的意义，统计了核数与度值间的关系，说明核数可以 用来更精确的刻画网络拓扑层次。在大时间跨度的数据集上，分析了网络核数的演化规 律，并对数据做时间切片分析，得到网络各层次间的节点及连接分布规律。通过分析， 得出最高核在网络中具有的极大影响力的结论，并基于最高核的核心地位，提出制定以 其为重点的网络故障预防策略。 进一步统计a s 网络中各层次的节点分布以及连接趋势，通过曲线拟合计算得出具 体公式，在此基础上给出一种面向a s 级i n t e m e t 网络的拓扑模型。实验证明，与以往 的经典模型相比，该模型在保证节点度幂律分布的前提下，还可以体现i n t e t n e t 的多层 次拓扑。通过对模型中连接优先概率公式的试验分析，表明网络核数对拓扑的性质具有 重要意义。 关键词：a s ；i n t e m e t 拓扑；幂律分布；拓扑建模；核数；网络演化；连通性 一一 东北大学硕士学位论文 i n t e r n e ta s - l e v e lm a c r o s c o p i c t o p o l o g yc h a r a c t e r i s t i c s e v o l v e m e n ta n a l y s i sa n dc o r e n e s sm o d e l a b s t r a c t i n t e r n e ti sac l a s s i c a li n s t a n c eo fc o m p l e xn e t w o r ka n dt h er e s e a r c ha n dm o d e l i n go ni t s t o p o l o g yh a sb e c o m eah o tt o p i c 缸p r e s e n ta n di t i ss i g n i f i c a n tf o rn e t w o r ka p p l i c a t i o n , d e v e l o p m e n ta n dt h eb u i l d i n go ft h en e x tg e n e r a t i o n r e c e n t l y , r e s e a r c h e si nt h i sf i e l dh a v e a c h i e v e dg r e a td e v e l o p m e n t sa n dm a n yc h a r a c t e r i s t i cl a w sb e h i n do ft h ei n t e r n a ln e t w o r k w e r ef o n do u t c u r r e n t l yt h er e l a t e dr e s e a r c hn e i t h e rh a se n o u g hs p a c eo rt i m es p a nf o rd a t a c o m p u t i n g a n da n a l y z i n g ,n o rh a sm u c hc o m p l e xm e a s u r e m e n t s t h e r e f o r e ，m o r e c o m p r e h e m i v er e s e a r c hn e e d st ob ed o n e i nt h i sd i s s e r t a t i o n , t h er e s e a r c hb a s e do nt h em a s s i v ed a t aa u t h o r i z e db yc a i d a ( t h e c o o p e r a t i v ea s s o c i a t i o nf o ri n t e r a c td a t aa n a l y s i s ) s k i t t e rp r o j e c ta n dt h ed a t a st i m es p a ni s 丘o mj a n u a r y2 0 0 2t oj u n e2 0 0 6 f i r s to f a l l t h ed e t a i l e ds t a t i s t i c so f v a r i o u sc h a r a c t e r i s t i c so f i n t e m e ta s ( a u t o n o m o u ss y s t 咖卜l 唧lm a c r o s c o p i ct o p o l o g ya n dt h ed e s c r i p t i o no ft h e e v o l u t i o no ft h en e t w o r k , o v e r a l ls m o o t ha n dt e n d i n gt oc o n n e c te v e n l y , w e r ed o n e n e c h a r a c t e r i s t i c so ft h r e ep o w e r - l a wd i s t r i b m i o u so fn e t w o r kn o d e sd e g r e ev a l u ew e r e c a l c u l a t e & b ya n a l y z i n gt h en e t w o r kt o p o l o g ye i g e n v a l u e s ，i tw a sg i v e nt h a tt h ei n t e r n e t t o p o l o g ya e n d sp l a i n l y s t a t i s t i c so ft h el i f ec y c l eo ft h en o d e sw e r ed o n ea n di t sl a w sw e r e a n a l y z e d t h ea p p l i c a t i o n so ft h ea n a l y s i sr e s u l t si ni m p r o v i n gt h ep e r f o r m a n c eo fn e t w o r k w a u s m i s s i o na n dp r e v e n t i o no f v i r u sw e l ed i s c u s s e d t h e nt h er e l a t i o n s h i pb c t g v p , c nh i e r a r c h i e so f n e t w o r kt o p o l o g ya n dt h en o d ec o f e n e s s w a sa n a l y z e d i ng r e a t e rt i m es p a no fd a t as e t , n o to n l yt h el a wo ft h ee v o l u t i o no ft h e n e t w o r ke n r e n e s sw a sa n a l y z e d , w h i c hp r o v e dt h es p do fn e t w o r ke v o l u t i o nu e n d sg e n t l y g a i n , b u ta l s ot h ec o n c l u s i o nt h a tt h em a x i m u mc o r eh a st h em o s ti m p o r t a n ti n f l u e n c ei nt h e n e t w o r k sw a sd r a w n b ya n a l y z i n gt i m e - s l i c i n gd a t a , t h el a wo fd i s t r i b u t i o n so fn o d e sa n d t h e i rl i n k sw a sg o t , w h i c hp r o v e dt h a tt h em a x i m u mc o r eh a si m p o r t a n ti n f l u e n c ea g a i nf r o m a n o t h e ra s p e c t t h en e t w o r kf a u l tp r e v e n t i o ns t r a t e g i e sf o c u s i n go i lt h em a x i m u mc o r ec a l lb e e s t a b l i s h e d ， 一卜一 东北大学硕士学位论文 a b s t l a c t 一。1 。_ - 。_ _ 。_ 。_ 。_ 。- _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ ，_ _ 一 f i n a l l yt h ef u r t h e ra n a l y s i so fn o d e sd i s t r i b u t i o na n dt h e i rc o n n e c t i n gt r a a db e t w e e n e v e r yc o r ew a sg i v e n w i 也t h es p e c i f i cf o r m u l ac a l c u l a t e db yc u r v e 肌崦，at o p o l o g ym o d e l b a s e d0 1 1i n t e r n c ta s l e v e lw a sp u tf o r w a r d 1 1 1 ee x p e r i i n e n t ss h o wt h a tc o m p a r e dw i t ht h e p r e v i o u sc l a s s i c a lm o d e l ，t h em o d e l0 1 1t h ep r e m i s eo f g u a r a n t e e i n gt h ep o w e r - l a wd i s t r i b u t i o n o fn o d e sd e g r e e ，c a nr e f l e c tt h eh i e r a r c h yt o p o l o g yo ft h ei n t e m e t t h r o u g ht h ee x p e r i m e n t s o fc o n n e c t i n gp r e f e r e n c ef o r m u l a , i ti sp r o v e dt h a tt h en e t w o r kc o r e n e s s i so fg r e a t s i g n i f i c a n c e k e y w o r d s ：a s ；i n t e m e tt o p o l o g y ；p o w e r - l a wd i s t r i b u t i o n ；t o p o l o g ym o d e l i n g ；c o r e n e s s ； n e t w o r ke v o l v e m e n t ；c o n n e c t i v i t y 一一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 动韵杠 签字e t 期：珈7 卜弓7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方 学位论文作者签名：王韵苹 签字日期 ：7 卯7 ，占f 东北大擘硕士学位论文第一章绪论 第一章绪论弟一早 三百下匕 1 1i n t e r n e t 拓扑研究的意义 i n t e m e t 作为当今人类社会信息化的标志，其规模正以指数速度高速增长，文献【1 】 的研究表明，i n t e m e t ，2 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 r n e t 已经成为人类生活不可分割的一部分。 如今i n t e r n e t 的“面貌己与其原型a r p a n 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 翻m e t 的基础。 1 2i n t e m e t 拓扑研究的现状 对i n t e m e t 的研究自i n t e r a c t 的诞生开始1 3 - 5 1 ，一直是层出不穷，经久不衰。在早期， 人们更多关注的是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 r n e t 所提供服务的安全性、q o s 、t c p 流量分析、拥塞处理、路由算法 以及拓扑建模等方面开始了新的探索和研究，并取得了相应的研究成果。特别是近几十 年来人们在复杂性科学和复杂网络等领域取得的研究成果，使国内外的研究者认识到 i n t e m e t 也是复杂网络之一，由此人们开始了从复杂性和复杂网络的角度对i n t e r n e t 的研 究。 i n t e m e t 拓扑，尤其是a s ( a u t o n o m o u ss y s t e m ，自治系统) 级拓扑，是目前研究的热 点问题。鉴于其重要性及对i n t e m e t 发展的基础性作用，国外一些大学对a s 级i n t e r n e t 的行为、模型进行了全面研究，并得到了网络运营商和设备制造商的大力支持。在近年 的i e e ei n f o c o m 和a c ms i g c o m m 上仍然是研究的热点问题，以美国的m i t ， a 1 陂t ，c a i d a ，英国剑桥大学c , d f f m 和a p n i c 的h u r o n 研究最为活跃。i r t f 成立了 r r ( r o u t i n g r e s e a r c h ) t 作组，对b g p 路由协议的设计进行全面考察，并成立了未来路由 一 一 东北大学硕士学位论文第一章绪论 协议扩展性研究小组( r r - f s ) 。 近年来人们在该领域取得了长足的进展，发现了许多隐藏在网络内部的特征规律。 但目前的相关研究工作存在或是数据统计的空间量级较小，或是数据分析时间跨度较 短，或是度量方法较为简单等问题，所以需要做更为全面的进一步研究。 1 3a s 级拓扑分析的可行性 c a i d a ( t h ec o o p e r a t i v ea s s o c i a t i o nf o ri n t e r n e td a t aa n a l y s i s ) 是一个对全球范围 i n t e r n e t 结构及数据进行研究的国际合作机构。东北大学嵌入式技术实验室经该组织授 权，成立c a i d a 中国第一节点( n e u n o d e ) ，成为该组织在中国的首家合作伙伴，共享研 究成果，并保持长期经验技术交流。n e u 节点不仅可以作为探测节点采集h t e m e t 拓扑 数据，还可以以合作者的身份，获得c a i d a 遍布全球的三十余个探测节点所提供的权 威的、海量的、更新及时的数据。无论是数据的量级、权威性、实时性等基础条件，还 是分析手段、研究深度、团队技术等科研力量，都为本课题提供坚实依靠和有效的保障。 i n t e m e t 的路由选择结构是一种层次式的选择结构，由若干路由器汇集成一个a s ， 不同a s 之间再通过边界路由器而彼此互连m 。所以，i n t e m e t 拓扑的研究工作也主要集 中在a s 级和路由级两个层面开展，是复杂网络领域研究的重点内容。根据国内外近几 年的研究重点倾向，并考虑实际分析对网络的应用价值，以及可能的计算代价，本文主 要研究工作定位于a s 级拓扑。与路由级拓扑相比，a s 级拓扑位于网络的更“上”一层， 其特征与变化对h t e m e t 的影响更为巨大，相关研究对网络未来的发展意义更为重大 同时，a s 级拓扑数据集规模小，以现有计算能力来说，可以更加有效执行深层次、高 时间复杂度的计算分析，探究更为深层次的客观特性。并且根据a s 拓扑分析的结果， 可以总结更为系统的分析策略，以及可靠的分析手段，以利进一步发现路由级拓扑中的 隐含规律，为超大规模网络统计分析提供可用手段。 考虑到i n t e m e = t 是动态变化的，其拓扑也是随时间而改变的，所以研究i n t e m e t 拓扑 的演化趋势，可以更好的了解网络的内在连接机制。而目前大多数对a s 级拓扑的研究 还集中于对静态数据上的研究，部分基于动态数据的研究选取的也是2 0 0 2 年以前较为 陈旧的数据，度量方法也较为简单，很难适应i n t e m e t 的飞速发展。由于上述因素，为 保证分析数据在时间维度上的冗余性，本文选取2 0 0 2 年1 月至2 0 0 6 年6 月的最新测量 数据进行分析，对网络特征量进行大时间跨度演化分析，观察网络生长过程中各项指标 的变化，分析其未来趋势。并且选取多种统计量进行分析，尽可能避免由于观察角度单 一而导致的特征遗漏。 - - 2 东北大学硕士学位论文 第一章绪论 i n t e r n e t 不仅具有传统意义上的局域j 一域或a s 路由层次结构，同时还体现出一种 自发的多层次的性质。以核数概念为基础，对网络的层次性做定量分析，统计并发现网 络各层之间的潜在连接规律。这不仅可以细致刻画网络特征，更加全面的描述网络拓扑， 还对网络内在连接机制的最根本问题提供了一种可能的解释方法。同时，层次特征还为 网络拓扑建模提供了一种可行的思路。 由于规模巨大，i n t e m e t 的相关研究工作( 如协议测试、病毒防御等等) 往往只能 在仿真环境下进行，因此建立可靠的i n t e r n e t 拓扑模型，是抽象分析及仿真模拟真实网 络的重要前提。现有理论模型大多只能体现网络的部分特征，但评价模型好坏的标准恰 恰就是看其是否能够符合真实网络的统计特征，因此有必要改进现有拓扑模型，使之更 好的体现网络实际性质。本文利用对已有的海量实测数据的分析结果，在经典网络增长 理论的基础上，加入对网络实际统计特征值的考虑，给出与真实网络更为贴近的拓扑模 型。通过拓扑建模的研究，还可以验证网络层次性质对于度量网络拓扑的重要性。 1 4 论文的组织结构 本文共分六章，各章的主要内容如下： 第一章为绪论部分，论述了a s 级i n t e m e t 拓扑研究的意义，以及目前a s 级i n t e m e t 拓扑研究的关键所在，强调了进行a s 级i n t e r n e t 拓扑演化分析及核数建模的意义，并 介绍了本文工作重点。 第二章介绍了i n t e m e t 拓扑研究的基本方法。首先根据网络理论和复杂网络理论， 论述了从复杂网络角度研究i n t 锄e t - ，复杂网络典型实例的基本方法，给出了从图论 角度研究i n t e r n e t 拓扑的基本概念和技巧，并给出相关概念的具体定义；然后给出了几 种经典的i n t e r a c t 拓扑建模思想，简单叙述其各自的建模过程；最后对c a i d a 项目的研 究背景进行了简介。 第三章统计了a s 级i n t e m e t 拓扑的多种宏观特征，包括网络节点数目、平均度、 最大度值等等，描述了网络的主要特性，并分析了其演化趋势。计算了a s 级i n t e m e t 拓扑的几种主要幂律分布特征，并对网络的代表性拓扑特征值进行时序分析，进一步给 出网络长时间跨度下的演化趋势。统计了网络中节点的生存时间，对节点的时效性质做 了分析。结合信息传播理论，指出拓扑演化在网络性能提高及病毒防治方面的应用j 第四章分析了拓扑图中节点核数的层次性含义，计算了a s 级i n t e r n e t 网络中与节 点核数相关的多项性质，包括节点核数与度值的关系，以及核数的演化规律。通过对时 间切片数据的计算，发现了现有网络中的核心所在，并进一步分析了网络各层节点之间 一3 一 东北大学硕士学位论文第一章绪论 的连接关系，以及各层内部的连接特性，从而对i n t e m e t 的拓扑层次相关性质给出了定 量描述。通过层次结构分析，制定网络故障预防策略。 第五章给出核数模型的建立方法。本章中考虑网络的各项宏观统计特征，结合已有 的经典网络建模理论，给出具体的建模算法。经实验分析表明，与传统模型相比，该模 型在保证网络节点度幂律分布的前提下，充分体现了网络的层次性，更加符合a s 级 i n t e m e t 拓扑的真实状况。通过对模型中优先连接概率公式的分析，验证了网络层次性 质对其拓扑形成的重要意义。 第六章为全文总结，对本文所做的工作及贡献进行了总结，并指出了进一步的研究 工作。 一4 一 东北大学硕士学位论文 第二章i n t e r n e t 拓扑研究基本方法 第二章i n t e r n e t 拓扑研究基本方法 i n t e r a c t 拓扑研究工作借鉴了大量经典理论，并在其基础上做了一定程度的延伸 本章对i n t e r a e t 拓扑特征相关的网络基本参量及拓扑研究的基本方法做了概念性的介 绍，给出几个经典拓扑建模方法的描述，并对c a i d a 数据做了简单介绍。 2 1i n t e m e t 的拓扑特征 2 1 1 网络的拓扑特征量 对于网络的研究，最早是从数学家开始的，其基本的理论就是图论。我们在复杂网 络的研究中遇到的各种类型的网络，无向的、有向的、加权的等等，这些都可以用图论 的语言和符号精确简洁地描述图论不仅为物理学家提供了描述网络的语言和研究的平 台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中目前，图论、尤其是随 机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一睁蠲因此， 了解图论中基本概念及符号，将帮助加速复杂网络研究过程和理解复杂网络研究成果。 本文下面对其重点概念进行简单介绍f 廿1 4 l 。t 【定义2 1 】图( g r a p h ) ：一个图g 是一个三元组，这个三元组包括一个顶点集v ( 6 3 ， 一个边集耳回和一个关系，该关系使得每一条边和两个顶点( 不一定是不同的点) 相关 联，并将这两个顶点称为这条边的端点 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上边，本文所讨论的图， 均符合上述要求，即均为不含多重边的图。 。 直径、平均距离、聚集系数等参数的取值以及顶点度分布的性质的实证研究，是复 杂网络领域最早的研究内容之一，尤其针对某些真实的复杂网络实例，如演员网、科学 家网等，对上述若干概念所进行的深入研究及成果，成为后续的大量研究的基础，因此 有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地 理解当前复杂网络研究的物理意义。 网络一词是社会学家斯梅尔( gs i m m e l ) 在1 9 2 2 年不经意创造的，这个词汇在自然 科学和社会科学领域中使用得如此频繁，以至于该词已成为社会网络i 巧1 分析方法的主导 词汇；而且在今天的自然科学中，网络研究也成为重要课题。今天的社会已经成为网络 的社会，人们的同常生活已经无法离开网络，如电视网络、i n t e r n e t 、电力网络等。网络 一5 一 东北大学硕士学位论文 第二章i n t e r n e t 拓扑研究基本方法 是一个由许多节点及连接节点的边组成的集合，其中节点用来代表真实系统中不同的个 体，而边则用来表示个体闯的关系，如果两个节点之间具有某种特定的关系则认为有边 相连。 【定义2 2 】网络( n e t w o r k ) ：称n - ，e ，c ，x ，y ) 为一个网络，如果 ( 1 ) g - ，e ) 是一个有向图； ， ( 2 ) c 是e 上正整数，称为容量函数，对于每条边e ，c 纠称为边e 的容量； ( 3 谬与y 是v 的两个非空不相交子集，分别称为g 的发点集与收点集， i - ( xl xu y ) 称为是e 的中间点集，x 的顶点称为发点( 源) ，l ，的顶点称为收点( 汇) ， j 的顶点称为中间点。 在图论中网络g 以e ) 是指由点集h g ) 和边集e ( g ) 组成的图，且联g ) 中的每条边 自有瞪 中的一对点m ，d 与之对应记顶点数为一吲，边数为三- i e i 如果任意 ，力 与( v ，) 对应同一条边，则称为无向网络，否则为有向网络【1 6 l ；如果任意k i 一1 则称为无 权网络，否则为加权网络 在统计物理学中把网络看成包含大量个体以及个体之间相互作用的系统，是把某种 现象或某类关系抽象为个体( 节点) 以及个体之问相互作用抽象成边而形成的图 【定义2 3 1 度e g r e e ) ：设是一个网络，k 叼是所有项点的集合，风的是所有边 的集合顶点1 ，的度k ，是指与此顶点 ，连接的边的数量， ，y 即 扣荟 ( 2 1 ) 其中，当边1 包含顶点y ，掣取值为1 ，否则为零，即 小f 多二v 度值的分布特征是网络的重要几何性质【协埘规则网络各节点的度值相同，符合d 分布；随机网络符合泊松分布；无尺度网络存在幂律形式的度分布；也有的网络废分布 为高斯型 【定义2 4 1 度分布( d e 掣d i s t r i b u t i o n ) ：对于无向图g ，e ) ，记度为七的顶点数 目为雕) ，则p 皓) 一嚣嚣给出了图g 的顶点度分布 关于复杂网络拓扑图中项点度分布常使用幂律形式的分布函数研究，如 f r e q u e n c y - d e g r e e 幂律分布、d e g r e e - r a n k 幂律分布、e i g e n v a h e r a n k 幂律分布以及 c c d f ( d ) - d e g r e e 幂律分布等【烈啦这将在本文后面进行详细介绍。 东北大学硕士学位论文第二章i n t e r n e t 拓扑研究基本方法 在网络拓扑图中，聚集系数：l ：c l u s t e rc o c 仿d e n t ) 是衡量网络节点的成团特性的参数， 一般可用来表示节点的集聚程度，节点的聚集系数及图聚集系数的数学描述形式如式 ( 2 3 ) 与式( 2 4 ) 所示。 【定义2 5 】聚集系数；图的聚集系数是衡量图的成团特性的参数。对于无向图 g ，e ) ，记某顶点x 的邻点集合为彳 ) ，显然d o ) - 4 a ( x i l ，顶点工的聚集系数被定义 为它所有相邻节点之问连边的数目占可能的最大连边数目的比例，即： 洲一粼 。 图g 的聚集系数则被定义为所有顶点聚集系数的平均值： c ( g ) l 志薹c 口o ) ( 2 4 ) 【定义2 6 1 最短路径( s h o r t e s tl a t h ) ：最短路径定义为节点i 和，之间的所有通 路中，经过的顶点数最少的一条或几条路径记节点f 和，之闯最短路径的集合为毛， 则相应的路径长度为如- b l 如果节点i 和j 之间不存在通路，那么记如- 为网络 中的节点数) 网络中所有节点之间的最短路径可表示为矩阵p 口) 舢，其分布特征是网。 络的一个重要的几何特征量，平均值称为平均最短路径d 【定义2 7 1 小世界效应f s m a nw b de f f e c t ) ：网络中节点数变化时，任意两节 点间的最短平均距离变化相对缓慢，大致随节点数增加呈对数增长，且网络具有较高的 聚集系数特征的现象称为小世界效应 ， 【定义2 8 】无尺度特性( s c a l e f r e e p r o p e r t y ) - 网络中的节点度服从幂律分布， 也就是说有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似 地表示，这种节点度的幂律分布为无尺度特性1 2 0 l 。 【定义2 9 1 富人俱乐部( r i c h - c l u b ) ：i n t e m e t 中有少量的节点具有大量的边，这些 节点被称为“富节点( r i c hn o d e s ) 。这些富节点们倾向于彼此之问相互连接，构成“富人 俱乐部” 【定义2 1 0 1 富人俱乐部连通性( r i c h - c l u bc o n n e c t i v i t y ) 可以用富人俱乐部连能 性e p ( r n ) 来刻画富人俱乐部现象，它表示的是网络中前，个度最大的节点之间，实际 存在的边数l 与这r 个节点之间总的可能存在的边数r ( ，一1 ) 2 的比值，即： 面, ( r u ) 一石l 丽一而2 l ( 2 5 ) 如果m ( ，) - 1 ，那么前，个最富的节点组成的富人俱乐部为一个完全连通的子图。 - - 7 - - 东北大学硕士学位论文 第二章i n t c r n e t 拓扑研究基本方法 【定义2 1 1 1k - 核( k - c o r e ) ：图的七核是指反复去掉度值不大于七的节点及与其连 接的边，所余下的子图。七值越大，则该核越深。本文称孟值相对较小的。b 核为低核， 反之为高核，七值最大的b 核被称为最高核【2 1 1 。 【定义2 1 2 】核数( c o r e n e s s ) ：节点核数表示包含该节点的最深的核，即指若节点 核数为七，则该节点存在于缸核中，而不存在于( h 1 ) 核中。图中节点核数的最大值为该 图的核数，同时该值也为最高核的七值1 2 i i 。 网络的b 核以及核数的相关性质可以说明其拓扑由核心节点至外围节点的层次结 构。值得注意的是，本文所指的层次结构是拓扑意义上的，而不是指广域网，局域网层次 结构或者服务供应商客户层次结构 2 1 2i n t e m e t 的复杂性 可以把i n t e r a c t l ) 看作是一个开放的、远离平衡态的系纠珥嘲人类缔造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 r n e t 与外界环境之间发生物质、能量和信息交换的表现。 据统计目前的i n t e r a c t 由1 0 0 多万个各式各样和宏观拓扑结构的网络组成，这些网络连 接了1 亿多台异构计算机i n t e r n e t 上每天新增的网页超过1 0 0 万个，而这些网页又通 过数l o 亿个超链接时空交互她连接在一起由此可见，i n t e r a c t 已经成为一个包含大量 子系统的分布式、不协作的异构系统i n t e r n e t 行为的复杂多重性，表现为网络流量的 长程相关性、重尾( 1 0 n gt a i l ) 分布规律、自相似性、分形和多维分形以及混沌现象等行为 特征频繁被访问的一些网页或节点将以更高的频率连接到其它网页或节点上。自组织 出现网页本地聚簇效应。这些聚簇实时演化成为i n t e r n e t 的子系统 虽然其在a s 级和路由级可得到两个不同的拓扑，但无论哪一种拓扑度分布都服从 幂律从a s 层次上看，a s 为节点，两个a s 边界路由器间的一个或多个连接作为一条 边；在路由器层，节点是路由器，边是对路由器之间的物理连接。本文的研究就是基于 i n t e m e t 的a s 级拓扑开展研究的。大量的研究发现，在a s 级i n t e r n e t 的拓扑结构呈现 出无尺度特征i 嬲l ，i n t e r n e t 是个高度连接的复杂网络，它的典型特性，包括开放性、 层次性和演化鲫性都充分显示了其开放复杂巨系统( o c g s ) 的本质 2 2 i n t e r a c t 的拓扑结构模型 ， i n t e r a c t 是个典型的复杂网络，近年来针对i n t e m e t 拓扑结构而提出了多种网络模 一8 一 东北大学硕士学位论文第二章i n t e r a c t 拓扑研究基本方法 型，这些模型也称为i n t e r a c t 拓扑产生器1 2 9 1 i n t e r a c t 拓扑建模是一项复杂的工作，涉及 网络测量、图论、算法设计、统计学、数据挖掘、可视化以及数学建模等多个研究领域。 正是由于其复杂性及高难度，吸引了大量专家在此领域展开研究。至今为止，i n t c r n e t 拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂系统特征化研 究的过程，大体上可按时间顺序分为三代【辑删： 第一代为2 0 世纪踯年代的随机图产生器【3 n ，在研究早期，由于缺乏真实测量数据 支持，拓扑模型都是研究人员基于经验假设建立的；第二代为2 d 世纪9 0 年代的结构产 生器，如啊e i s ( 等级) 模型阎与t r a n s i t s t u b 模型f 3 3 堤明显的基于层次结构设计思想的两 类拓扑生成器：第三代始于1 9 9 9 年，f a l o u t s ( m 等人发现i n t e r a c t 拓扑结构中存在幂律 ( p o w e r - l a w ) 1 2 0 1 ，从而产生基于网络节点度的拓扑模型与拓扑产生器 这些拓扑生成算法及拓扑产生器为i n t e r a c t 模拟提供了有利的支持不过，现有理 论模型大多只能体现网络的部分特征但新的研究总是建立在已有研究成果的基础之 上，充分吸收已有经验及设计思想，解决现有模型问题，才能提出更优秀的模型1 3 4 3 5 1 因此本文下面就上述部分典型的拓扑模型及算法进行概述。 2 2 1 随机图模型 1 9 8 8 年w a x m a n 提出的随机图模型及产生器p 1 】较好地再现了a p a r n e t 网络，其 建模步骤如表2 1 所示： 表2 1w a x m a n 随机图模型建模过程 t a b l e2 1 m o d e u n gp t o c e d u r eo f w a x m a nr a n d o mg r a p h 步骤操作内容 ( 1 ) ( 2 ) 在a x | l 的平面上均匀放置个节点； 两节点“和y 之间建立边的概率为：n ( u ，d a e 。i - ) 7 皿，其中0 a ，墨1 。 d 钕，y ) 是节点# 和v 之闻的欧氏距离，4 为平均连接度。是图中相距最远的两 节点间的欧氏距离，决定了边的平均长度。如果4 增大，则边的生成概率0 ，d 增大使得最后生成的图中边的数目增加；如果，增加，则使得最后生成的图中 较长的边相对于较短的边出现的概率增加 w a x m a n 图中相距较远的两节点问存在边的可能性较小，从而获得连通图的可能性 也比较小，通常用来对网络中的最大连通子图进行研究。w a x m a n 产生器是随机图产生 器的典型代表，后来很多随机图模型都受其启发【3 2 1 一9 一 东北大学硕士学位论文第二幸i n t e r n e t 拓扑研究基本方法 2 2 2i n e t 模型 1 9 9 9 年f a l o u t s o s 等人发现i n t e r a c t 拓扑结构中存在幂律w * l a w ) 【驯后，i n t e m e t 拓扑模型及生成器进入一个新阶段为反映i n t e m e t 的拓扑特性，尤其是连接度的幂律 分布特性，2 0 0 0 年美国m i c h i g a n 大学研究人员提出拓扑生成器l n e t 3 6 1 。其建模过程如 表2 2 所示 2 9 , 3 7 1 ，l n e t 可用于产生不少于3 0 3 7 个节点的网络，这是1 9 9 7 年1 1 月i n t e r a c t 上a s 的数目 表2 2l n e t 生成器模型建模过程 t a b l e 2 2 m o d e l i n g 珥| i l m o f l n e t t o p o l o g y 伽咀髓m d “ 步骤操作内容 ( 1 )获取节点个数及个节点中度为1 的节点所占比例耘 c 2 )根据式一e x p ( 0 0 2 9 8 t + 7 9 8 4 2 ) i l - l i i n t e r n e t 从1 9 9 7 年1 1 月份的节点个数增 长到所需时间月份) ( 3 )定义巧、和矿；巧是度为1 的节点的集合，是前三个最大度的节点集合， 矿为除去n 、圪椰中节点以外的其他节点； ( 4 ) 代入“根据f ( d ) - e d 4 “计算矿中节点的度分布，其中f ) t ，o ) ，。、 b 、c 为已知常数i n t e r a c t 度为1 的节点所占比例基本上维持在3 0 左右根据 d c 孕m n k 指数增长律d 口，+ f ，。计算，中节点的度分布，p 、覃为已知常数； ( 5 ) 在度大于1 的节点间构建一个生成树：令g 为所要产生的图初始为空集；不在 g 中的度大于l 的节点f 与g 中的一个节点，相连的概率为：n g ，) - 叫罗计， 屈 ，吨为节点度f 的度，( 噍) 为 按概率计算公式o ，) 一 一罗衅，将n 中的t 个节点连接到g 中的节点上； 屈 从具有最大度的节点开始。连接g 中仍剩余的自由度；在进行这些连接时，以概 率式g ，) 一w ，w ；随机选取有自由度的节点。 彪 一1 0 一 n ， m小 撼 中 的 其 度 东北大学硕士学位论文 第二幸i n t e r n e t 拓扑研究基本方法 2 2 3p f p 模型 a s 级i u t e m e t 存在“富人俱乐部”现象，正反馈优先( p o s i t i v ef e e d b a c kp r e f e r e n t i a l ，p f p ) 模型正是在研究此现象的基础上提出的 2 9 , 3 9 。p f p 模型是基于新节点和内部边这两个方 面的交互增长、非线性优先连接两个机理构建的。每一步除了将新节点连接到已存在的 h o s t 节点上，还会将该h o s t 节点连接到其他已存在的节点上，从而产生内部边。当选择 所要连接的已存在节点时，采用非线性优先连接概率。其建模过程如表2 3 所示。 表2 3p f p 模型建模过程 t a b l e2 3 m o d e l i n gp r o c e d u r eo f p f pm o d e l 步骤 操作内容 ( 1 ) ( 2 ) 通过m o - i 条边，将个孤立节点连接起来，每一步执行- f 面( 2 x 3 ) ( 4 ) 三个步骤中 的一个