2.2.2 WS小世界网络
由于ER 网络中的两个节点由恒定、随机且独立的概率相连，ER 网络不能生成局部集聚，聚类系数不高。Duncan J.Watts（邓肯J.沃茨）和Steven Strogatz（斯蒂文·史楚盖兹）[36]提出现实世界许多网络比如人际关系网络具有小世界性，即网络有较短的平均节点间距离和较高聚类系数。构造过程如下：
（1）假设网络大小为N，平均度为＜k＞（＜k＞为偶数）；
（2）构建一个环状网络，让图中任一节点与它的＜k＞个邻居相连，节点两侧各有＜k＞/2个邻居节点；
（3）随机化重连，提出一个随机概率p，把网络中的边以概率p 断开，其中一个端点保持不变，另一个端点在网络中随机选择一个节点相连并且避免出现重连和自环。
图2-2给出了不同随机重连概率p 时，WS网络的示例图。可以看出从左到右，网络的聚类系数和平均距离随p 的增加而减小。当p=1时，所有断边重连。(https://www.daowen.com)
图2-2 WS小世界网络演化[36]
WS小世界网络聚类系数和平均距离随p 的变化如图2-3所示。
图2-3 WS小世界网络聚类系数和平均距离随p 的变化
