小世界网络统计量属性分析

葛伟伦

摘要：该文首先阐述了复杂网络最短路径平均距离、度值和集聚系数属性意义，并推导出相应的计算公式。概况了随机化加边优于随机化重连构造小世界网络模型的合理性。通过MATLAB设计仿真实验，通过得到的统计图分析了小世界网络的特征和变化规律，为理解实际网络的运行机理及监督、维护和控制网络运行提供参考数据。

关键词：复杂网络；度；集聚系数；最短路径平均距离；MATLAB

中图分类号： TP393 文献标志码：A 文章编号：1009-3044（2016）16-0052-02

当前对复杂网络的研究引起了相关领域学者和专家的高度关注和重视，该网络是由大量节点相互连接而成，网络规模大，网络拓扑结构复杂且动态变化。现实生活中的人际关系网、组织结构网络、车辆交通网络、计算机网络、生物学中的神经网络、细胞网络等都属于复杂网络，人、车、细胞、计算机、神经元可抽象成点，点之间的依赖关系、共存性、相互作用、连接性可抽象成边。把各种类型的复杂网络抽象成具体模型是探索和研究复杂网络最好的方式，近年来提出的小世界网络模型深刻揭示了复杂网络背后隐藏的客观规律和属性特征。

1 复杂网络统计量属性[1-2]

1.1 最短路径平均距离

复杂网络中任意两个节点的最短路径距离Si，j指从节点i到j的多条冗余路径中选择一条包含边数目最少的路径，即最短路径上边的数目称为i到j的最短距离。整个网络最短路径平均距离为所有节点对最短路径距离的平均值，设N为网络节点数目，则网络最短路径平均距离Savg用公式表示：

2 网络模型[3]

对网络的探索经历了从规则网络、随机网络到复杂网络模型的发展历程。规则网络模型节点之间按照有规律的方式连接，形成规则图，具有对称性，任一节点的相邻边数都相同，规则网络是一种理想和假设的网络构造，不能表示真实动态的网络。随机网络模型是节点之间以完全随机的方式进行连接，形成随机图，是复杂网络的一个极端，是由匈牙利著名的两位数学家保罗·爱尔德和阿尔弗雷德·莱利在1960年提出，此模型一直被认为是刻画现实世界网络最形象的模型。但在近年来的研究中测得的实验数据与随机图模型统计的数据背离较大，并不能真实代表复杂网络。直到1998年Watts和Strogatz提出的WS小世界网络模型和后来Newman和Watts提出的改进NW小世界网络模型才真实反映复杂网络的特征和规律。

2.1 WS和NW小世界模型构造过程[4-5]

从一个含有N个节点的规则环状网络开始，每个节点都与它最近邻的左右各m/2个结点连接，连出m条边，m为偶数，m也是节点的度数。

1）随机化重连：以概率p，一般取p=0.1随机地重新连接网络中的每个边，即将边的一个节点保持不变，对端节点取为网络中随机选择的另一个节点。并规定任意两个节点之间至多只能有一条边，并去除自连接，构造出WS小世界网络模型。改变p值，即可实现从规则网络（p=0）向随机网络（p=1）转换。

2）随机化加边：以概率p，一般取p=0.1在随机选取的一对节点之间加上一条边。并规定任意两个节点之间至多只能有一条边，并去除自连接，构造出NW小世界网络模型。改变p值可以实现从规则网络（p=0）向随机网络（p=1）转换。

2.2 小世界模型构造过程分析

NW模型是通过用“随机化加边”取代WS小世界网络模型构造中的“随机化重连”，由于WS小世界模型构造中的随机化重连会破坏原网络的连通性和产生孤立节点，所以N小世界模型更符合复杂网络真实情况。

小世界网络模型是处于0

3 仿真实验设计和分析[6]

3.1 实验设计

本文对小世界网络选用随机化加边构造算法来实现，使用MATLAB进行仿真实验，验证小世界网络的统计量属性及变化规律。用概率p=0.1来决定一对节点是否加边来构造规则网络向NW小世界网络的转换，用随机函

数rand（）来产生一个随机值，当≤0.1，两个节点随机加边，对两个节点的选择可由int（Nrand（）+1）来决定，记为μ，表示节点编号，1≤μ≤N，int为向下取整函数，运算两次随机产生一对节点编号，按产生的编号连接实现随机化加边。实验数据样本设置为N=5000，边数K=10000。分别对NW小世界网络模型的平均路径长度、度值和集聚系数进行统计分析，产生的统计图如下所示。

3.2 WS模型度分布分析

如图1所示，对于0

3.3 WS模型最短路径距离分析

如图2所示，任意两个节点之间的最短距离不超过6，距离为7的节点对数为0，符合六度理论。由实验统计得到的网络平均最短路径距离约为2.021，较小。由于对于0

3.4 WS模型集聚系数分析

如图3所示，各个节点的集聚系数较大但变化幅度不大，由实验统计得到的集聚系数约为0.562。因为对于p=0的规则网络，集聚系数R=3（K-2）/4（K-1），对于0

4 结束语

本文对复杂网络的几个重要属性进行归纳，并推导出属性值的计算公式。分析了能代表复杂网络的WS和NW小世界网络模型构造过程。通过MATLAB设计了仿真实验，基于统计数据和统计图剖析了复杂网络属性值的特征和隐藏的变化规律，为我们认识实际的网络及监控、维护、管理和控制网络正常运行提供重要的参考数据。

参考文献：

[1] 王小帆，李翔，陈关荣.复杂网络理论及应用[M].北京：清华大学出版社，2006.

[2] 程学旗，沈华伟.复杂网络的社区结构[J].复杂系统与复杂性科学，2011，8（1）：57-66.

[3] 郭雷，许晓鸣.复杂网络[M].上海：上海科技教育出版社，2010.

[4] 刘常昱，胡晓峰，司光亚，等.基于小世界网络的舆论传播模型研究 [J].系统仿真学报，2006，18（12）：3608-3611.

[5] 李果，高建民，高智勇，等.基于小世界网络的复杂系统故障传播模型[J].西安交通大学学报， 2007，41（3）：334-338.

[6] 王波，王万良.WS和NW两种小世界网络模型的建模及仿真研究[J].浙江工业大学学报，2009，37（2）：179-188.