《无标度网络拓扑的统计研究.pdf》由会员分享，可在线阅读，更多相关《无标度网络拓扑的统计研究.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第卷 第期 年月 （）科学技 术与 工程 无标度网络拓扑的统计研究王羽孙颖（西北大学信息学院，西安 ；西北工业大学理学院；西安）摘 要 近年来，无标度网络已成为系统科学研究的热点，出现了一些通用的形式化分析方法。从概率论的角度，分析了无标度的形成机制及其对复杂系统宏观结构的影响，介绍了国际上最有影响的一些成果和研究，并简述了无标度网络的应用前景。关键词 复杂网络 无标度网络幕律拓扑结构 最大等级法中图法分类号；文献标识码 无标度网络是利用节点的度分布来研究复杂系统拓扑结构的理论。 年， 等在研究无标度网络。的拓扑特点时，提出这一理论 。实验证实 ） ， 无标度网络具有“小世界效应”。因此， 与
2、正则网格、随机图、小世界网络等模型相比，它更贴近真实网络，已成为近年来系统科学研究的热点。无标度性的宏观作用讨论网络的宏观性质需要有一个形式化框架。与“小世界网络”的两位创始人利用母函数法， 建立了处理具有任意度分布的随机图的统一途径汇， 。平均路径长度，其母函数为任意给定度分布二，（）对无标度性的解释 年， 等发现真实网络的度分布既非正态分布又非指数分布，而是幂律分布 一 ， ， 其中、二， ， ；。二兴（“，）是 函数，） ， 网络是严重两极分化的。例如，基本上是由少数度很高的节点串连起来的， 的页面的度不到，而占总数不到万分之一 。任意边与另外人条边相邻的概率（ ） ，、为，其母函数为，
3、（ ）二艺。 二 如。卜）， 、 ，、 ，一。二云哭于令。任选一点，经过一条边到达第层连）”一， 一”一朴“ ”“的极少数点却有（以上的度 等提出了一个模型解释无标度网络生通点，这一层所包含的节点数目的期望为二，。，、。，、。 ，月、（，（ ，（ ）二 二 ：（） （）山。、一、一、”产产产互一一”、一一成机制 。它基于两点假设：动态增长和马太效应。这两个假设都是必要条件：取消第一个后，度分布呈指数速度衰减；取消第二个后，度分布随时间逐渐演变为正态分布。 等根据模型，用个初始节点迭代了 （】步，得到度指数的 年月日收到。第一作者简介：王 羽（ ），女， 计算机软件与理论专业研究生。以） （）。
4、设为网络的平均路径长度，连通图中任意点的前个连接层包含了所有节点，因此叉。当 ， ：时，整理得 （， ） （ ，）（）研究方向：分布式网络，网络安全。， ： 二。，科学技 术与 工 程表 和的几个拓扑指标。表示把子域着作节点， 表示把路由器看作节点拓扑指标网络规模一卷实验值 ，理论值出度指数人度指数，抽一 ，参考文献一 表显示了两个典型复杂系统 和的拓扑指标。其中，系数较大，实际值比理论值，略高。 等测定 ， 的平均路径长度为二 十 ，与理论预测在形式上相吻合。 的结构研究有向图时，需要同时考虑出度与人度。以 ；， 表示人度为 、 出度为的联合概率分布，其母函数为（ ， ）艺 。那么，人度、出
5、度、指向任意边、任意边所指的概率的母函数分别为 （）二（，），（）二（，），尹，（），、 ，（ ！。 二）名第一层邻接点数目的期望（不论人向方式、出向方式）。有最大强连通块。以，。表示网络中指向部分、被所指部分和本身的规模所占的比例。记，为任意边不指向中节点的概率，它等于该边所指的边都不指向中点的概率，即，二，（）。记为任意边不被的点所指的概率，同样。二，（）。解出这两个方程的最小非负解， 则； ， 。可计算如下：气一（ ），毓二一（），（ ）气一（，）一（，）（， 等利用搜索引擎 分析了亿网页和亿超链接，得到凡二，并提出了著名的基于连通性的结构 。等按（）式计算的理论结果； ，与 等的实验结
6、果较接近 。无标度网络的演化 等对无标度网络随度指数的变化而演化的情况进行了详细的研究 ，他们证明：存在阑值 。当。时，网络“几乎”没有主连通块；当。时，网络“几乎”只有唯一的主连通块。当。时，随着的减小，次连通块的规模从（川）缩小为（），网络的连通性越来越强。当时，网络“几乎”是完全图。等用母函数法也算得相同的。从表可知，的度指数小于，因此它存在主连通块，也就是上文的 无标度网络的启示作为一种系统理论，无标度网络的提出，为其他学科研究提供了很多有益启示：（）病毒传播。改变以往传染病模型认为病毒的扩散取决于传染强度的阂值的观念，发现无标度网中不存在这个阂值，“所有病毒都可以在无标度网络中传播和
7、长期存在，即使传染力很低的病毒也是如此，（，）！混沌同步。汪小帆等证明。 ，当无标度网的藕合强度大于某一正临界值时，无论规模如何都会出现同步现象。例如，尽管不同路由器独立地发布路由消息，但它们最终会达到同步状态，造成网络拥塞。（ ）贪心搜索。小世界性表明，在任意两个节 。文献【指出，当度指数， 时，大规模随机网络存在唯一的概率几乎为，否则，若其邻边指向中的点，则该边与邻边都在中。“几乎”的意思是，随机事件序列川依概率收敛为， 卜，图二（，）上的强连通块（，），如果有 二（），则称为的主连通块。期王 羽，等；无标度网络拓扑的统计研究点间寻找短的路径（网络规模的对数级大小）是有达 ，而频数法只有希
8、望的，这对文件搜索很有启发性。 在文献【中，我们设计了一种高精度的方研究了带扰动的二维网格上的贪心搜索算法，找到法 最大等级法，可以弥补顺序法的不足，并证明一种对数平方级的算法” 。进一步的研究方向它是判定整数型大样本幂律随机量的充要条件。我们以平均相对误差为主要评价指标，在相同条件下比较了频数法、最大等级法、中间等级法， 、 顺序法 和著名的 方法 对幂指数的估计精自模型出现以来，学者们越来越重视度分布的两极分化这一关键因素。胡海波等甚至借宏观经济学中刻画收入差异程度的系数，建立了一个演化模型 。目前，尚无一个能深人揭示“马太效应”与幂律之间关系的理论体系。不过，诚如 等所指出的那样 ， 概
9、率论提供了一些有益的线索：引理（广义中心极限定理） 当 时，独立同分布的随机变量之和艺二；的极限分布是 分布：（尹， ；），其中，。引理（重尾渐进） 若一（刀，声；），它的特征指数偏度一， ， 则当二时，（）一 （， ） 二一，其中， （ ） （ 。） 引理描述了即使在期望、方差无限大时，随机和仍然有极限分布，它是有重尾和偏度的一系列包罗广泛的分布族。引理表明，幂律实际上就是 分布的近似。这启示我们，从无限制增长（方差无限）的角度来考虑幂律的成因是有希望的。我们的工作幂律的验证及幂指数的估计，是很基础但往往容易被忽视的问题。最简单的方法就是计算待测量的频数，在双对数坐标中作图，看图像是否近似直
10、线， 然后线性拟合出幂指数。这一方法过于粗糙，有时甚至产生错误结论，如文献【中的反例图因此等建议不用频数法而用顺序法验证幂律。我们发现，当样本不太大时，这个方法确实较频数法精确，但在 个样本的场合，它的平均相对误差高度。我们发现（， 时，最大等级法的平均相对误差最低，效果最好，使整数型大样本估计的平均相对误差降低至。如表所示。表对 个幂律随机数，在步长为的区间， 内模拟次得到几种方法的平均相对误差项目频数法最大等级法中间等级法顺序法平均相对误差 结语无标度性刻画了网络节点在微观上的不平等。网络的增长与马太效应是导致它的必不可少的因素， 尤其是后者受到很多学者关注。无标度性深刻影响了网络的宏观结
11、构，导致了平均路径长度的对数级大小和的 结构。分析网络的聚集系数须用二部图解释【 ， 本文不赘述。对网络拓扑性质的认识，为理解病毒传播机制和 控制等方面提供了有益帮助，无标度网络思想已经渗透到应用研究中了。参考文献 ， ， ；（）； ， 试 ，；（）： ， ， ， ； ， ， ， ； ， ， ，当二时， 分布蜕化为正态分布。不仅如此，著名的分布、 分布都是。分布的平凡（ ）例子。科学技术与 工程卷， ； ， ， ！ ， ；（）： ， ， ， ， ， ；（）： ， ， ， 以 ： ， ， ， ， ，；（）： ， ， ， ； ； ， ， ： 人 ， ， ，： ， ， ， ， ； ， ， （ ） ， ； 一 孙颖，刘小冬，王 羽用最大等级法测定幕律系统工程，； （） ， 巧” ， ；（）： ， 一 ： ，；（）： 丁学东，文献计量学基础北京：北京大学出版社，： 山日 ， ； （）： ：， ， ， ，（ ， ， ，； “ ， ， ，）【 ， ， 一 一 一