WS小世界模型 Watts–Strogatz model

WS小世界模型 Watts–Strogatz model 是一种随机图生成模型，其生成的图具有小世界属性，包括较短的平均节点间距离和高集聚系数。该模型由邓肯 J. 沃茨 Duncan J. Watts和斯蒂文·史楚盖兹 Steven Strogatz在1998年两人联合发表于《自然》的论文中提出 。Watts在其广受欢迎的科学读物《Six Degrees》中使用[math]\displaystyle{ \beta }[/math]来阐述该模型，这之后，该模型也被称为（沃茨）[math]\displaystyle{ \beta }[/math] 模型。

模型基本原理

对Random_graph的正式研究可追溯至 保尔·厄多斯 Paul Erdős和阿尔弗烈德·瑞利 Alfréd Rényi的工作 。他们所考虑的图，也就是现在所谓的经典图或ER随机图模型，给许多应用提供了简单而强有力的模型。

但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性：

1. 不能生成局部集聚 local clustering 和三元闭合 triadic closures(网络有三元闭合、三元闭包等释义）。相反，因为图中两个节点有恒定、随机且独立的概率彼此相连，ER随机图模型的集聚系数较低。
2. 不能解释中心节点 hub 的构成。在形式上，ER随机图模型的度分布收敛于Poisson_distribution ，而不是我们在现实世界中观测到的、无标度网络 scale-free networks 的幂律分布 power law。

WS模型是针对于第一条局限性来设计的最简可能模型。它在解释了集聚的同时保持了ER模型较短的平均节点间距离，这是通过在近似ER图的随机化结构和正则环点阵 regular ring lattice中进行内插得到的。因而，该模型至少能够部分解释许多网络中的“小世界”现象（"small-world" phenomena），比如电网、秀丽隐杆线虫 C. elegans的神经网络、电影演员的社交网络、以及芽殖酵母脂肪代谢的信息交流 。

算法

假设所期望的节点数为[math]\displaystyle{ N }[/math]，平均度为[math]\displaystyle{ K }[/math]（假定K为偶数）和一个特殊的参数[math]\displaystyle{ \beta }[/math] ，满足[math]\displaystyle{ 0\leq \beta \leq 1 }[/math]，且[math]\displaystyle{ N\gg K\gg lnN\gg 1 }[/math]。

该模型以下述方式构建了一个具有[math]\displaystyle{ N }[/math]个节点，[math]\displaystyle{ \frac{NK}{2} }[/math]条边的无向图：

1. 构建一个正则环点阵。该图有[math]\displaystyle{ N }[/math]个节点，每个节点和[math]\displaystyle{ K }[/math]个相邻的节点相连，其中每一侧有[math]\displaystyle{ K/2 }[/math]个。即是，若每个节点用[math]\displaystyle{ n_{0},...,n_{N-1} }[/math]标示，当且仅当[math]\displaystyle{ 0\lt \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2} }[/math]时，存在边[math]\displaystyle{ (n_{i},n_{j}) }[/math]。
2. 对于每个节点[math]\displaystyle{ n_{i}=n_{0},...,n_{N-1} }[/math]，选出其与最右侧第[math]\displaystyle{ K/2 }[/math]相邻节点之间的边，即满足[math]\displaystyle{ n_{i} \lt n_{j} \leq n_{i} + K/2 }[/math]的所有边 [math]\displaystyle{ (n_{i},n_{j}\mod N) }[/math] ，以概率[math]\displaystyle{ \beta }[/math]将其重新连接。重新连接的过程是把边 [math]\displaystyle{ (n_{i},n_{j}\mod N) }[/math] 替换为边 [math]\displaystyle{ (n_{i},n_{k}) }[/math] ，其中[math]\displaystyle{ k }[/math]以一致的随机性从所有可能的节点选出，并且避免出现自回路[math]\displaystyle{ (k\neq i) }[/math]和重复连接（边 [math]\displaystyle{ (n_{i},n_{{k}'}) }[/math] ，其中[math]\displaystyle{ {k}'=k }[/math]，在该算法中不会出现）的情况。

特性

该模型基础的点阵图结构产生了局部集聚的网络，而随机的重新连接则大大减少了平均节点间距离。其算法引入了大约[math]\displaystyle{ \beta \tfrac{NK}{2} }[/math]条非点阵边。改变[math]\displaystyle{ \beta }[/math]的值可以在正则环点阵（[math]\displaystyle{ \beta =0 }[/math]）和接近ER随机图的结构[math]\displaystyle{ (\beta = }[/math][math]\displaystyle{ 1 }[/math]，[math]\displaystyle{ G }[/math][math]\displaystyle{ (N,p) }[/math]满足[math]\displaystyle{ p=\frac {K}{N-1}) }[/math]间进行内插。由于每一个节点都与至少[math]\displaystyle{ K/2 }[/math]个其他节点相连，该模型并没符合真实的ER模型。

我们感兴趣的三个特性是平均节点间距离 average path length、集聚系数 clustering coefficient 和度分布degree distribution。

Watts–Strogatz 小世界模型，由igraph生成，Cytoscape 2.5进行可视化，100个节点

文件:Watts strogatz.svg

Watts_strogatz图

平均节点间距离

• 对于环形点阵，平均节点间距离是[math]\displaystyle{ \ell(0)=N/2K\gg 1 }[/math]，且随系统规模线性变化；

• 对于极限情况[math]\displaystyle{ (\beta \rightarrow 1) }[/math]，该图趋近于随机图，平均节点间距离[math]\displaystyle{ \ell(1)=\frac{lnN}{lnK} }[/math]，但实际上不收敛于此；

• 在区间[math]\displaystyle{ (0\lt \beta \lt 1) }[/math]内，平均节点间距离随着[math]\displaystyle{ \beta }[/math]的增大迅速下降，并很快接近于其极限值。

集聚系数

• 对于环形点阵，集聚系数为[math]\displaystyle{ C(0)=\frac{3(K-2)}{4(K-1)} }[/math]，因此随着K的增大趋向于[math]\displaystyle{ 3/4 }[/math]，且与系统规模无关；
• 对于[math]\displaystyle{ \beta \rightarrow 1 }[/math]的极限情况，集聚系数与经典随机图同阶，[math]\displaystyle{ C=\frac{K}{N-1} }[/math]，与系统规模成反比；区间内的集聚系数则十分接近于正则环点阵的系数值，只有在[math]\displaystyle{ \beta }[/math]相对较大时才会下降，这就导致了在一定区间范围内平均节点间距离下降迅速，而集聚系数保持相对恒定的情形，也就解释了“小世界”现象。
• 如果我们用巴拉特 Barrat和魏格特 Weigt的方法 ，即是用一个节点的相邻节点之间的平均边数和这些相邻节点之间可能的平均边数之商来定义集聚系数[math]\displaystyle{ C'(\beta) }[/math]，或者说:

[math]\displaystyle{ C'(\beta)=\frac{3\times \text{number of triangles}}{\text{number of connected triples}} }[/math]

可得出[math]\displaystyle{ C'(\beta)\sim C(0)(1-\beta)^{3} }[/math]

度分布

• 正则环点阵的度分布即以K为中心的狄拉克[math]\displaystyle{ \delta }[/math]函数，在[math]\displaystyle{ 0\lt \beta \lt 1 }[/math]内的度分布可记为：

[math]\displaystyle{ P(k) = \sum_{n=0}^{f(k,K)} {{K/2}\choose{n}} (1-\beta)^n \beta^{K/2-n} \frac{(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!} e^{-\beta K/2} }[/math]

[math]\displaystyle{ k_{i} }[/math]是第[math]\displaystyle{ i }[/math]个节点的边数或称为度。这里[math]\displaystyle{ k\geq K/2 }[/math]，[math]\displaystyle{ f(k,K)=min(k-K/2,K/2) }[/math]。

• 度分布的形状类似于随机图，在[math]\displaystyle{ k }[/math][math]\displaystyle{ = }[/math][math]\displaystyle{ K }[/math]处取得明显峰值，对于较大的[math]\displaystyle{ \left | k-K\right | }[/math]呈指数衰减。

• 网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。

局限性

该模型的主要局限性是会产生不符实际的度分布。相较而言，现实中的网络通常是非齐次的无标度网络，有中心节点的存在和无标度的度分布。考虑到此，这样的网络可以用偏好依附模型 preferential attachment model来更好的描述，比如BA网络模型。 （另一方面，BA模型没有产生真实网络中出现的高集聚特性，而这个弱点是WS模型所不具备的。因此，WS模型和BA模型均不应被看成是完全符合实际的。）

WS模型也暗含了固定的节点数，所以也不能用来描述网络的生长。

参见

• 小世界网络
• ER随机图模型
• Barabási–Albert模型
• 社交网络

参考文献

---

本中文词条由用户Iceblaze9527参与编译，flynn审校，张江总审校，乐多多编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。