WS小世界模型

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

模型基本原理

对随机图的正式研究可追溯至 保尔·厄多斯 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]（假定[math]\displaystyle{ K }[/math]为偶数）和一个特殊的参数[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]，在该算法中不会出现）的情况。

构建小世界网络

构建小世界网络的主要机制是Watts-Strogatz机制。

小世界网络也可引入延时，这不仅会产生分形，而且在特定条件下，还会形成混沌，或者在动态网络中转变为混沌。

构造度直径图（Degree–diameter graph）的方法是：网络中每个顶点的邻居数量是有界的，而网络中从任意给定顶点到其他顶点（网络直径）是最小的。构建这样的小世界网络，其实是为寻找临近摩尔边界的图的秩，而做出的一部分努力。

Barmpoutis等人给出的从零开始构建小世界网络的另外一种方法，构建了一种平均距离极小且平均集聚度极高的网络。他们提到了一种复杂度恒定的快速算法，以及不同生成图鲁棒性的度量。根据每个网络的应用，可以从一个这样的“超小世界”网络开始，然后重新连接一些边，或者使用几个这样的小网络作为子图，构筑一个更大的图。

通过双相演化(dual-phase evolution)过程，小世界属性可以在社交网络和其他现实世界系统中自然产生。在顶点之间的连接增长受到时间或空间的制约时，小世界网络尤其常见。该机制通常涉及相位之间的周期性变换，其中，在“全局”阶段——连接建立，而在“本地”阶段——连接被移除。

参考：扩散限制凝聚，模式构成。

构建小世界网络代码实现

使用networkx生成小世界网络

import networkx as nx
import matplotlib.pyplot as plt

# WS network
# 生成20个节点的小世界网络
# 每个节点有四个邻居
# 每条连边以0.3的概率随机重置链接
WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
pos = nx.circular_layout(WS)
nx.draw(WS, pos, with_labels = False, node_size = 30)
plt.show()

此时得到的图片是下图所示:

使用原生方法x生成小世界网络

G = nx.Graph()
node_num = 20
neighbour_num = 4
probility = 0.3
# 节点与邻居相连
for i in range(node_num):
    from_node = i
    for j in range(neighbour_num):
        to_node = (i+j) % node_num - neighbour_num / 2
        if to_node >= 0:
            to_node += 1
        G.add_edge(from_node,to_node)
# 连边随机重连
edges = copy.deepcopy(G.edges())
for edge in edges:
    if random.random() <  probility:
        G.remove_edge(edge[0],edge[1])
        ran_edge = np.random.randint(node_num,size=2).tolist()
        G.add_edge(ran_edge[0],ran_edge[1])
# 绘图
pos = nx.circular_layout(G)
nx.draw(G, pos, with_labels = False, node_size = 30)
plt.show()

此时得到的图片如下图所示：

小世界网络的性质

小世界网络中往往会包含团（cliques）以及临近团（near-cliques）——此处的“团”，指的是内部几乎任意两个节点之间都存在连接的子网络。这遵循高集聚系数的定义属性。其次，大多数节点对之间，都至少存在一条短路径。这遵循平均最短路径较小的定义属性。许多其他属性，通常也会与小世界网络有所关联。通常情况下，网络中会存在很多的中心（hub）——它们是具有很高连接数的节点（即高度（Degree）节点）。这些中心扮演了公共连接的角色，缩短了其他边之间的短路径长度。通过对比，航空航班的小世界网络，都体现出了较短的平均路径长度（例如，在任意两个城市之间飞行，你通常可能只需要乘坐三程或更少的航班数），因为很多航线都可以通过枢纽城市进行中转。这一属性的分析，通常要考虑网络中，具有相同入度的节点的比例（网络的度的分布）。网络具有较多中心（hub），意味着度值较大的节点占比会更高，因此，在这种网络的度分布中，高度值分布更高，即俗称的厚尾分布（fat-tailed distribution）。具有不同拓扑结构的图，只要满足上述两个定义，就可以被定义为小世界网络。

网络的小世界性被量化为一个系数 σ，可以通过比较给定网络与具备相同度分布的等价网络的集聚系数与路径长度，计算得出。

[math]\displaystyle{ \sigma = \cfrac { \frac {C} {C_r} } { \frac {L} {L_r} } }[/math]

如果[math]\displaystyle{ \sigma \gt {1} }[/math]( [math]\displaystyle{ C \gg C_r }[/math]，且[math]\displaystyle{ L \approx L_r }[/math]), 网络即为小世界网络

另一个量化网络小世界性的方法，是利用小世界网络的原始定义，比较给定网络与等价随机网格网络的集聚系数及路径长度。小世界所用的度量（ω）定义如下：

[math]\displaystyle{ \omega = \frac{L_r}{L}-\frac{C}{C_l} }[/math]

其中，对于所选受测网络而言，L是特征路径长度，C是集聚系数。[math]\displaystyle{ C_l }[/math]是等价栅格网络的集聚系数， 而[math]\displaystyle{ L_r }[/math]则是等价随机网络的的特征路径长度。

R. Cohen和Havlin分析出，无标度网络是超小世界。在这种情况下，由于中心的存在，最短路径会变得非常小，并且满足如下关系：

[math]\displaystyle{ L \propto \log{\log N} }[/math]

结果表明，在存在白噪音的小世界网络中，会出现随机同步，这意味着，白噪音有助于系统针对中等噪声强度进行更好地同步，而非减少噪音。这种现象，与白噪音在随机图或无标度网络中的效果形成了鲜明的对比，即应用噪声会降低这些网络中的同步幅度。

局限性

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

网络鲁棒性（Network robustness）

Barabási等研究人员提出假设，认为小世界网络在生物系统中的普遍存在，可能反映了这种结构的进化优势。一种可能性是，小世界网络相比其他网络架构，对扰动的鲁棒性更强。如果这种假设成立，小世界网络将为受到突变或病毒感染损害的生物系统提供优势。

在一个具备遵循幂律分布现象的度分布的小世界网络中，随机删除节点，极少能导致平均最短路径长度显著增加（或集聚系数的显著降低）。这是因为，节点之间的最短路径通过中心点流动，而且，如果一个外围节点被删除，不太可能干扰其他外围节点之间的通路。由于小世界网络中，外围节点的比例要远高于中心的比例，因此，删除重要节点的概率非常低。例如，如果爱达荷州太阳谷的小型机场被关闭，不会增加在美国旅行的其他乘客到达各自目的地所需的平均航次。但是，如果随机删除的节点是中心枢纽，那么平均路径长度就会急剧增加。每年都可以看到，当芝加哥奥黑尔机场等北部枢纽因大雪关闭时，经常会出现这种状况；许多乘客不得不搭乘更多航班，以达到目的地。

相反，在随机网络中，所有节点具有数量大致相同的连接，随机删除节点可能会略微增加平均最短距离，但删除任意节点都会带来这样的影响。从这个意义上来讲，随机网络容易受到随机扰动的影响，而小世界网络则具备鲁棒性。但是，小世界网络容易受到针对中心的攻击，而目标攻击无法对随机网络造成灾难性故障。

病毒已经进化到可以干扰中枢蛋白的活动，诸如p53，并因此产生有利于病毒复制的细胞行为的巨大变化。渗流理论是分析网络鲁棒性的一个有效方法。

特性

该模型基础的点阵图结构产生了局部集聚的网络，而随机的重新连接则大大减少了平均节点间距离。其算法引入了大约[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模型。

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

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

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]呈指数衰减。

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

例子

小世界网络例子

在现实世界的很多现象中，都能够看到小世界属性，这包括网络中的导航菜单、食物网、电网、代谢处理网络(metabolite processing networks)、脑神经网络、选民网络、电话呼叫图、社交影响网络等等。文化网络与单词共现网络也被证明是小世界网络。

相连的蛋白质网络同样具有小世界性质，例如遵从幂律的度分布。类似地还有转录网络，其节点为基因，如果某一个基因对另一个基因有上调或下调的遗传影响，且这些基因彼此相连，这一网络就具有小世界网络的性质。

非小世界网络例子

另一个例子就是人与人之间的“六度分离”理论，这里默认的适用领域是一群在任意时刻都活着的人。阿尔伯特·爱因斯坦与亚历山大大帝之间的分离度，几乎肯定是大于30的，而且这个世界并不具备小世界属性。一个同样不具备小世界性质的网络还有“曾去同一家学校上学”的网络：如果两个人加入某一所大学的时间差了10年，他们不太可能在学生团体中有共同的熟人。

类似的，消息传播过程中必须要通过的中继站点的数量并不总是很小的。回溯到邮件还需要手工投递或骑马寄送的时期，一封信件从它的起点到终点所需要转手的次数，会比现在大上很多。可视电报（约存在于1800-1850年）时代，消息易手的次数，要由两个站点之间是否是在视线连接范围内决定。

如果没有检验隐含假设，可能会对图“望图生义”，偏向于寻找小世界网络（一个例子就是发表性偏倚导致的文件抽屉问题（file drawer））。

应用

社会学应用

小世界网络对社会运动群体的优势在于，它们由于采用了高度互联的节点的过滤设备，因而对变化具有一定的抗性，以及它有效地实现了，在中继信息的同时，保持了连接网络所需的最少链路数”。

William Finnegan在社会学论证提出，小世界网络可直接适用于亲和团体（Affinity Group）理论。亲和团体指的是旨在实现某个较大目标或功能的小型半独立社会运动团体。虽然在节点级别上并没有严格的隶属架构，但作为连接节点的少数高连接性成员，能够通过网络连接组织内的不同群体。这种小世界网络已被证明是一种极其有效的抗议警察行动的组织策略。Clay Shirky认为，通过小世界网络创造的社交网络越大，高连接性结点在网络内的价值就越高。同理可适用于亲和团体模型，即每个团体内只有少数人与外部团体相联系，从而极大提高了灵活性和适应性。这方面的一个实践案例是William Finnegan在概括1999年西雅图世贸组织抗议活动时，所提到的亲和团体中的小世界网络。

地球科学应用

许多研究地质学和地球物理学的网络，已被证明具有小世界网络的特征。在裂缝系统和多空物质中被定义的网络，已经显示出了这些特征。南加州地区的地震网络或许就是一个小世界网络。上述提及的例子所发生的空间尺度大相径庭，也证明了在地球科学中，这一现象不受空间尺度大小所影响，具备尺度不变性（scale invariance）。气候网络或许也可被视作小世界网络，其中的联系具备长度不一的尺度。

计算应用

小世界网络已被用于估算存储于大型数据库中信息的可用性。这种度量方法被称为“小世界数据变换法”数据库链接与小世界网络对齐度越高，用户越有可能在将来提取到信息。这种可用性通常以牺牲存储在同等空间中的信息量为代价来取得。

Freenet和比特币点对点网络已经被证明在模拟中构筑了小世界网络，使得信息的存储和提取，能够随着网络扩展，而有效扩张。

大脑中的小世界网络

大脑中连接与皮层神经元的同步网络都体现出了小世界拓扑结构。

小世界神经元网络可以呈现出短期记忆。Solla等人提出的计算机模型具有两个稳定状态——一种被认为在记忆存储中十分重要的特性（被称为双稳态）。激活脉冲在神经元之间产生自我维持的通信活动循环。第二波脉冲则终止这一活动。脉冲让这一系统在稳定状态间切换：流动（记录“记忆”）以及停滞（保留记忆）。小世界神经元网络也被用于建模，了解病情发作的原理。

在更一般的层次上，大脑中的许多大规模神经网络，例如视觉系统和脑干，都体现出了小世界特性。

参见

• 小世界网络
• ER随机图模型
• BA网络模型
• 社交网络
• 气候网络
• 双相演化（Dual-phase evolution）
• Dunbar数
• Erdős数
• 渗透理论（Percolation theory）
• 无标度网络
• Kevin Bacon的六度理论
• Watts Strogatz模型

参考文献

书籍

• Buchanan, Mark (2003). Nexus: Small Worlds and the Groundbreaking Theory of Networks. Norton, W. W. & Company, Inc. ISBN 0-393-32442-7.
• Dorogovtsev, S.N. & Mendes, J.F.F. (2003). Evolution of Networks: from biological networks to the Internet and WWW. Oxford University Press. ISBN 0-19-851590-1.
• Watts, D. J. (1999). Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton University Press. ISBN 0-691-00541-9.
• Fowler, JH. (2005) "Turnout in a Small World," in Alan Zuckerman, ed., Social Logic of Politics, Temple University Press, 269–287
• Reuven Cohen and Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.

期刊

• Albert, R.; Barabási A.L. (2002). "Statistical mechanics of complex networks". Rev. Mod. Phys. 74: 47–97. arXiv:cond-mat/0106096 Freely accessible. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
• Albert, R.; Barabási A.L. (1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–12. arXiv:cond-mat/9910332 Freely accessible. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342.
• Barthelemy, M.; Amaral, LAN. (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180–3183. arXiv:cond-mat/9903108 Freely accessible. Bibcode:1999PhRvL..82.3180B. doi:10.1103/PhysRevLett.82.3180.
• Dorogovtsev, S.N.; Mendes, J.F.F. (2000). "Exactly solvable analogy of small-world networks". Europhys. Lett. 50: 1–7. arXiv:cond-mat/9907445 Freely accessible. Bibcode:2000EL.....50....1D. doi:10.1209/epl/i2000-00227-1.
• Milgram, Stanley (1967). "The Small World Problem". Psychology Today. 1 (1): 60–67.
• Newman, Mark (2003). "The Structure and Function of Complex Networks". SIAM Review. 45 (2): 167–256. arXiv:cond-mat/0303516 Freely accessible. Bibcode:2003SIAMR..45..167N. doi:10.1137/S003614450342480. pdf
• Ravid, D.; Rafaeli, S. (2004). "Asynchronous discussion groups as Small World and Scale Free Networks". First Monday. 9 (9). doi:10.5210/fm.v9i9.1170. [1]
• R. Parshani, S.V. Buldyrev, S. Havlin (2011). "Critical effect of dependency groups on the function of networks". PNAS. 108: 1007–1010. arXiv:1010.4498 Freely accessible. *Bibcode:2011PNAS..108.1007P. doi:10.1073/pnas.1008404108. PMC 3024657 Freely accessible. PMID 21191103.
• S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–8. arXiv:0907.1182 Freely accessible. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559.

相关链接

• 动态临近网络 Seth J. Chandler, Wolfram展示项目
• 小世界网络词条, Scholarpedia (Mason A. Porter)

编者推荐

书籍推荐

《网络科学导论》封面

网络科学导论第七章小世界网络模型

《网络科学导论》由汪小帆，李翔，陈关荣联袂编著，致力于系统地介绍网络科学的基本概念、思想和方法，使得具有高等数学基础的读者都能够看懂，并具备把网络科学方法用于实际网络分析的能力。为此，本书没有过多地陷入数学和物理推导，而是更为关注网络科学的思维习惯和研究方式。

课程推荐

复杂网络2020

本课程是对复杂性科学的一个概述，包含10个章节，每节都会涵盖复杂系统的一个主要概念。

集智相关文章

从复杂网络小世界、无标度、高聚类特性看新型冠状病毒肺炎

该文章基于复杂网络最基本的三大特点——小世界、无标度、高聚类，来分析新型冠状病毒肺炎这一场突如其来的灾难。

---

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

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