1.3　小世界网络

Watts和Strogatz在分析了规则网络和随机网络后发现:前者不存在短路径，后者缺乏群集性;规则网络是秩序的象征，随机网络是混乱的代表;但现实网络不太可能是这两个极端之一。1967年美国社会心理学家Milgram^[18]通过“小世界实验”提出了“六度分离推断”，即地球上任意两人之间的平均距离为6，也就是说只要中间平均通过5个人，你就能联系到地球上的任何人。随后，一些数学家也对此进行了严格的证明。于是，1998年Watts和Strogatz^[19]在《自然》杂志上发表了一篇开创性的论文，提出了网络科学中著名的小世界网络模型（WS模型），刻画了真实网络所有的大聚簇和短平均距离的特性。小世界网络的基本模型是WS模型，算法描述如下。

① 一个环状的规则网络开始:网络含有N个节点，每个节点向与它最临近的K个节点连出K条边，并满足N≥K≥lnN≥1。

② 随机化重连:以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生pNK/2条长程的边把一个节点和远处的节点联系起来。改变p值可以实现从规则网络（p=0）向随机网络（p=1）的转变。当p=0时，每个节点都有K个邻点，完全没有“随机跳跃边”，显示一个规则网络模型;而在0<p<1时，随机重连边的期望值是pNK（N→∞），显示一个位于规则与随机之间的模型;当p=1时，所有边都随机重连，模型转化为一个ER随机网络模型。

由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，出现孤立的集团，而且不便于理论分析。于是，Newman和Watts^[20]提出了NW小世界网络模型，该模型是通过用“随机化加边”取代WS小世界网络模型构造中的“随机化重连”。NW小世界模型构造算法如下。

① 一个环状的规则网络开始:网络含有N个节点，每个节点向与它最临近的K个节点连出K条边，并满足N≥K≥lnN≥1。

② 随机化加边:以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同节点之间至多只能有一条边，并且每个节点都不能有边与自身相连。改变p值可以实现从最近邻耦合网络（p=0）向全局耦合网络（p=1）转变。当p足够小且N足够大时，NW小世界模型本质上等同于WS小世界模型。