（计算机软件与理论专业论文）internet拓扑结构研究及在im网络建模中的应用.pdf

i n t e r n e t 拓扑结构珂f 究及在l m 网络建模中的应用 摘要 随着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 是一个无尺度网络，它具有小世界特性，并具 有一种松散的层次结构。现有的网络拓扑模型主要分为随机型，演化型，层次型 三类。通过对现有的几种比较经典的网络拓扑模型进行深入的研究和分析之后发 现，每一种模型都是突出表现网络拓扑特征的一两个方面，而不能较完整的描述 网络的所有特征。 本文对现有的一种演化型模型g b a 模型进行了三次改进，并加入层次型的 思想，提出一种新的i n t c m e t 拓扑模型c l i q u e v g b a 模型。第一步，针对g b a 模型考虑网络演化过程中事件的不完备性，新模型将其进行扩充，把重连事件分 解为去边和加边两种事件。第二步，通过对实际数据的分析发现，去边事件对小 度数节点具有偏好性，新模型将这种”优先断开”的思想形式化后引入网络的演化 规则当中。第三步，新模型提出子网( c l i q u e ) 的概念，在演化型模型的基础上 与层次型模型相结合，最终形成了c l j q u e v g b a 模型。 对模型进行数学处理后，将得到的平均聚集程度，平均最短路径，度分布指 数等拓扑度量在实际1 1 1 t e m e t 上采集的数据进行验证，并与现有几种经典模型e r 模型，b a 模型，g b a 模型相比较。从得出的结果中可知，a i q u e - v g b a 模型确 实较完整的描述了网络的大规模拓扑特征，并且对于每一种特征的描述都优于其 它模型。 i m 网络是i n t e m e t 上的虚拟社会网络，因此它不但表现出与i n t c m e t 相似的 统计学特征，也是一种社会关系网络。对i m 网络进行拓扑建模，对分析和研究 其安全性有很大的指导意义。本文将c l i q u e v g b a 模型应用于l m 网络中，针对 其具体特征，对新模型拓扑度量的分析也进行适应性的调整。最后文章从拓扑结 构角度对i n t e r n e t 与i m 网络的安全性进行了分析，并提出一些安全策略建议。 关键词：，拓扑结构，i n t e r n e l 拓扑建f ：| ，i m 例络，安全叶 i n l e m c t 拓扑纳构研究及在i m 网络建模中的应用 a b s t r a c t a st h eb a s i so fi n t e m e ld e v e l o p m e n ta n de x p l o i t a t i o no nh i g h e rl e v e 】s ，t h e i n t e m e tt o p 0 1 0 9 ym o d e l i n gc a nb eu s e dt oa n a l y z et h ei n t e m e t sl a r g e - s c a l et o p o l o g y ， a n df b r e c a s io rc o n t i n ln e t w o r k i sb e h a v i o r s t h ei n t e m e “sas c a l e - f r e e ，s m a l l w o r l dn e t w o f k ，w h i c hh a v eal o o s eh i e f a r c l l i c a l s i r i l c t u r e t h ei n t c m c lt o p o i o g y m o d e l i n gs t a n s 鼬t h cr a i l d o mm o d e lt o t h e h i e i a r c h j c a lm o d e l ，t h 蜘t ot h ee v o l u t i o nm o d e l a n e fr e a r c h e dd e e p l ym a n yc u r n t c l 觞s i c a lt o p o i d g ym o d e l s ，t h i sp a p e rf i n d st h a t 卸y o 雠渤o n l yd e s c 曲ep a i i so ft h e n e t w o r k s lt o p o l o g yc ：h a m d e r am wh i t e m e tt o p o l o g y m o d e l c l i q u e - v g b am o d e l i sp r 船e l l t c dw h i c h 砌c l i o r a t ct h ec u r r e mg b am o d e l 恤r e et i i n 鹤弛t l y t h en e wm o d e lt a k e si n t o a c c 0 强to fa d d i n ge d g 髂a n dd e l c t i n ge d g e si nt h ee v o l v 矗l gn e 柳o d 疆t oa m 蛐dg b a m o d e l s e c o n d l y ，n i d e ao f ”p r e f c n t i a lc u t ”i si n t 加d u dt on e wm o d c l ，b e c a 惦c d e l e t i n ge d g c sm o mh a p p e n st on o d e sw i ml c 姆d e g m c f i n a l i y n c wm o d dc o m b i s t h ch i e r 盯c h i c a lm o d e l 柚dt h e “o l u l i o nm o d e l t oa c o o m p l i s ha i q u c v g b am o d e l m 姐yc h a r a c t e r i s t i c so ft o p o l o g ya r c 船a l y z e dw i l ht h cc o r r 鹤p o n d i n gm c t r i c s ， i n c l u d j n gc l i q u e - v g b an i o d c l t sp ( n e rl a we x p o n 吼t ， s h o n e s tp a t h ，c l u s t c f i n g e 蚯d e n t t h e nt h e s em e t r i c s 盯ev a l i l d a t c di nm a l i s t i cd a t ao ft h ei n t e m c t a n d m p a f e dw i t hl h ee rm o d e l ，b am o d e l ，a n dg b am o d e l n ea n a l y s i ss h d w st h e n e wm o d e lc 强d e s c r i b et h ei i l l e m e t f st o p d l o g yc h 啪d c rm o r em a t u r c i yt h a nt h co t h 盯 m o d e l s 1 r h ei mn e m o r ki sav i n u l la n ds o c i a ln e 伽o r ki nt h ei n t e m e l ，w h i c h to n l y s h o w st h ei n t e m e t ss t a t i s t i c a lc h a f t e r ，b u ta l s oi sas o c i a in e t w o r k t h i sp a p e r a p p l j e st h ec “q u e v g b am o d e l t ot h ei mn e t w o f k ，a n da n a l y z e si t sp e c u l j a rm e i r i c s ， s u c ha st h eb e t w e e n n e s s ，i n - d e g r e ed j s t r i b u t i o n ，o u t - d e g r c ed i s t r i b u t j o n ，a n ds oo n f u f t h e r m o r e ，t h ep a p e ra n a l y z c st h es e c u r i t yo ft h ei mn e l w o r ka n dp r c s e n t ss o m e e f f e c c u a ls e c u r i i ys i r a t e g j e s k e y w o r d s ： c 【 p t ) l o g i c a ls t r u c t u r e ；i n i e r n e lt o p o l o g ym o d c l i n g ；t h cl mn e l w o r k ：s e c ur j t y y9 7 6 l 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切 法律责任和法律后果，特此郑重声明。 学位论文作者：b 彬1 虱图 御6 年笋月狁日 i n t e m e t 拓扑结构研究鼓在1 m 刚络建模中的应用 第一章引言 i n t e m e t 作为当今人类社会信息化的标志，其规模正以指数速度高速增长。依 其高度的复杂性，可以将其看作一个由计算机构成的“生态系统”。i n t e r n e l 拓扑建 模研究就是探求这个看似混乱的网络之中蕴含着哪些还不为我们所知的规律。发 现i n t e r n e t 拓扑的内在机制是认识i n t e m e t 的必然过程，是在更高层次上开发利用 i n l 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 的3 个组成部分，即在拓扑网络中节点间执行协议，形成流量。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 拓扑建模的需求至少有以下几个方面【1 】： ( 1 ) 许多新应用或实验不适合直接应用于i n t e r n e t ，其中一些具有危害性，如 蠕虫病毒在大规模网络上的传播模拟； ( 2 ) 对于一些依赖于网络拓扑的协议( 如多播协议) ，在其研发阶段，当前 i n t e r n e t 拓扑只能提供一份测试样本，无法对协议进行全面评估，需要提供多个模 拟拓扑环境来进行实验； ( 3 ) 从国家安全角度考虑，需要在线控制网络行为，使国家对网络管理更具宏 观控制力。如美国国防高级研究计划局( d a r p a ) 的n m s ( n e t w o r k m o d e l j n ga n d s i m u l a t j o n ) 项目： ( 4 ) 分析病毒在网络上的传播模式，研究病毒对抗或预警方式，防范大规模 刚络攻击，同时为信息攻击对抗提供必要的网络测绘和流量分忻i ( 5 ) 为仿真模拟i n t e m e t 环境协议设计与评价以及z 力态网络仃沂阽分析提供 驯究j l 为l n l e r n e t 流量：f 程( 1 r a f f i ce n g i n e e r i n g ) 利刚络仃为。节( n c l w o r kb e h a v i o f ) 的川“傩“j 助依据及验证平台。 i n l e m e t 拓扑结构研究及在i m 刚络建模中的应用 h l t e 加e t 拓扑建模是一项复杂的工作，涉及网络测量、图沦、算法设计、统 计学、数据挖掘、可视化以及数学建模等多个研究领域。i n t e m e t 拓扑建模研究 内容可归结为3 个问题【1 】： ( 1 ) 拓扑结构测量l ，即如何获得一份完整而准确的i n c e f n e t 拓扑数据，属 网络测量范畴； ( 2 ) 拓扑特征发现，即如何对i n t e f n e t 网络拓扑特征进行描述； ( 3 ) 拓扑生成算法构造，即如何构造一幅类似于实际i i l t e m e t 的拓扑图。 本文按如下方式组织内容：第二章总结了i n t e m e t 的大规模拓扑特征，并给出 几个常用的拓扑度量的定义；第三章从静态随机图，演化型模型以及层次性模型 三方面介绍了几种经典的i n t e m e t 拓扑模型；第四章对演化型g b a 模型进行三次 改进，提出自己的一种拓扑模型c l i q u e v g b a 模型，并且根据实测的i n t e m e t 数据 对该模型进行验证；第五章将模型应用于一个i n t e m e t 上的虚拟社会网络i m 网络： 文章最后从拓扑结构的角度对i m 网络的安全性进行了分析。 i 呲e m e t 拓扑结构研究投在i m 网络建模中的应用 第二章i n t e r n e t 大规模拓扑特征 2 1i n t e l l l e t 拓扑图与拓扑度量 g = ( v ，e ) 作为图论的概念是指由一个点集v ( g ) 和一个边集e ( g ) 组成的一 个图，且e ( g ) 中的每条边e i 有v ( g ) 的一对点( u ，v ) 与之对应。如果任意( u ，v ) 与( v ， u ) 对应同一条边，则称为无向网络，否则为有向网络；如果任意ie j i _ 1 ，则称 为无权网络，否则为加权网络i ”。 i n t e m e t 拓扑通常进行形式化为无向图g ，g = ( v ，e ) ，其中v = v l v 是g 中的 一个节点 ，e = ( u ，v ) i u ，v v 且u ，v 相邻接) ，g 数学表示为邻接矩阵m 。设d ，表示 节点v 的出度，d ，= i u i ( u ，v ) e ，l 。设f d 表示节点出度频率，fd = i v i v v 且d ，= d 1 1 】 i n t e m e t 可以分解成相互连接的若干个子网，每个子网具有独立的管理机构， 当然也具有独立的路由政策，这样的子网称为自治系统( a u t o n o m o u ss y s t c m ) ， 简称a s 。这样就得到了构造互联网拓扑结构图的两种方法【3 ”】：1 1 将互联网中 的路由器看成图的结点，如此得到的图称为路由器级图，简称i r 级图( 图2 1 ) ； 2 ) 将每个自治系统看成一个结点，而将自治系统之间的连接看成边，如此得到 的图称为自治系统层上的图，简称a s 级图。通常对i n t e m e t 拓扑结构的研究工作 均是针对上述两类图来进行的，实际上a s 级图是i r 级图的一个紧缩。 | 冬| 2 1 魁 个i r 级削的局部 米自丁h a lb u r c ha n db i l lc h c s w i c k f n l n 【e r n e l 绘l 引1 平l l ( h t i p ：，w w 、v 1 u m e t ac 。m ) 下而对几个常川的抖i 扑迈j l 作卜i 划9 j ： l n i e r n e t 拓扑结构研究及在i m 网络建模中的应用 定义1 顶点的度指与此顶点连接的边的数量，即： t2 荟6 j ( 2 1 1 ) 其中e 为边集，若顶点f 包含在边z 的顶点中，则6 j = 1 ；否则，6 - o 。 定义2 平均最短路径( d 是矩阵( d q ) n 。n 的分稚特征值的平均值。其中，d o = l ， _ 表示两点间的最短距离，n 表示点集。两点的最短路径li j 定义为所有连通( i ，j ) 的通路中，所经过的其他顶点最少的一条或几条路径。记( i ，j ) 之间最短路径的 集合为su ，相应的路径长度为幽= i z f “。如果r f ，j 之间不存在通跷那么记 由= 。于是我们可以得到的矩阵f d ，州。 定义3 聚集程度的意义是网络集团化的程度考察连接在一起的集团各自的 近邻之中有多少是共同的近邻。即： 铲k 蠢即吵q ( 2 z ) 其中m 表示顶点的近邻集合，n = l ji 。实际上c r 是一个比率，是f 的最近邻之 间边的数量与最近邻之间可能的边的总数之比。所有顶点的集聚程度的统计分布 是刻画网络的一个重要几何量其平均值称为平均集聚程度c ： 砸) = 志罩q ( 2 _ 3 ) 定义4 介数饵e 伽e e 蛐e s s ) ：顶点“的介数含义为网络中所有的最短路径之中， 经过“的数量。它反映了顶点“的影响力。记r f ，) 之间虽短路径的集合为s 驴， 顶点“的介数定义为： v 鸭6 7 2 刍下r ( 2 4 ) 平均介数定义为： 耻) = 赢；4 d ： s ) 类似地可以定义边的介数，边的介数i f 以肝j 卜分t ；_ 顶点的聚类。其基本思想 址1 ，| ：也禽不同集团的网络中所有最短路径经过次数城多的边，山就是介数最大的 也，必然址联接曲个集团之问的边。 i n i e m e i 拓扑结构研究及在i m 网络建模中的应用 定义5 度相关性： k ( 七) 2 善御( 七i 七) ( 2 6 ) 其中尸伍7 纠是表示度数为k 的一个节点与度数为k7 的节点相连的概率。 令k 点为该节点的邻节点，该度量的意义就是度数为k 的节点的最近邻节点的平 均度数。如果不存在度相关性( 如不相关的随机网络) ，那末k 。( 七) 独立于k 。 定义6 增长概率： 丌( 七f ) = 6 鼻6 七 ( 2 7 ) 其中d 女为在一个时间片r 内增加的边的总数。这样比率6 k ，d k 就被定义为一 条新边连接到点i 的概率。 k ：表示在r 时刻，第s 点的度数。 p 以f ) ：在时间，一个节点的度数为 的概率。 2 2 小世界性质 1 9 6 7 年，美国的一位心理学家米尔格伦提出了他著名的“六级分离”( s i x d e 乎e e so fs e p a r a t i o n ) 的理论，该理论描述了一个神奇的小世界。他认为，任何 两个陌生人都可以通过“亲友的亲友”建立联系，而这两个人之间的亲友数量大约 是5 。而研究者对在i n t e m e t 中测量出的数据进行分析时发现，无论是a s 级图， 还是i r 级图中都存在节点间的最短路径相对于图的规模来说非常小的现象。节 点对之间的最短路径的概率在其平均值上形成了一个峰值，并在峰值两边迅速的 降低，因而平均最短路径长可以看作网络的特征长。在i r ( a s ) 级图中，9 7 的点 对的最短路径都是1 5 ( 8 1 或者更小【6 l 。这种现象正好符合了小世界性质，简单的 描述就是在系统中从一个点出发到另一个任意点只需要经过很少数量的中间点。 i n t e m e t 的小世界性质是如何形成的昵? 研究者w a t t 和s t r o g a t z1 7 1 发现，小 世界网络是种介于规则网络和随机网络【8 】的网络结构，只需要在规则网络上稍 作随机改动就r - j 以同时具备高集聚程度和小最短路径两个性质。舰则网络是指平 移对称性品格，仟何一个格点的近邻数目都相同。一维链，：绯l ：方品格等都为 规则刚络。f 5 f i 机刚络是个顶点构成的图中，可以存在c 二。祭边，从- ，随机 连接m 餐边 = j l j 成的m 络姚叫随机刚络。还有一种乍成随 l ic q ! 舢1 山浊址，刈 i n l e m e t 拓扑结构研究及在l m 叫络建棱中的应用 于c 2 n 中任何一个点对，都以概率p 的连接。令m = p c 2 n ，g a 力则与g 等价。 规则网络的特征是平均集聚程度高而平均最短路径长，随机网络的特缸是 平均集聚程度低丽平均最短路径小。规则网络的平均最短路径d n ，而其集 聚程度可以通过改变近邻数目h 来调整例如在图2 2 所示的规则网络中k o = 4 ， 集聚程度分别为0 5 。而在随机网络中，平均集聚程度非常的小，在图2 2 阳l 的随 机网络中，顶点数与边数都与规则网络相同，但集聚程度为a 0 2 。正是由于其集 聚程度非常小，所以其平均最短距离小。考察一个顶点u 的近邻，假设其近邻数 为a ，那么在a 个近邻的近邻之中相互重复的个数非常少，所以从u 出发经过两 次近邻关系我们可以找到正比于a 的新顶点，最多经过l o g a n 个近邻关系，就可以 穷尽整个网络。所以，其最短路径满足d l r l 。可见对于规则网络，也正是由 于其集聚程度高，重复率大，所以平均最短路径大。 r 鐾叫a r s m 日w p n d r 4 n d o m o 桊 p d + p 。， 图2 2 规则网络，随机网络与小世界网络 对上面两个网络进行改动，使其形成同时具有高集聚程度，小最短路径的 小世界网络，方法如下：对于规则网络的每一个顶点的所有边，以概率p 断开一 个端点，并重新连接，连接的新的端点从网络中的其他顶点晕随机选择，如果所 选的顶点已经与此顶点相连，则再随机选择别的顶点来重连。当p = 0 时就是规则 网络，p = l 则为随机网络，在0 印 1 很大的区域，同时捐j 有较大的集聚程度和较 小的最短路径，这就是小世界网络。一。个典型的小世界网络见图2 2 中问的示意 图。 2 3 无尺度网络 自从1 9 5 9 年匈牙利数，、# 彖er d o s 干r e n v i 提随机网络m 1 1 ，1 2 】之后的4 0 个 早，科学家惯刊哿所仃复杂f t q ，hr i f l 。址 【嗍络。1 9 9 8 年a l b e r l l a s z l o b a r 曲j i n t e m e i 拓扑结构研究及曲：i m 嘲络建模中的应用 和e r i cb o n a b e a u 与美国圣母大学的郑夏雄及a l b e r t 合作丌展一个描绘万维网的 项目【1 3 】时，本以为会发现一个随机网络，然而实测结果却推翻了这个预测。研究 发现，基本上，万维网是由少数高连结性的页面串连起来的，8 0 以上页面的连 结数不到4 个。然而只占节点总数不到万分之一的极少数节点，却有1 0 0 0 个以 上的连结，这样的节点称为集散节点。 在计算恰好拥有k 个连结的万维网页面的数目时，发现网页的链按分布 【“1 5 1 6 】遵循幂律t ( 幂律是指形如1 ，矿的方程，对于两个变量彳和n 存在一 个常数c ，使得y 与x 的c 次幂成比例) 形式：任何节点与其他k 个节点相链接 的概率，与l l 【成正比。幂次定律不像钟形曲线那样具有一个峰值，而是由连续递 减的函数来描述。如果用双对数坐标系来描述幂次定律，得到的是一条直线( 见 图2 3 ) 。与随机网络中连结的民主分布不同，幂次定律所描述的，是由少数集散 节点所主控的系统。 节盎釜结i 赫豫曲缝甜它苇点巷结彀的幂浚筮栩 特箝 蒜瞎靛 淳纬赫蓬鼎数r 勰戢鳖撑 图2 3 左图为随机网络的度分布图，右图为无尺度网络度分布图 f a l o u t s o s ( 1 9 9 9 ) 第一次指出l r ，a s 图的概率分布接近于幂指数规律1 1 7 j 。图 2 4 左给出了i r 图中任意给定点的度k 的概率p ( k ) 。度分布于三个数量级之问。这 种现象也可以称作度分布的“重尾( h e a v y t a i l ) ”现象。图2 4 右给出对数坐标的 a s 图三年的积累度概率分布。从这两个图可以看出，度的分布非常的稳定，近 似于一条直线，可以用幂指数形式表达为：p ( k ) k _ r ，其中r 2 2 。 i n i c r n 酣拓扑结构研究及在i m 网络建模中的应用 关于度分布的重尾现象说明系统的平均行为并不是典型行为。特征度数通 常指随机抽取点时最常遇到的点的度数。但是在1 r 图和a s 图中各个不同度数的 点抽取到的可能性差不多，因而平均度数( k ) 没有任何特殊意义。当度分布指 数在2 ( k ) 的网络称为无尺 度网络。k 是个对网络受度分布影响的所有性质和物理过程的关键参数。 f a l o u t s o s 等人对n l a i n r ( n a t i o n a ll a bf o ra p p i i e dn e m o r kr e s e a r c h ) 在1 9 9 7 1 9 9 8 年间的3 份b g p 数据以及1 9 9 5 年的一份测量数据进行分析后，发现 i n t e m e t 拓扑中存在着4 条幂律2 1 。 两个声明：( 1 ) 节点v 的等级为r v ，v 是在按度数降序排列序列中的索引值， 也就是v 的度数；( 2 ) 邻接矩阵特征值按降序排列，第i 个特征值为k 。 幂律1 ( 等级指数r ) ：节点出度以与该节点等级r ，的r 次幂成比例， d 。“。 幂律2 ( 出度指数o ) ：出度频率彤与该出度d 的。次幂成比例，厂d o cd o 。 近似幂律( h o p p l o t 指数忉：跳步数小于等于 的结点对的数量与 的月次幂 成比例，j p r jo ( “。 幂 b 4 ( 特征指数e ) ：特征值h 与其次序f 的次幂j 戊比例，i ，o cf 。 雅律l 税l w n i n l e r n e ir f ，既不存在随机网络那样的一f 等”，山i _ 二l 等级森 严”址i i 仃干l i i 桧敞的层次陀。幂律l 和幂律2 反f 叭这此系统j 【仃离迂m 均 i n l e m c t 拓扑鲒构研究及枉i m 网络建模中的戚用 一性，即少数节点具有很高的度数，而大量节点具有较小的度数，直接否定了随 机网络模型中节点分布规律。近似幂律中的h o p p l o t 指数删以用来对拓扑图进 行分类，例如，对于环，h = 1 ；对于二维网格月= 2 。对于i n l e r n e ，在a s 级上，冉蝇4 7 ， 在i r 级上，h 。2 8 。幂律4 可以用来进一步对相似的同类图形进行区分。 通过大量对i n t e r n e t 的大尺度量化研究，可以看到i i i i e m e t 同时具备小世界特 性和无尺度特性( 表2 5 ) 。文章第二章对小世界网络，无尺度网络的形成与特 征作了详细分析，为下一步的l i l t e m e t 建模工作做好基础准备。 2 0 0 42 0 0 5 i n t e m e t 平均最短路径 3 1 02 8 5 小( 小世界) 聚集程度 o 2 6 9o 4 5 2 大( 小世界，层次性) 度分布 r = 2 1 7f = 2 1 7 幂率( 无尺度) 表2 5i n t e r n e t 特征 2 4 马太效应 在建立随机网络模型的时候，e r d o s 和r e n v i 假设在安置连结之前能够得到 所有节点的清单。而事实上，万维网的页面数量绝对不是恒定的。1 9 9 0 年整个 万维网只有一个网页，而到今天它的网页数已经超过了3 0 亿。大约3 0 年前，整 个因特网只有几个路由器，随着新的路由器与网络原有的路由器相连结，如今路 由器的数量己经高达百万。由于现实中的网络具有不断成长的本性，所以老节点 获得连结的机会就比较高。 此外，并非所有的节点在增加连接的时候都是平等的。在选择将网页连结到 何处时，人们可以从数十亿个网站中进行选择。然而大部分人只熟悉整个万维网 的一小部分，这一小部分中往往包含那些拥有较多连结的站点，因为这样的沾点 更容易为人所知。只要连结到这些站点，就等于造就或加强了对它们的偏好。这 个过程称为“优先连结( d r e f e r e n i i a ia t t a c h m e n i ) 【2 3 】。在i n t e m e t 上，那些连结较 多的路由器通常还拥有更大的带宽，因而新用户就更倾向于连结到这些路由器 上。美国著名的社会学家k m e r f o n 将这种现象称之为“马太效应”。这个词来渊 于新约圣经的内锌：“儿f j 的，还要加给他，叫他有余。” 成长性和优先适结这两种j 订l 叽m * 释集散节点的存在：、1 新扎，i i n ! 时，它们更倾向j ：适站剑l ? f j 较衫适，l 洲i 点，随着时问的摊逊，返qm 、i 棚 i n t e r n e t 拓扑结构研究及ni m 网络建模中的应用 拥有比其他节点更多的连结数目。这种“富者逾富”的过程，有利于早期节点 它们更有可能成为集散节点。 i n t e m e t 中优先连结的机制常常是线性的，如果一个现存节点的连结数是其 相邻节点连结数的两倍，那么新节点与它连结的可能性，也是与邻近节点连结可 能性的两倍。美国波士顿大学的r e n d e r 及同事研究了不同类型的优先连结【2 4 l ， 如果这种机制运行得比线性更快f 例如，即一个节点的连结数是另一个的两倍， 而新节点连接到前者的可能性却是后者的4 倍) ，那就容易出现一个攫取最多连 结的集散节点，在这种”赢者通吃”的情况卜，网络最终演变为捐j 有一个中心集散 节点的星型拓扑结构。 2 5 分级层次结构 i n t e m e t 并不遵循一种精确的组织结构或者体系结构，它具有一种松散的层次 结构，见图2 6 。 图2 6i n t e m e t 体系结构图 一种量化i n t e m e t 体系结构的方法是通过主干( b a c k b o n e ) 的概念，i n t e r n e t 是由些连接大部分源目的对进行通信的主十连接而成。这种体系结构有两个 显著特点l 删。第一是：一些连接比其他连接更常用；第一二是：大部分的源目的 地路径倾向r 首先上行到更常用的连接，然后再f 行到不常用的连接。这就是 u d d o w n 策略，在i n t e m e t 早一条路径首先寻找上级的 下，然后再下行到能达到 最终目的的路线。 顺点和边的工作负载并不是拓扑量值，不能直接通过l n l e r n e t 幽来计算，不 过l - 】以通过源一| _ = i 1 的地对所经过的顶点利边的最z j 路仟数显束汁竹，这要使用到 介教? 亿a s ，a s + 和i r 图【+ i ，6 t 都是单渊增嘲数，指了饥钱坡大的，盱其际上 一一t _ | | ：蔓敬人的。 ，负载集中的点利边就组成j 良盯，l 义f 】11 ： i n t e r n e t 拓扑结构研究及在1 m 网络建模中的应用 有两种u p d o w n 路径定义方法：一种是严格的u p d o w n 路径，要求其中不能 存在局部最小值，遵循严格的先上行后下行的策略；另一种是松散的u d d o w n 路径，可以存在局部最小值，但是局部最小值要大于最终点的值。通过对a s 图 与i r 图的分析，发现8 0 都遵循着松散的u p d o w n 策略，说明i n t e m e t 的体系 结构性非常的明显。 另一个i n t e m e t 体系结构性质的标志是：倾向于度数越高的节点能更好的相互 连接。就是说度数高的节点能形成相当好的相互连接，因此被称作r i c h c l u b 现象 f 瞄1a 砌c h - c h j b 系数 ) = 面：赫，巾( k ) 是一个比率，用度数大于k 的 点( m k 个) 之间边的总数( b k ) 比上这些点之间最大的边数。研究显示巾( k ) 也 呈幂律增长，由( k ) k ，在a s 图和玳图中，v 值分别为1 1 o 2 与1 8 0 2 。r i c h c l u b 现象说明集散节点之间通常有很好的相互连接，但不能说明解散节点的多数边直 接与其他集散节点相连，通常大部分集散节点的多数边都是与周边的节点或小度 数的节点相连的。这里又用到度相关性概念见2 1 节定义5 。在a s 图中度分布存在 很强的相关性，就是在统计上高度数顶点大部分的邻居都是低度数顶点，而反之 亦然。但i r 图却表现出不同的行为，它围绕一个恒值进行较小的变化，这个恒值 接近2 8 ，高度数节点倾向于连接高度数节点。 对i n t e m e t 绘制拓扑图，并且对其大规模拓扑度量值和其拓扑特征进行分析， 目的正是了解其内在的动力学机制，作为对i n t e m e t 建模的准备知识，那么下一章 就丌始讨论如何对i n t e m e t 进行拓扑建模。 i n l c m e “再扑结构i l j 究及曲：i m 刚络建模中的应用 第三章几种经典的网络拓扑模型 在大尺度上，对i n t e m e t 建模就是在观测a s 和i r 图的基础上进行重现其拓扑 性质的图的构造。把i n t e m e t 作为图来考虑就是要忽略其路由器和连接的物理特 征。 最初用来对h t e m e t 建模的传统的方法是静态随机图( s t a t i cr a n d o mg r a p h s ) ， 用来描述不规则变化的复杂网络，e r 模型是其中最简单的一种。它的特征是完 全没有任何指导元素问进行连接的规则信息，顶点对之间以给定的概率随机的连 接。基于随机图模型的范例，研究者开发出i n t e m e 【模型来测试通信协议。但是这 种测试的性能对于拓扑结构的细节非常敏感，可能在模型上运行良好的协议，在 真正的i n t e m e t 上运行就很差。 用统计物理学的方法对网络建模把动态进化规则作为主要的元素，基于此形 成了一种新的建模方式，它有两个基本方面：1 ，i n t e m e 或者其他复杂网络，是 一个增长的网络，其节点和连接数都随时间不断增加。2 ，连接都是由随机过程 来确定，这个随机过程具有节点局部属性的偏好性。 3 1 静态随机图模型 1 9 5 9 年，为了描述通信和生命科学中的网络，e r d o s 和r e n v i 提出，通过在 网络节点问随机地布：霞连结，就可以有效地模拟出这类系统。随机网络理论有一 项重要预测：尽管连结是随机安置的，但由此形成的网络却是高度民主的，也就 是说，绝大部分节点的连结数目会大致相同。随机网络中节点的分布方式将遵循 钟形的泊松分布，连接数目比平均数高许多或低许多的节点，都十分罕见。随机 网络也称作指数网络，因为一个节点连接k 个其他节点的概率，会随着k 值的增 大而呈指数递减。 3 1 1e r 模型 第一个随机网络的理论模型即e r 模型( t h ee r d o s r n v im o d e i ) 。e r 模型 认为网络是静态的，就是有固定的规模。网络丌始于个常数的独立点集，建模 由在点对之问分配边的规则求确定。 图g ne 由 用这种力法， 由e 条随机连接在点j 边所 ：| 【成。 所形成的概率空川f t个| 冬| 邴川j 始 龠 能 蜒 v ? - 点叭j 阶掣， 龠r 他 n t e r n c t 拓扑结杜j 研究及柏- l m 网络建模中的脚用 样的几率可能发生。该图的一个变体( g j l b e n ，1 9 5 9 ) g n p 由n 个不同的点组成， 共有n ( n 1 ) 2 条可能的边，每条边以概率p 相互连接，以概率1 - p 不连斟2 ”。这种 图的概率是 p ( g e ) = p 5 ( 1 一p ) ；一1 卜 ( 3 1 ) 接下来考虑以概率p 连接定义的e r 模型。这种模型的性质很容易被推导 _ 来，平均边的数量是( e ) = n ( n 1 ) p 2 ，那么平均度数就是 ( 七) ：等叫却啦 ( 3 z ) 要确定度分布p ( k ) ，注意到创建一个概率为p 的顶点的概率，等价于连接其他 k 个顶点和不连接另n 1 k 个顶点的概率。由于每条边都是一个独立事件，那末概 率p ( k ) 就是遵从如下二项分布： 荆2 枷刊“ 。) 其中n p = ( k ) ，所以该二项分布近似于泊松分布： 耶一书，鳟 a ， e r 模型的度分布最显著的特点就是比幂衰减的更快，只允许非常小的度波 动。在这一点上，e r 模型是一个同构的随机图的原型例子，不同点的度数接近 于常数，约等于平均度数( k ) 。 e r 模型聚集程度( c ) 来自于连接的独立性，对任一个点聚集程度就是 ( c ) = p = ( k ) n ( 3 5 ) 从这个公式可看出，该模型的聚集程度随着图规模增大逐渐减小，当网络 大到无限时，聚集程度趋向于o 。 对于顶点数为n 的网络的平均最短距离，假定平均度数 1 ，任何一个 顶点距离为1 的邻居的数量为( k ) ，不考虑环，距离为d 晌点的数量为( ) 。，其中 顶点的总数为n ，则可计算j 卜均最短趼离为 ( 忙器 e ， 这个值表现构似多幻尔川络- i 小| | y 俐j 以 i n c e r n e t 拓扑结构研究及在l m 嘲络建模中的施用 e r 模型尽管表现了小世界性质，但是却不能认为很好的表现了i n t e r n e t 。首 先，它不能体现出i n t e r n e t 的其他特征性质，比如重尾度分布和大的度波动。聚集 程度也非常的不匹配，如a s 图的聚集程度为o 3 0 ，但是相同规模的e r d o s r n y i m o d e l 的聚集程度只有约4 x 1 0 ，小了3 个数量级。 3 1 2 扩展的e r 模型 为了产生个具有预先确定的度分布( 未必是泊松分布) 的扩展的随机图， 可以对e r 模型进行扩展。这个思想首先由b e n d e r 和c a n d i e l d ( 1 9 7 8 ) 提出【2 8 j ，图被 分配了一个固定的度序列 ) ，i - 1 ，n ，其中篇i 个顶点具有度数t ，然后根 据点各自的度数在点之间分配边的端点。就是随机数集 t ( 其中m 三丘三n ) 被产生出来，然后根据所选择的度分布p ( k ) 被分配给各个点。共有。等条边。 考虑具有任意度分布p ( k ) 的扩展随机图，任意一条边与度数为k 的点连接的 概率是k p ( k ) ( k ) 。可以计算出该模型的聚集程度： ：专掣 ， 二二里 ( c ) _ v 一一其中7 7 3 ( 3 8 ) 计算得平均最短路径为： 小嚣 ( 3 9 ) 总之对于有限的度分布，度的波动( 2 ) 是有限的，司+ 以观察到( c ) 1 n ( ，) l o g n ，这与e r 模型结果是相同的。然而对于具有幂率度，f 2 ) 非常大 韪至脱离r n ，这时聚集程度比相同规模和i f 均度数的e r 模型盟人，因此该模型 与e r 膜，弘相比哑近似于无尺度网络的拓扑结构。 3 2 演化型i n t e r n e t 模型 雎j l l f i j 代川州薅杂网络的理论研7 洲川叫i 从州t q 。m 纪m 业雠扎一一j 埘嘲 i n t e m e l 拓扑结构 i f 究及柏二【m 网络建模中的戍用 络演化的建模，这种新的方法就是把网络看成根据一定的动力学规则并发的增加 新边和新点的产物。换句话说，重点在于产生拓扑性质的进化机制，i n t e m e t 所表 现的拓扑特性可以看作系统动力学的副产品。这种方法论类似于用统计物理学研 究复杂现象，目的是为了通过研究其结构的动力学从而预知其大尺度性质。 些 解析技术和统计技术从统计物理学中借鉴来应用到这里，这些技术主要用来解决 指导网络形成的基本的动力学。在这里我们可阻把时问的增长看作是网络上新点 的增加，用这种方法，时间被这样定义l = n m o ，m o 是最初的核的规模，网络 的增长过程由此开始。因此根据一定的动力学规则，每一个时间步对应于新点的 增加，这些新点与原有节点之间建立一定数量的连接。可以通过概率p ( k ，s ，t ) 来对 系统进行描述，这个概率表示在时间s 引入一个度数为k 的节点的概率，其中t s 。 知道了概率p ( k ，s ，t ) 就能够求 时间t 中第s 个点的平均度数，( f ) ： 七s ( f ) 2 磊懒蹦) ( 3 1 1 ) 时间t 的度分布可以用如下式表示( n = t 十m o ) ： p ，f ) = 罗p ( 足，s ，f ) ( 3 1 2 ) f + m o 例 由此可计算出度分布尸他) = l j m p ( 女，f ) 。 在上面的离散方程中，系统的演化使用以时间增长的概率p ( k ，s ，t ) 表示的 m a s t e r 方程|