无标度网络拓扑的统计研究.pdf

第７卷第８期２００７年４月科学技术与工程Ｖｏｌ７Ｎｏ．８Ａｐｒ．２００７１６７１－１８１９（２００７）[e-mail]．无标度网络拓扑的统计研究王羽孙颖１（西北大学信息学院，西安７１０１２７；西北工业大学理学院‘；西安７１００７２）摘要近年来，无标度网络已成为系统科学研究的热点，出现了一些通用的形式化分析方法。从概率论的角度，分析了无标度的形成机制及其对复杂系统宏观结构的影响，介绍了国际上最有影响的一些成果和研究，并简述了无标度网络的应用前景。关键词复杂网络ＢＡ无标度网络幕律拓扑结构最大等级法中图法分类号０１８９．１３；文献标识码Ａ无标度网络是利用节点的度分布来研究复杂系无标度网络。统拓扑结构的理论。１９９８年，Ｂａｒａｂｆｋｓｉ等在研究Ｗｅｂ的拓扑特点时，提出这一理论［１ｌ。实验证２无标度性的宏观作用实［［２），无标度网络具有“小世界效应”。因此，’与正则网格、随机图、小世界网络等模型相比，它更贴近讨论网络的宏观性质需要有一个形式化框架。真实网络，已成为近年来系统科学研究的热点。Ｎｅｗｍａｎ与“小世界网络”的两位创始人利用母函数法，建立了处理具有任意度分布的随机图的统一途１对无标度性的解释径汇，〕。２。１平均路径长度１９９８年，Ｂａｒａｂｂｓｉ等发现真实网络的度分布既任意给定度分布｛ｐｋＩｋ二０，１，…｝，其母函数为非正态分布又非指数分布，而是幂律分布ｐｋ＝Ｉｐｋｘｋ。任意边与另外人条边相邻的概率Ｃｋ一，，其中、二１，２，．．．；。二兴（“，）是ＫｉｅｍａｎｎＧｏ（ｘ）（ｋ＋１）ｐｋ．，‘、７Ｉ其母函数为Ｇ，（ｘ）二艺。＊二‘＝－ｚｅｔａ函数，，＞１）［’＇，ＳＦ网络是严重两极分化的。为，＊Ｅ如。．例如，Ｗｅｂ基本上是由少数度很高的节点串连起来Ｇ＇卜）．．．，＿．Ｉ．‘、、，＿，、，一．。二的，８０％的页面的度不到４，而占总数不到万分之一云哭于令。任选一点，经过ｋ一１条边到达第ｋ层连的极少数点却有１００（〕以上的度［３１０Ｇ＇ｏ｛１）”一￣，．’一‘”一朴￣“￣／．‘”’“‘Ｂａｒａｂｆｌｓｉ等提出了一个模型解释无标度网络生通点，这一层所包含的节点数目的期望为ｚｋ二成机制［［４１。它基于两点假设：动态增长和马太效ｄ＿，。，＿＿ＧＯ（Ｇ，（．．．Ｇ，，，、、、．（ｘ）））１二二：＝Ｇ＇。，，＿、＿ｔｏ（１）ＧＩ．。－．（１）＝，月、应。这两个假设都是必要条件：取消第一个后，度分山’。、一’、一’、”产产产’‘’互一一”、‘／’１、一２一以ｋ）（１）。设ｌ为网络的平均路径长度，连通图中任布呈指数速度衰减；取消第二个后，度分布随时间逐意点的前ｌ个连接层包含了所有节点，因此１＋渐演变为正态分布。Ｂａｒａｂ４ｓｉ等根据模型，用５个初始节点迭代了２００００（】步，得到度指数ｙ＝２．９的叉‘＝Ｎ。Ｉ当Ｎ》ｚ１，ｚ２》：：时，整理得Ｉｎ（Ｎ／ｚ，）２００６年１１月２７日收到。ｌ＝１＋（１）Ｉｎ（ｚ２／ｚ，）第一作者简介：王羽（１９８２－），女，计算机软件与理论专业研究生。研究方向：分布式网络，网络安全。Ｆ，ｍａｉｌ：ｗａｎｇｙｕ．ｓｉｎｌｅ＠ｐｍａ７．二。，１５１８科学技术与工程７卷表１Ｉｎｔｅｒｎｅｔ和Ｗｅｂ的几个拓扑指标。Ｉｎｔｅｒｄｏｍａｉｎ表示把子域着作节点，ｒｏｕｔｅｒ表示把路由器看作节点拓扑指标实验值理论值出度指数人度指数Ｋ网络规模参考文献ｌｏｒ，１ｐ，７．ｗ，抽Ｉｎｔｅｒｄｏｍａｉｎ３０１５一４３８９２．１一２．２３０一４０［６］ｒｏｕｔｅｒ１５００００１１７．４７６０［７］ＷＷＷ２ｘ１０８１６７．６１２．７２２．１４０００［８］表１显示了两个典型复杂系统Ｉｎｔｅｎｒｅｔ和Ｗｅｂ的拓扑指有主连通块④；当Ｙ＜Ｙ。时，网络“几乎”只有唯一的标。其中，系数Ｋ较大，实际值ｌ‘比理论值ｌ，略高。Ａｌｂｅｔｒ主连通块。②当１＜Ｙ＜Ｙ。时，随着Ｙ的减小，次连等测定［［９］，Ｗｅｂ的平均路径长度为ｌ二０．３５十２．０６１ｇＮ，与理通块的规模从ｏ（１ｇ川）缩小为Ｏ（１），网络的连论预测在形式上相吻合。２．２Ｗｅｂ的结构通性越来越强。③当０＜Ｙ＜１时，网络“几乎”是完全图。研究有向图时，需要同时考虑出度与人度。以｛Ｐ；ｋＩｊ，ｋ＝０，１，．．．｝表示人度为．１、出度为ｋ的联合概Ｎｅｗｍａｎ等用母函数法也算得相同的Ｙｏ。从表率分布，其母函数为Ｄ（ｓ，ｔ）＝艺Ｊ＂ｉｋｉｓｔｋ。那么，１可知，Ｗｅｂ的度指数小于３，因此它存在主连通块，也就是上文的ＳＣＣ．人度、出度、指向任意边、任意边所指的概率的母函数分别为Ｆ．（ｓ）二Ｄ（ｓ，１），Ｇｏ（ｔ）二Ｄ（１，ｔ），３无标度网络的启示＿，、１ａＤ１ａＤ尹，（ｓ）＝—ＩＧ，（ｔ）ｚａｔ！。二Ｉ’名ａｓ第一层邻接点