WS小世界网络统计特性研究摘要：WS小世界网络是一种常见的网络模型，常被用来描述现实世界的社交网络。本文首先阐释了ER随机的生成机制，进而引出了WS小世界网络的概念，给出了WS小世界网络的模型。接着通过统计实验得出WS小世界网络的度分布、聚集系数、平均最短路径等统计特性。最后，在实验结果的基础上，对WS小世界网络统计特性做了进一步分析。Abstract:WSsmallworldnetworksisacommonnetworkmodelthatusuallyusedtodescribetherealworldofsocialnetworking.ThispaperfirstexplainsthegenerationmechanismofERrandomgraph，andleadstotheconceptofWSsmallworldnetworks,proposesthemodelofWSsmallworldnetworks.ThenobtainsthedegreedistributionandclusteringcoefficientandaverageshortestpathoftheWSsmallworldnetworksthroughstatisticalexperiments.Finally,basedontheexperimentalresults,theStatisticalcharacteristicsofWSsmallworldnetworkareanalyzedfurther.关键词：WS小世界网络；ER随机图；统计特性Keywords:WSsmallworldnetworks；ERrandomgraph；statisticalcharacteristics：TP311文献标识码：A：1006-4311(2016)04-0226-020引言近年来，复杂网络引起了许多相关领域研究人员的关注。所谓复杂网络就是具有复杂拓扑结构和动力行为的大规模网络，它是由大量的节点通过边的相互连接而构成的1960年匈牙利数学家Erdo’sandR6nyi建立了随机图理论，研究复杂网络中随机拓扑模型(ER)，自此ER模型一直是研究复杂网络的基本模型［1］。但是近年的研究发现：现实中得到的许多试验数据结果与随机图模型并不符合，1998年Watts和Strogtz提出了“小世界”网络模型(WS)［2］，刻画了真实网络所具有的特性。WS网络模型基于ER随机的生成机制，是规则网络到随机网络的过度。现实网络的结构类型极为丰富，以往的研究更多关注了这些网络在统计意义上的共性问题，而实际网络的差异性也是一个值得注意的基本问题［3］。本文将首先阐述ER随机图及WS网络的生成机制，进而通过实验得出WS小世界网络的统计特性(如度分布、聚集系数、平均最短路径等等)，最后基于实验结果分析WS小世界网络独有的图统计特性。1网络模型1.1规则网络规则网络是一种常见的网络，其模型为：网络中任何一个结点，都与其相邻的左右各两个或者N个结点相连接，如1中左边的网络结构。1.2ER随机图模型及WS小世界模型ER随机模型生成机制基于规则网络模型，它将规则网络中任何一条边以概率p进行重连，具体办法是遍历图中所有的结点，将每个节点连接的所有边都以概率p进行重连，若该节点有边需要重连，则从该节点出发，选择非当前边所连结点的另外一个节点进行链接，以此达到网络随机化的目的。如图1所示，如果概率p为0,则所有的边均不需要重连，则网络结构还是规则网络，当概率p逐步从0到1变化，则网络的结构将从规则化逐渐变为随机化，当p迗到1的时候，所有的边都进行了重连，网络就成了完全随机网络，如1右边的网络结构。而当P介于0和1之间时，就形成了小世界网络，许多现有的研究结果表明，现实网络数据大多符合小世界网络的特性。1.3图统计特性度与度分布：度是指网络中结点的连接的边的条数。度分布指的是整个网络中所有的结点的度的分布。聚集系数：聚集系数代表了一个网络的聚集的程度大小。一个结点的聚集系数是指与此结点相连的所有结点之间互相存在的边的数量与这些节点之间可能存在的所有边的数量的比值。平均最短路径：某两个结点之间的最短路径指的是连接这两个点之间的最短通路上的边的数量，整个网络的平均最短路径则指的是任意两点间最短路径的平均值。2统计实验本文实验使用SNAP[4]图分析库生成了一个WS小世界网络，通过实验计算出其度分布、聚集系数、平均最短路径等统计特性。2.1实验环境实验使用的计算机配备了IntelCorei3的CPU,主频为2.5Ghz,内存为4G，硬盘为320G,使用的操作系统为windows7,C++开发环境使用的是Microsoftvisualstudio2012。2.2图统计特性实验实验使用的小世界网络模型是以概率P重连生成的，具体的数据如表1所示。分别对表1中的图数据计算其度分布、聚集系数、最短路径等统计特性，...