下载文档原格式
小世界网络（SWN）及其在经济管理领域的应用
小世界网络(SWN)及其在经济管理领域的应用
小世界网络(SWN)理论由物理、数学、行为科学和计算机科学等多学科交叉生成,用以说明世界上几乎任何两个人都可以通过中间人用较少的连接联系起来,其典型连接数为6-本文称之为"六度分离".SWN 理论一经使用,势必为经济管理领域带来全新思路,提供一种有效的技术工具,展现出广泛的适用性和广阔的发展前景.本文介绍有关SWN的由来、原理及其在经济管理领域的应用.
作者：田颖杰李南江可申作者单位：南京航空航天大学刊名：世界经济研究 PKU CSSCI英文刊名：WORLD ECONOMY STUDY 年，卷(期)：2001 ""(6) 分类号：关键词：网络结构小世界网络随机网络特征路径长度集团化。
WS小世界网络统计特性研究作者：王洋崔红波来源：《价值工程》2016年第04期摘要：WS小世界网络是一种常见的网络模型，常被用来描述现实世界的社交网络。
本文首先阐释了ER随机图的生成机制，进而引出了WS小世界网络的概念，给出了WS小世界网络的模型。
接着通过统计实验得出WS小世界网络的度分布、聚集系数、平均最短路径等统计特性。
最后，在实验结果的基础上，对WS小世界网络统计特性做了进一步分析。
Abstract： WS small world networks is a common network model that usually used to describe the real world of social networking. This paper first explains the generation mechanism of ER random graph， and leads to the concept of WS small world networks， proposes the model of WS small world networks. Then obtains the degree distribution and clustering coefficient and average shortest path of the WS small world networks through statistical experiments. Finally， based on the experimental results， the Statistical characteristics of WS small world network are analyzed further.关键词：WS小世界网络；ER随机图；统计特性Key words： WS small world networks；ER random graph；statistical characteristics中图分类号：TP311 文献标识码：A 文章编号：1006-4311（2016）04-0226-020 引言近年来，复杂网络引起了许多相关领域研究人员的关注。
小世界效应的网络舆情演化迁移元胞模型小世界网络是具有两个重要特性的网络，第一个特性是“短路径”，即通过少数转发节点，信息可以在网络中快速传递。
第二个特性是“聚集性”，即网络中的节点呈现群集化特征，同一社区内的节点联系紧密，而不同社区间联系相对较少。
小世界效应指的就是这种网络结构的特性，它在各种领域的研究中都有广泛应用。
网络舆情是指由网络传播所引发的针对某一主题或事件的舆论。
随着新媒体的发展，网络舆情已成为现代社会的重要问题之一。
研究网络舆情迁移的元胞模型是网络科学领域的一种重要研究方法，它可以帮助我们理解信息在网络中的传播过程，进而预测社会事件的发展趋势。
本文采用元胞自动机模型进行网络舆情演化迁移的分析，基于小世界网络的结构特点，综合考虑舆情节点的情感倾向、信息传播范围等因素，探究网络舆情演化过程中的关键因素和演化规律。
在模型的设计中，我们将网络中的节点分为三类：负面节点、中立节点和正面节点。
对于每个节点，我们设定其具有一定的个体情感倾向，并给出一个取值范围（-1到1之间）。
模型还考虑到每个节点的邻居节点，即与该节点相连的节点，包括近邻节点（直接相连）和远邻节点（通过其他节点连接）。
这种影响范围的设计是基于小世界网络的“短路径”特性。
在模拟过程中，我们假设负面节点的信息传播效率较高，即一个负面节点可以较快地将负面信息传递给其邻居节点；正面节点的信息传播效率较低；中立节点则不会主动传播信息，只有当其邻居节点传来信息时才会转发。
这是基于对不同节点类型信息传播特性的观察。
通过模拟可以发现，网络舆情的演化过程受到两个因素的影响：情感倾向和信息范围。
当负面节点数量较多、正面节点数量较少时，网络舆情往往呈现负面倾向；当正面节点数量占据优势时，网络舆情会逐渐向正面倾向演化。
在情感倾向相同的情况下，节点与邻居的联系紧密程度也会影响信息的传播效率。
在小世界网络中，有些节点既有短程联系，也有长程联系。
这种联系模式面临的挑战是如何在保证短程联系的同时，加强两个社区间的联系。
小世界模型平均路径长度小世界模型是网络科学中的一个重要概念，它描述了现实生活中许多网络系统的特征。
其中一个重要指标就是平均路径长度，它衡量了网络中两个节点之间的平均距离。
本文将围绕小世界模型平均路径长度展开讨论，介绍小世界现象、小世界网络的生成机制以及平均路径长度的计算方法。
一、小世界现象小世界现象是指在许多实际网络中，节点之间的平均距离相对较小，远远小于节点总数。
这意味着网络中的节点之间存在着短路径，人们可以通过少数的步骤就能够相互联系。
小世界现象的典型代表是社交网络，比如Facebook、微信等。
在这些社交网络中，我们可以通过共同的朋友或者兴趣爱好迅速找到彼此。
二、小世界网络的生成机制小世界网络的生成机制主要包括随机连接和局部重连两个过程。
首先，随机连接阶段，网络中的节点随机地与其他节点建立连接，形成一个随机网络。
然后，在局部重连阶段，节点会重新连接到与其距离较近的节点，以形成更为紧密的联系。
通过这两个过程的迭代，网络中形成了许多短路径，从而呈现出小世界现象。
三、平均路径长度的计算方法平均路径长度是衡量小世界网络结构特征的一个重要指标。
它表示网络中任意两个节点之间的平均距离。
计算平均路径长度的方法是首先计算网络中每对节点之间的最短路径长度，然后将这些最短路径长度进行平均。
在大型网络中，计算所有节点对之间的最短路径长度是不现实的，因此可以使用一种近似的方法，例如随机选取一部分节点对进行计算，然后将结果进行平均。
四、小世界模型在实际中的应用小世界模型不仅仅是对网络结构的一种描述，它也广泛应用于各个领域。
在社交网络中，小世界模型可以用来解释信息传播的速度和路径选择；在物理学领域，小世界模型可以用来研究粒子之间的相互作用；在生物学领域，小世界模型可以用来研究蛋白质相互作用网络等。
总结：小世界模型平均路径长度是衡量网络中节点之间距离的重要指标。
小世界现象描述了许多实际网络中的特征，而小世界网络的生成机制包括随机连接和局部重连两个过程。
经典网络仿真一．WS与NW小世界模型1.WS小世界模型构造算法：（1）从规则图开始：给定一个含有N个节点的环状最近邻耦合网络，其中的每个节点都与它左右相邻的各K/2个节点相连，K为偶数。
（2）随机化重连：以概率p随机的重新连接网络中的原有的每一条边，即把每一条边的一个端点保持不变，另外一个端点改取网络中随机选择的另外的一个端点，其中规定不可以有自边和重边。
2. NW小世界模型构造算法：（1）从规则图开始：给定一个含有N个节点的环状最近邻耦合网络，其中的每个节点都与它左右相邻的各K/2个节点相连，K为偶数。
（2）随机化重连：以概率p随机在随机选取的NK/2对节点之间添加边其中规定不可以有自边和重边。
3. WS与NW小世界网络仿真结果（N=1000，K/2=5）(a)(b) (c)图1.(a)WS小世界的平均最短路径和聚类系数归一化处理后的曲线；(b)平均最短路径曲线；(c)聚类系数曲线由图可知，小世界网络具有较高的聚类系数与较短的平均路径长度。
图2.p=0，0.5，1时的WS模型构建示意图由图可知，随着重连概率的增大，网络由规则图转化为随机图。
图3.p=0.1，0.4，0.8，1.0时的WS度分布图由图可知，WS模型度分布呈现泊松分布，且中心在K=10处，几乎不变。
图4.p=0，0.5，1时的NW模型构建示意图图5.p=0.1，0.4，0.8，1.0时的WS度分布图由图可知，NW模型度分布也呈现泊松分布，但中心在随着p增大往右侧偏移。
二．BA无标度网络模型1. BA无标度网络模型构造算法：（1）增长：从一个具有m0个节点的连通网络开始，每次引入一个新的节点,并且连到m 个已经存在的节点上，这里m≤m0。
（2）优先连接：一个新的节点与一个已经存在的节点i相连的概率p i与节点i的度k i之间满足关系：p i=k i/Σk i。
2. BA无标度网络模型仿真结果（N=5000,m=m0=3，6，9）(a)m=m0=3(b)m=m0=6(c)m=m0=9图6. (a)(b)(c)(d)分别为m=m0=3，6，9的度分布图和双对数坐标下的图由图可知，BA无标度网络的度分布是呈指数衰减的，在双对数坐标下度分布近似为一条直线。
收稿日期：2018-01-10基金项目：2017年安徽高校省级重点自然科学研究项目（KJ2017A859）.作者简介：葛伟伦，安徽合肥人，安徽财贸职业学院讲师；房丙午，博士，安徽财贸职业学院教授（安徽合肥230601）.计算机及其应用2018年第2期第39卷总第277期（自然科学）学报小世界网络模型分析和算法模拟葛伟伦，房丙午摘要：首先对小世界网络模型的构建过程和主要统计量进行分析，基于一个规则环状网给出算法描述和代码实现小世界网络模型的模拟，设计代码计算此模型的最短路径平均长度和集聚系数，通过运行代码获得的统计数据进一步验证和分析了小世界网络模型的内在特征和规律，为模拟实现具有大规模节点的小世界网络提供可能.关健词：小世界网络；集聚系数；最短路径平均长度；算法模拟中图分类号：TP311文献标识码：A文章编号：1008-7974（2018）02-0056-05DOI ：10.13877/22-1284.2018.04.014当前对复杂网络的研究引起了各国学者的高度关注和重视，复杂网络是对现实世界复杂系统的抽象和概括，该网络是由大量节点相互连接而成，网络规模大，网络拓扑结构复杂且动态变化.现实生活中的人际关系网、因特网、万维网、电子邮件网、食物链网等都属于复杂网络.把各种类型的复杂网络抽象成具体模型是研究复杂网络最好的方式，近年提出的小世界网络模型能真实深刻地揭示复杂网络背后隐藏的客观规律和属性特征［1-2］.1小世界网络模型1998年Watts 、Strogat 提出的WS 小世界网络模型和Newman 、Watts 提出的改进NW 小世界网络模型能真实反映复杂网络的特征与规律［3-4］.WS 小世界网络模型建模过程：从某个含有N 个节点的规则环状网开始，m 为节点的度且为偶数，每个节点都与它左右邻接的各m /2个节点相连，然后进行随机化重连，将边的一个端点保持不变，另一个端点随机选择规则网中的另一个节点进行连接，满足节点之间只有一条边，并去除自连接.在WS 小世界网络模型中，p =0对应于完全规则网，p =1则对应于完全随机网，通过调节p 的值可以控制从完全规则网到完全随机网的变化，如图1所示.图1随机化重连Newman 和Watts 进一步提出了NW 小世界网络模型，该模型用随机化加边取代WS 模型的随机化重连，避免了构造过程孤立节点的产生.葛伟伦，等小世界网络模型分析和算法模拟NW 小世界网络模型建模过程：从某个含有N 个节点的规则环状网开始，m 为节点的度且为偶数，每个节点都与它左右邻接的各m /2个节点相连，然后进行随机化加边，以概率p 在随机选取的一对节点之间加上一条边，满足节点之间只有一条边，并去除自连接.NW 小世界网络模型中，p =0对应于完全规则网，p =1是规则网和随机网的叠加，如图2所示.图2随机化加边2小世界网络特征统计量分析［5-6］2.1最短路径平均长度最短路径平均长度是小世界网络重要的特征值，这里最短路径指的是从一节点到另一节点经过的边的最小数目，整个网络最短路径平均长度为所有节点最短路径长度的平均值.设N 为节点数，d i ,j 为两个不同节点间的最短路径长度，最短路径平均长度L avg 的计算公式为：Lavg ＝2∑d i ,jN (N -1)i >j >02.2集聚系数集聚系数是反映小世界网络集团化程度的特征量，集团中的成员相互紧密联系，依赖性强.节点i 的集聚系数能表示网络中与该节点直接相连接的其他节点之间的连接紧密度，k i 表示与节点i 直接连接的节点数，e i 表示与节点i 相连接的节点间实际存在的连接边，k i (k i -1)/2表达式为k i 个节点间理论上存在的最大连接边，则节点i 的集聚系数C i 表示为：C i =2e ik i (k i -1)（0<i >N ，N 为网络节点数）则整个网络的集聚系数C 定义为所有节点集聚系数的平均值，表示为：C ＝∑C iN3小世界网络模型的算法模拟和分析［7-8］3.1算法描述根据上文分析，以WS 小世界网络模型为例设计算法实现模拟，首先假设一个环状规则网络有N 个节点，每个节点与最近邻的k 个节点相连，本次模拟网络规模较小，设置N =20，k =4，不改变边和节点的数目.重连概率用随机函数产生一个0到1之间的随机数θ来表示，θ=rand （），假设随机化重连的概率为0.1，当产生的随机数θ<0.1就进行重连，否则不重连；重连过程中随机选择重连对端节点，通过随机函数产生一个在1到N 范围内的随机整数m ，表达式为1+int （rand （）*（N-1）），m 代表随机重连的节点编号，若m 恰好等于原节点编号，就重新产生一次，即再产生一个随机数.算法如下.首先，随机选择一个节点，当θ<0.1时按顺时针方向把连接它和它最近的那个节点的边重新连接到环状网上的其他对端节点，对端节点编号随机产生，θ>=0.1不进行重连.然后，同样按顺时针方向把连接它和它第二近的那个点的边以随机概率θ是否大于0.1判断是否重新连接到环状网上的其他对端节点，重复此过程直到此节点的所有边都按随机概率θ大小重新遍历一遍.最后，轮换到下一个节点重复（1）和（2）步骤，直至N 个节点都按相同方式遍历所有节点结束.3.2算法代码实现（1）通过以下算法代码生成规则环状网，如图3所示，矩阵中“1”表示有边连接两个不同节点，”0”表示无边连接节点.//以下代码实现规则边n =Val （Text1.Text ）：k =Val （Text2.Text ）For i =1To n For j =1To k /2If i +j >n Then edge （i ，j ）=i +j -nElse edge （i ，j ）=i +jEnd IfNext j2018年第2期（自然科学）学报For j =k /2+1To k If i -j +k /2<=0Then edge （i ，j ）=i -j +k /2+n Elseedge （i ，j ）=i -j +k /2End IfNext jNext i//以下代码实现规则矩阵For i=1To n ：For j =1To k edge2（i ，edge （i ，j ））=1Next ：Next图3N =20，k =4规则环状网（2）通过以下算法代码使用随机化重连生成小世界网络模型，如图4所示.观察矩阵，可看出其中一些边在满足概率p 条件下已经重新连接，不过因为重连的概率（p <0.1）不大，所以很多边保持不变，这使得每个节点与其周围邻居节点关系较规则网络变化不大，聚类系数仍然保持在一个较大的数值，但因为生成了一些长路径加强了远距离节点的连接，从而使得整个小世界网络最短路径平均长度明显减小.//确定随机矩阵Private Sub pp （edge3（）As Integer ，pp As Single ，nn As Long ，ka As Integer ）For j =1To ka /2For i =1To nn r =RndIf r <=pp ThenIf i +j >nn Then jj =i +j -nn Else jj =i +j edge3（i ，jj ）=0：edge3（jj ，i ）=0//随机消边a =0：ReDim a1（nn ）//随机连边For ii =1To nn If edge3（i ，ii ）=0ThenIf i <>ii Then a =a +1：a1（a ）=ii End IfEnd IfNextr1=Int （Rnd *a ）+1edge3（i ，a1（r1））=1edge3（a1（r1），i ）=1End IfNext Next End Sub图4N =20小世界网络模型（3）通过以下算法代码统计小世界网络模型最短路径平均长度.Private Function lount （si As Long ，nn As Long ，edgee （）As Inte ⁃ger ）As Singlea =nn -1：dd =1：linkk （1）=si ：e （si ）=10Do While a <>0c =c +1For i =1To dd ：For j =1To nn If edgee （linkk （i ），j ）=1Then If e （j ）<>10Thend =d +1：link （d ）=j ：b （c ）=b （c ）+1e （j ）=10：a =a -1End If ：End IfNext ：Nextdd =d ：d =0If dd =0Then MsgBox （"有节点未连接"）：Exit FunctionEnd IfFor i =1To dd ：linkk （i ）=link （i ）：link （i ）=0：NextLoopFor i =1To c ：lount =lount +i *b （i ）：s =s +b （i ）：Next lount =lount /（nn -1）End Function（4）通过以下算法代码统计小世界网络模型聚类系数值.Private Function find （ni As Long ，no As Long ，eedge （）As Integer ）葛伟伦，等小世界网络模型分析和算法模拟As DoubleReDim a1（no）For i=1To noIf eedge（ni，i）=1Then：aa=aa+1a1（aa）=i：End IfNextFor i=1To aaFor j=1To aaIf eedge（a1（i），a1（j））=1Thenff=ff+1：End IfNextNextSelect Case aaCase0：find=0Case1：find=0Case Else：find=ff/（aa*（aa-1））End SelectEnd Function3.3统计数据分析本次网络规模较大，取节点数N=1000，每个节点的度k=20，依据上面统计特征值代码计算规则环状网的最短路径平均长度L=50.45045，聚类系数C=0.6666667.现在以15个不同的概率P从小到大进行随机化重连构建WS小世界网络模型，依据上文算法计算最短路径平均长度和聚类系数值，对每次取的概率P模拟运算20组数据求出统计量平均值，概率P、平均聚类系数avsc、最短路径平均长度avsl如表1所示.可以看出随着随机化重连概率P的增加，连接节点的长路径增多，使最短路径平均长度从44.83816急剧减小4.413377，但聚类系数缓慢变小，变化幅度从0.6663419缓慢减小到0.4872532，完全符合复杂网络的小世界特性和高聚类特性.对最短路径平均长度和聚类系数进行归一化处理，获得的统计结果如图5所示，图中L（P）和C（P）表示以不同的概率p得到的小世界网络平均最短路径长度和聚类系数，L（0）和C（0）表示规则环状网的最短路径长度和聚类系数，用L（0）和C（0）对L（P）和C（P）进行归一化处理.展示了最短路径长度和聚类系数随概率P变化的曲线图.可以得出这样结论：在概率P处于0.01~ 0.02附近，最短路径平均长度已经很小，但聚类系数仍然很大，符合小世界网络特征，现实世界中很多复杂网络系统从诞生、形成、发展和消失和算法模拟生成的小世界网络特征和规律完全吻合［9］.表1P和avsc、avsl的平均值p（1）=0.0002p（2）=0.0004p（3）=0.0006p（4）=0.0008p（5）=0.001p（6）=0.002p（7）=0.004p（8）=0.006p（9）=0.008p（10）=0.01p（11）=0.02a（12）=0.04p（13）=0.06p（14）=0.08p（15）=0.1avsc（1）=0.6663419avsc（2）=0.6656905avsc（3）=0.665625avsc（4）=0.6653495avsc（5）=0.6644472avsc（6）=0.6624835avsc（7）=0.6587855avsc（8）=0.6556028avsc（9）=0.6519706avsc（10）=0.647175avsc（11）=0.6289542avsc（12）=0.5918728avsc（13）=0.5539923avsc（14）=0.5247461avsc（15）=0.4872532avsl（1）=44.83816avsl（2）=36.31089avsl（3）=34.88402avsl（4）=32.43476avsl（5）=25.15813avsl（6）=19.19243avsl（7）=13.5335avsl（8）=11.44449avsl（9）=10.03519avsl（10）=8.877937avsl（11）=6.902753avsl（12）=5.56514avsl（13）=4.971393avsl（14）=4.670202avsl（15）=4.413377图5最短路径平均长度和聚类系数随P变化情况4结语对WS和NW小世界网络模型建模过程进行分析，并阐述了最短路径平均长度和集聚系数特征值的意义，基于一个规则环状网设计算法和代码模拟了小世界网络模型的形成，并解决了重连概率θ和对端节点选择的随机产生问题；并设计和运行代码获得最短路径平均长度和集聚系数特征值的统计数据，验证和分析了小世界网络的内在特性，使模拟大规模的小世界网络成为可能.参考文献：［1］王小帆，李翔，陈关荣.复杂网络理论及应用［M］.北京：清华大学出版社，2006.［2］周涛，张子柯，等.复杂网络研究的机遇和挑战2018年第2期（自然科学）学报［J ］.电子科技大学学报，2014，43（1）：1-5［3］程学旗，沈华伟.复杂网络的社区结构［J ］.复杂系统与复杂性科学，2011，8（1）：57-66.［4］郭雷，许晓鸣.复杂网络［M ］.上海：上海科技教育出版社，2010.［5］刘常昱，胡晓峰，司光亚，等.基于小世界网络的舆论传播模型研究［J ］.系统仿真学报，2006，18（12）：3608-3611.［6］李果，高建民，高智勇，等.基于小世界网络的复杂系统故障传播模型［J ］.西安交通大学学报，2007，41（3）：334-338.［7］王波，王万良，等.WS 和NW 两种小世界网络模型的建模及仿真研究［J ］.浙江工业大学学报，2009，37（2）：179-188.［8］杨晓光，朱保平.基于复杂网络的社区发现算法［J ］.南京理工大学学报，2016，40（3）：267-271.［9］肖维民，张赛.k 错线性复杂度的分布研究［J ］.吉林师范大学学报，2016（2）.（责任编辑：王前）Analysis and Algorithm Simulation of Small World Network ModelGE Wei-lun ，FANG Bing-wu（Anhui Finance &Trade Vocational College ，Hefei ，Anhui 230601，China ）Abstract ：Firstly ，the modeling process and main statistics of small world network model are analyzed.Then ，based on a regular ring network ，the algorithm description and code are given to simulate the small world network model ；and the code to calculate the average length of shortest path and clustering coefficient is designed ，the internal characteristics and rules of small world network model are fur ⁃ther verified and analyzed through the operation code to obtain statistical data.It is possible to sim ⁃ulate the small world network of large-scale nodes.Key Words ：Small World Network ；clustering coefficient ；average length of the shortest path ；algorithm simu ⁃lation。
关于小世界网络的文献综述一，小世界在P2P网络方面的研究Small-World模型 (也称 W-S 模型 )是由 W atts和 Strogatz于 1998年在对规则网络和随机网络的研究的基础上提出的。
从本质上说 , W-S模型网络是具有一定随机性的一维规则网络。
W -S模型中定义了两个特征值:(1)特征路径的平均长度 L:它是指能使网络中各个节点相连的最少边长度的平均数 ,即小世界网络的平均距离 ;(2)聚类系数 C:表示近邻节点联系紧密程度的参数。
Scale-F ree网络 ,又称无标度网络。
这类网络中，大多数节点的连接度都不大 ,只有少数节点的连接度很高 ,可以将这些少数节点看成中心节点。
这样的节点一般连接不同的区域, 是重要节点 (或称关键节点 ), 起着簇头的作用。
它们使网络通信范围更广, 可用资源更丰富 , 查询和搜索效率更高。
Barabási和 A lbert (BA)等人研究发现节点的连接具有偏好依附的特性。
因此 ,网络规模随着新节点的加入而增大,但新加入的节点偏向于连接到已存在的具有较大连接度的节点上去。
简要介绍了Small-World模型和Scale-Free模型, 详细介绍了小世界现象在P2P网络中资源搜索以及网络安全方面可能的3个应用点, 并提出了一种基于“小世界现象”的高效的资源搜索策略———关键节点资源搜索法。
该搜索法将中央索引模型和泛洪请求模型相结合, 一方面增强了可伸缩性和容错性, 另一方面避免了消息泛滥, 使得搜索效率明显增强。
二、小世界网络概念方面的研究Watts和Strogatz开创性的提出了小世界网络并给出了WS小世界网络模型。
小世界网络的主要特征就是具有比较小的平均路径长度和比较大的聚类系数。
所谓网络的平均路径长度，是指网络中两个节点之间最短路径的平均值。
聚类系数被用来描述网络的局部特征，它表示网络中两个节点通过各自相邻节点连接在一起的可能性，以及衡量网络中是否存在相对稳定的子系统。
小世界网络MATLAB建模1.简介小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。
在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。
若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。
在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。
小世界网络就是对这种现象的数学描述。
用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。
除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。
许多经验中的图可以用小世界网络来作为模型。
因特网、公路交通网、神经网络都呈现小世界网络的特征。
小世界网络最早是由邓肯·瓦茨（Duncan Watts）和斯蒂文·斯特罗加茨（Steven Strogatz）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS模型），这也是最典型的小世界网络的模型。
由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW小世界网络模型，该模型是通过用“随机化加边”模式来取代WS小世界网络模型构造中的“随机化重连”。
在考虑网络特征的时候，使用两个特征来衡量网络：特征路径长度和聚合系数。
特征路径长度（characteristic path length）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。
这是网络的全局特征。
聚合系数(clustering coefficient)：假设某个节点有k个边，则这k条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。
大量的实证研究表明，许多真实网络都具有小世界效应，有的甚至具有所谓的超小世界效应，小世界网络模型正是模拟了真实网络的这一特点。
1998年Watts和Strogatz提出了一种小世界网络模型（WS)的构造方法：对规则网络中每一个节点的所有连边，以一定的概率P断开一个端点，然后重新连接到其他任意一节点上，如图2．1。
当重连概率P=0时，网络是一个规则网络；P=1时形成的网络为完全随机网络；当0<P<1时，形成的网络为小世界网络。
小世界网络是介于完全规则网络和完全随机网络之间的网络，既具有与规则网络类似的类聚特性，又具有与随机网络类似的较小的平均路径长度，即同时具有大的簇团系数和小的平均最短距离。
对WSd"世界网络统计特性模拟研究的结果如图2．3所示，当P=0等于零时，即对于规则网络来说，簇团系数C(P)和最短距离，(p)都较大，当P=l时，即对于随机网络来说，系统的簇团系数和最短距离都较小，而存在一个很大的P的区域，系统同时具有大的簇团系数和较小的最短距离，此即是世界效应。
WS小世界网络的构造，P=0时，是一规则网络，P=1时是完全随机网络，0<P<1时，是一小世界网络，同时具有固定连边和长程随机连边。
随着对网络研究的深入，人们发现真实网络在许多性质上与随机网络仍然有比较大的差别。
在现实世界中很多网络并不能抽象成为规则网络，也不能抽象成为随机网络，而是一种介于规则网络和随机网络之间的一种网络。
这些网络存在我们称之为“小世界效应”的特性。
对于“小世界效应’’的研究可以追溯到1967年。
在那一年，著名的心理学家Mil掣锄在HaⅣard大学做过一个简单的实验。
这个实验的过程可以进行如下简述：Mil孕锄随机的将一些信件分发给内布拉斯加少}I(Nebraska)的一些实验参与者，这些信件的送往的目的地是马萨诸塞州(Massachusetts)的首府波士顿(Boston)(之所以这么选择，是因为Mil留am认为这两个地方相距甚远)。
课题：WS小世界网络模型构造姓名赵训学号 2班级计算机实验班一、WS 小世界网络简介1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型。
实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较大的聚类系数) 。
传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER 随机网络具有小世界特性但却没有高聚类特性。
因此这两种传统的网络模型都不能很好的来表示实际的真实网络。
Watts 和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特性和聚类特性,可以很好的来表示真实网络。
二、WS小世界模型构造算法1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。
2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。
其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如图a所示。
图a相应程序代码（使用Matlab实现）ws_net.m （位于“代码”文件夹内）function ws_net()disp('WS小世界网络模型')N=input('请输入网络节点数');K=input('请输入与节点左右相邻的K/2的节点数');p=input('请输入随机重连的概率');angle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(angle);y=100*sin(angle);plot(x,y,'r.','Markersize',30);hold on;%生成最近邻耦合网络；A=zeros(N);for i=1:Nif i+K<=Nfor j=i+1:i+KA(i,j)=1;endelsefor j=i+1:NA(i,j)=1;endfor j=1:((i+K)-N)A(i,j)=1;endendif K<ifor j=i-K:i-1A(i,j)=1;endelsefor j=1:i-1A(i,j)=1;endfor j=N-K+i:NA(i,j)=1;endendenddisp(A);%随机化重连for i=1:Nfor j=i+1:Nif A(i,j)==1pp=unifrnd(0,1);if pp<=pA(i,j)=0;A(j,i)=0;b=unidrnd(N);while i==bb=unidrnd(N); endA(i,b)=1;A(b,i)=1;endendend%根据邻接矩阵连线for i=1:Nfor j=1:Nif A(i,j)==1plot([x(i),x(j)],[y(i),y(j)],'linewidth',1); hold on;endendendhold offaver_path=aver_pathlength(A);disp(aver_path);对应输出（取网络节点数N=16，K=2；p分别取0，0.1，1）。
p=0（ws_n=16_k=2_p=0.fig的截图）P=0.1（ws_n=16_k=2_p=0.1.fig的截图）p=1（ws_n=16_k=2_p=1.fig的截图）输出结果与图a(图a位于第2页)吻合。
三、WS小世界网络模型平均路径长度L(p)与聚类系数C(p)归一化图平均路径长度平均路径长度也称为特征路径长度或平均最短路径长度，指的是一个网络中两点之间最短路径长度（或称距离）的平均值。
从一个节点s i出发，经过与它相连的节点，逐步“走”到另一个节点s j所经过的路途，称为两点间的路径。
其中最短的路径也称为两点间的距离，记作。
而平均路径长度定义为：这其中N是节点数目，并定义节点到自身的最短路径长度为0。
如果不计算到自身的距离，那么平均路径长度的定义就变成：集聚系数集聚系数（也称群聚系数、集群系数）是用来描述图或网络中的顶点（节点）之间结集成团的程度的系数。
具体来说，是一个点的邻接点之间相互连接的程度。
例如在社交网络中，你的朋友之间相互认识的程度。
一个节点s i的集聚系数C(i) 等于所有与它相连的顶点相互之间所连的边的数量，除以这些顶点之间可以连出的最大边数。
显然C(i) 是一个介于0与1之间的数。
C(i) 越接近1，表示这个节点附近的点越有“抱团”的趋势。
介于随机与规则之间对于纯粹的规则网络，当其中连接数量接近饱和时，集聚系数很高，平均路径长度也十分短。
例如完全耦合网络，每两个节点之间都相连，所以集聚系数是1，平均路径长度是1。
然而，现实中的复杂网络是稀疏的，连接的个数只是节点数的若干倍（），远远不到饱和。
如果考虑将节点排列成正多边形，每各节点都只与距离它最近的 2K个节点相连，那么在K比较大时，其集聚系数为：虽然能保持高集聚系数，但平均路径长度为：平均路径长度与节点数成正比。
纯粹的随机网络（如ER随机网络模型）有着很小的平均路径长度，但同时集聚系数也很小。
可是现实中的不少网络虽然有很小的平均路径长度，但却也有着比随机网络高出相当多的集聚系数。
因此瓦茨和斯特罗加茨认为，现实中的复杂网络是一种介于规则网络和随机网络之间的网络。
他们把这种特性称为现实网络的小世界特性，就是：1.有很小的平均路径长度：在节点数N很大时，平均路径长度近似于2.有很高的集聚系数：集聚系数大约和规则网络在同一数量级，远大于随机网络的集聚系数。
图bWS模型的集聚系数C（红色）与平均路径长度L(蓝色)随p变化的图像相应程序代码（使用Matlab实现）ws.m （位于“代码”文件夹内）clc;clear all;format long;n=1000;k=5;L=zeros(14,20);C=zeros(14,20);for i=1:14p(15-i,1)=1/2^(i-1);end% p=zeros(1,14);% p1=zeros(14,20);% LWS=zeros(14,1);% CWS=zeros(14,1);%%生成最近邻耦合网络A=zeros(n);for i=1:nfor j=i+1:i+kjj=j;if j>njj=mod(j,n);endA(i,jj)=1; A(jj,i)=1;endend%%计算平均路径长度L(0)D1=A;D1(find(D1==0))=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为inf，自身到自身的距离为0.for i=1:nD1(i,i)=0;endm=1;while m<=n %Floyd算法求解任意两点的最短距离for i=1:nfor j=1:nif D1(i,j)>D1(i,m)+D1(m,j)D1(i,j)=D1(i,m)+D1(m,j);endendendm=m+1;endL0=sum(sum(D1))/(n*(n-1)); %平均路径长度%%计算聚类系数C(0)Ci0=zeros(n,1);for i=1:naa1=find(D1(i,:)==1); %寻找子图的邻居节点if isempty(aa1)Ci0(i)=0;elsem1=length(aa1);if m1==1Ci0(i)=0;elseB1=D1(aa1,aa1); % 抽取子图的邻接矩阵Ci0(i)=length(find(B1==1))/(m1*(m1-1));endendendC0=mean(Ci0);for z=1:14% p(z)=1/2^(z-1);for g=1:20%%生成最近邻耦合网络B=zeros(n);for i=1:nfor j=i+1:i+kjj=j;if j>njj=mod(j,n);endB(i,jj)=1; B(jj,i)=1;endend%随机化重连% for i=1:n% p_rand=rand(1,1);% b=find(B(i,:)==1);% for j=1:length(b)% j1=b(j);% if p_rand<p(z,1) %% 生成的随机数小于p，则边进行随机化重连,否则，边不进行重连% B(i,j1)=0;B(j1,i)=0;% bb=randint(1,1,[1,n]);% if B(i,bb)==0&&B(bb,i)==0&&bb~=i %重连条件% B(i,bb)=1;B(bb,i)=1;% end% end% end% endfor i=1:nfor j=1:kp_rand=rand(1,1);if p_rand<p(z,1)bb=randint(1,1,[1,n]);if B(i,bb)==0&&B(bb,i)==0&&bb~=i %重连条件j2=j+i;if j2>nj2=mod(j2,n);endB(i,j2)=0;B(j2,i)=0;B(i,bb)=1;B(bb,i)=1;endendendend%%计算平均路径长度aver_L% n1=size(A,2);D=B;D(find(D==0))=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为inf，自身到自身的距离为0.for i=1:nD(i,i)=0;endm2=1;while m2<=n %Floyd算法求解任意两点的最短距离for i=1:nfor j=1:nif D(i,j)>D(i,m2)+D(m2,j)D(i,j)=D(i,m2)+D(m2,j);endendendm2=m2+1;end% if length(infline)>0% D(infline,:)=[];% D(:,infline)=[];% n2=size(D,2);% L(z,g)=sum(sum(D))/(n2*(n2-1));%求出平均路径% elseL(z,g)=sum(sum(D))/(n*(n-1));%求出平均路径% end%%计算聚类系数aver_CCi=zeros(n,1);for i=1:naa=find(D(i,:)==1); %寻找子图的邻居节点if isempty(aa)Ci(i)=0;elsem3=length(aa);if m3==1Ci(i)=0;elseBB=D(aa,aa); % 抽取子图的邻接矩阵Ci(i)=length(find(BB==1))/(m3*(m3-1));endendendC(z,g)=mean(Ci);endendfigureLWS=mean(L,2);CWS=mean(C,2);semilogx(p,LWS/L0,'ro');hold on;semilogx(p,CWS/C0,'b*');对应输出(ws.fig的截图)与图b（图b位于第7页）吻合四、结论在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达（本文只讨论WS小世界模型）。
