定义
小世界网络(Small-world Network)的概念在1998年由Watts和Strogatz提出，他们把介于规则网络和随机网络之间的网络类型定义为小世界网络[1]。
构建步骤：
- 构建一个环状的规则网络：网络含有N个结点，每个节点向与它最临近的K个节点连出K条边；
- 随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。
当p=0 为规则网络（Regular Network），p=1 为随机网络（Random Network），如图1所示。
图 1 规则网络、小世界网络和随机网络
小世界网络的性质：较大的集群系数和较小的平均路径长度，如下图2所示。
集群系数：衡量某个节点的邻居节点是否也互为邻居的程度；
平均路径长度：任意两个节点之间的最短路径长度的平均值；
图 2 集聚系数C（红色）与平均路径长度L(蓝色)随 p变化
参考文献
[1] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature, 1998, 393(6684): 440.
