Internet网络拓扑建模(2)

幂律分布特性是一种广泛存在于自然界与人类社会的性质，该特性表现为大量事件出现概率很小，而少量事件出现概率很大的分布现象．例如，人类语言中只有少数词汇的使用频率很高，而绝大多数词汇实际上很少被使用的现象．各领域学者已发现的典型幂律分布，包括地震规模大小的分布、月坑直径的分布、战争规模分布、生物物种数量的分布等等，其形式多种多样【２９】．

Ｉｎｔｅｒａｃｔ网络拓扑结构中存在的幂律分布特性【２６】是１９９９年由Ｆａｌｏｕｔｓｏｓ三兄弟发现的．在Ｉｎｔｅｒｎｅｔ网络拓扑结构中存在的幂律分布特性未被揭示之前，Ｉｎｔｅｒｎｅｔ网络一直被认为是一种随机网络（ｒａｎｄｏｍｎｅｔｗｏｒｋ），且网络节点度分布符合二项分布，即在满足Ⅳｐ（其中∥是节点个数炉是连接概率）趋于定值的情形下，近似服从泊松分布．由于泊松分布下高度数节点存在的可能性呈指数级衰减，因此，可基本忽略高度数节点，而将网络拓扑近似看作一种均匀结构，即绝大多数节点的度数都分布在节点平均度附近‘３０。３２１；而Ｉｎｔｅｒｎｅｔ网络中幂律分布特性的发现证明了Ｉｎｔｅｍｅｔ网络的节点度分布应满足幂律分布，即节点度间实际上相差悬殊，在双对数图中应表现为一条斜率为负的直线，这一线性关系是判断给定的实例中随机变量是否满足幂律分布的依据．另外，由于幂函数具有标度不变性，因此，人们现在也把节点度服从幂律分布的网络称为无标度网络（ｓｃａｌｅ．ｆｒｅｅｎｅｔｗｏｒｋ）．

Ｆａｌｏｕｔｓｏｓ兄弟发现的幂律分布特性包括３条幂律及ｌ条近似幂律【２６１，分别为：

幂律ｌ（秩指数矗）．节点出度与该节点等级的月次幂成比例．

ｄ，ｏＣ蠢．

其中，或表示节点ｖ的出度，～表示节点ｖ在网络拓扑中按度降序排列的等级．

幂律２（度指数Ｄ）．度大于ｄ的节点在网络拓扑中所占百分比与节点出度ｄ的Ｄ次幂成比例．

厶茁ｄＤ，

其中，后代表该百分比ｐ是Ｒ的倒数．幂律３（特征值力，特征值五，与其次序ｉ的献幂成比例．

１１２ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９

疋芘ｉ６，

其中，兄，为网络对应连接矩阵的特征值，ｆ为将特征值按降序排列时的序列号．

另外，幂律２还指出一条近似幂律（ｈｏｐ—ｐｌｏｔ指数田：磊跳内节点对（ｐａｉｒｓ

比例．ｏｆｎｏｄｅｓ）的数量与ｈ的始次幂成

幂律分布特性对于Ｉｎｔｅｒｎｅｔ网络拓扑结构生成以及网络性能改进影响很大，例如，该特性可反映出网络拓扑结构与用户需求之间的明显联系，因此我们可以考虑能否在降低用户需求幂律指数，即分布式部署高度数节点的情况下，改善网络传输性能等等［３３，３４］．另外，Ｉｎｔｅｒｎｅｔ网络拓扑结构的幂律分布特性对网络的动力学性质等也有深刻影响．以病毒传播为例，之前基于规则网络及随机网络的研究曾认ｆｆ；ｊ［３５，３６］，病毒只有当传染强度大于某阈值时才能在Ｉｎｔｅｒｎｅｔ网络中长期存活；而基于幂律分布特性的研究则表明，Ｉｎｔｅｒｎｅｔ网络不存在类似的阈值（３７＿４０１。要想在现有Ｉｎｔｅｒｎｅｔ这样的无标度网络上彻底消灭病毒，即使是已知病毒也不太可能【６，４１１．

２．１．２鲁棒且脆弱性

鲁棒且脆弱性特性【２７】是大规模Ｉｎｔｅｒａｃｔ网络的基本特性之一，也是体现随机图网络和无标度网络之间存在显著差异的重要拓扑特性．与早期随机图网络不同，无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性，因此，无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性．

这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响．研究表ｆｉｒ］［４２，４３１。无标度网络具有很强的容错性，但是对基于节点度值的选择性攻击而言，其抗攻击能力相当差，高度数节点的存在极大地削弱了网络的鲁棒性，一个恶意攻击者只需选择攻击网络很少的一部分高度数节点，就能使网络迅速瘫痪．另外，已有研究‘１０】指出，Ｉｎｔｅｒｎｅｔ网络路由器级拓扑表现出与自治域级拓扑所不同的鲁棒且脆弱性。并且其生成机理不能同样用无标度模型来加以刻画．

２．１．３聚集特性

随着对网络拓扑的进一步研究，人们发现仅用节点度分布来刻画网络拓扑结构是远远不够的，满足同样幂律分布的网络完全可以呈现截然不同的拓扑结构。在幂律分布特性的基础上，人们开始研究网络拓扑中存在的聚集特性【２ｓ】．

聚集特性是主要反映网络节点关联性［６】的特性之一，并通过定义聚集系数来刻画节点邻居之间的亲疏程度．基于自治域级Ｉｎｔｅｍｅｔ网络拓扑的相关研究表吲４４，４５１，实陌－－．。。］．。。。。。。’。。…ｚ。．。的聚集系数，且低度数节点也很可能具有较高的局部聚集系数．然而，目前相当多的嘲络拓扑模型并不能刻画出这一拓扑特性．有关详细的聚集系数介绍参见第２．２节．

２．２主要度量指标

目前，在Ｉｎｔｅｒｎｅｔ网络拓扑建模中使用的主要度量指标包括节点度分布、聚集系数、介数、核数、平均路径长度等：

（１）节点度分布Ｐ（扮：节点度分布函数尹（七）定义为网络中度数为后的节点个数占总节点数的比例，也等于在随机一致原则下挑选出的节点具有度数ｋ的概率；所有节点度之和的平均值则称为网络的节点平均度（”．

规则图中：所有节点拥有相同数量的边，即节点的度分布ｐ（七）函数为定值；

随机图中：节点的度分布遵循泊松分布，大多数网络节点的度都集中于网络节点平均度门ｐ附近，远离峰值的节点数呈指数衰减，即随机图中一个节点拥有ｋ条边（七大于等于节点平均度）的概率很小：

无标度嘲络中：节点的度分布接近幂律形式分布Ｉ口（七）一ｋ－ｒ．

（２）聚集系数：聚集系数（ｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔ）是从全局来刻画网络的聚集特性的度量指标，用来刻画一个节点邻居之间的亲疏程度．Ｄｏｒｏｇｏｖｔｅｓｅｖｔ删给出了３种不同的衡量聚集特性的参数。分别为：

局部聚集系数Ｃ（∞：

Ｃ（．ｉ｝）＝［，，ｌ。（七）】／（七（七一１）／２），

其中，［ｍ。（动】表示节点度为ｋ的节点的邻居之间平均存在的连接数．

平均聚集系数（ｍｅａｎｌｏｃａｌｃｌｕｓｔｅｒｉｎｇ）：’

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１３

一●＇

ｋｃ＝∑Ｐ（七）ｃ（七），

其中，Ｐ∞表示图中任意一个节点的度数为七的概率，即节点的度分布

全局聚集系数（ｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔ）：

∑Ｐ（七）［‰（七）】

Ｃ础＝

ＩＩ∑Ｐ（ｋ）ｋ（七一１）／２＝—』—————————．—＝：——．一，【后２】一七∑Ｐ（七）七（七一１）ｃ（七）

其中，眵］表示节点度的二阶矩阵，ｋ表示网络的平均节点度数．

目前，在拓扑建模领域，通常使用平均聚集系数来衡量聚集特性，但是，这一度量指标并不总能正确地反映网络的真实情况．在某些情况下，平均聚集系数和全局聚集系数可能存在不一致性【４３１，需要更深入的研究、分析、论证．

（３）介数（ｂｅｔｗｅｅｎｎｅｓｓ）：介数【４６】也是Ｉｎｔｅｒｎｅｔ网络拓扑的一个重要度量，分为节点介数（ｎｏｄｅｂｅｔｗｅｅｒｍｅｓｓ）和边介数（ｅｄｇｅｂｅｔ …… 此处隐藏：2256字，全部文档内容请下载后查看。喜欢就下载吧 ……