什么是小世界网络模型 | 集智百科
1998年，邓肯·瓦茨（ Duncan J. Watts）和他的老师史蒂芬·斯托加茨（Steven Strogatz）在两人联合发表于《Nature》的论文中提出了著名的“小世界网络”理论。同时也提出了WS小世界模型 Watts–Strogatz model。瓦茨在其广受欢迎的科学读物《六度分隔》中使用β来阐述该模型，这之后，该模型也被称为（瓦茨）β 模型。这篇文章重点介绍WS小世界模型，但是我们不妨先了解一下小世界理论。
目录
一、什么是小世界网络？
二、什么是WS小世界网络模型？
三、小世界网络算法
四、小世界网络特性
五、相关学者推介
六、相关资源推介
七、集智百科词条志愿者招募
首先，我们需要了解小世界网络是一种数学图。在这种图中，绝大多数节点之间并不相邻，但任一给定节点的邻居们却很可能彼此相邻，并且大多数任意节点，都可以用较少的步或跳跃访问到其他节点。在社交网络中，这种网络属性意味着一些彼此并不相识的人，可以通过一条很短的熟人链条被联系在一起，这也就是小世界现象。许多经验网络图都展示出了小世界现象，例如社交网络、互联网的底层架构、诸如Wikipedia的百科类网站以及基因网络等等。
具体来说，小世界网络的定义如下：如果网络中随机选择的两个节点之间的距离L（即访问彼此所需要的步数），与网络中节点数量N的对数成比例增长，（即：）且网络的聚集系数（Clustering Coefficient）不小，那么，这样的网络就是小世界网络。
什么是聚集系数
这是图论中的一个概念，是用来描述一个图中的节点之间结集成团的程度的系数。简单来说，是一个节点的邻接点之间相互连接的程度。举例来说，就是生活社交网络中，你的朋友之间相互认识的程度。
当我们了解了以上概念，明白下面的模型就会更加的容易。
二、什么是WS小世界网络模型？
二、什么是WS小世界网络模型？
邓肯·瓦茨和斯蒂芬·斯托加茨提出，小世界网络是一类随机图。他们指出，这类网络图可以通过两个独立的结构特征，即集聚系数和平均节点间距离（也称作平均最短路径长度）来进行识别。
随机图
随机图的“随机”主要体现在边的分布上。一个随机图实际上是将给定的节点之间随机地连上线。举例来说，将一些纽扣散落在地上，并且不断随机地将两个纽扣之间连上一条线，这样就得到一个随机图的例子。不同的随机方式会产生不同的连接，这样就产生了不同的随机图模型。对随机图的正式研究可追溯至保尔·厄多斯（Paul Erdős）和阿尔弗烈德·瑞利（Alfréd Rényi）的工作的工作。他们所考虑的图，也就是现在所谓的经典图或ER随机图模型，给许多应用提供了简单而强有力的模型。ER模型是指在给定n个顶点后，规定每两个顶点之间都有p的概率连起来（0⩽p⩽1），而且这些判定之间两两无关。
图2：二项分布ER模型生成的一个图（p=0.01）
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性：
1.不能生成局部集聚（Local clustering）和三元闭合（Triadic closures）(网络有三元闭合、三元闭包等释义）。相反，图中两个节点有恒定、随机且独立的概率彼此相连，因此ER随机图模型的集聚系数较低。
2.不能解释中心节点（hub）的构成。在形式上，ER随机图模型的度分布收敛于泊松分布（Poisson distribution） ，而不是我们在现实世界中观测到的、无标度网络（Scale-free networks）的幂律分布（Power law）
简单来说，根据ER模型构造的纯随机图，会展现出较小的最短路径长度以及较小的集聚系数。Watts和Strogatz验证了这一点，事实上，现实世界中很多网络的平均最短路径长度都较短，而集聚系数又远高于普通随机图。
WS小世界模型是针对于第一条局限性来设计的最简可能模型。它在解释了集聚的同时保持了ER模型较短的平均节点间距离，这是通过在近似ER图的随机化结构和正则环点阵（regular ring lattice）中进行内插得到的。因而，该模型至少能够部分解释许多网络中的“小世界”现象（"small-world" phenomena），比如电网、秀丽隐杆线虫 C. elegans的神经网络、电影演员的社交网络、以及芽殖酵母脂肪代谢的信息交流 。
三、 小世界网络算法
-
构建一个正则环点阵。该图有N个节点，每个节点和K个相邻的节点相连，其中每一侧有K/2个。即是，若每个节点用 标示，当且仅当
时，存在边
。
对于每个节点
，选出其与最右侧第
相邻节点之间的边，即满足
的所有边
，以概率β将其重新连接。重新连接的过程是把边
，其中k以一致的随机性从所有可能的节点选出，并且避免出现自回路
和重复连接边
，其中
，在该算法中不会出现）的情况。
该模型基础的点阵图结构产生了局部集聚的网络，而随机的重新连接则大大减少了平均节点间距离。其算法引入了大约βNK2条非点阵边。改变β的值可以在正则环点阵（β=0）和接近ER随机图的结构(β=1，G(N,p)满足p=KN−1)间进行内插。由于每一个节点都与至少K/2个其他节点相连，该模型并没符合真实的ER模型。
我们感兴趣的三个特性是平均节点间距离、聚集系数和度分布。
平均节点间距离
对于环形点阵，平均节点间距离是ℓ(0)=N/2K≫1，且随系统规模线性变化；
对于极限情况(β→1)，该图趋近于随机图，平均节点间距离ℓ(1)=lnNlnK，但实际上不收敛于此；
在区间(0<β<1)内，平均节点间距离随着β的增大迅速下降，并很快接近于其极限值。
集聚系数
对于环形点阵，集聚系数[5] 为C(0)=3(K−2)4(K−1)，因此随着K的增大趋向于3/4，且与系统规模无关；
对于β→1的极限情况，集聚系数与经典随机图同阶，C=KN−1，与系统规模成反比；区间内的集聚系数则十分接近于正则环点阵的系数值，只有在β相对较大时才会下降，这就导致了在一定区间范围内平均节点间距离下降迅速，而集聚系数保持相对恒定的情形，也就解释了“小世界”现象。
如果我们用巴拉特A.Barrat和魏格特Weigt的方法[6]，即是用一个节点的相邻节点之间的平均边数和这些相邻节点之间可能的平均边数之商来定义集聚系数C′(β)，或者说：由C′(β)可得出
度分布
正则环点阵的度分布即以K为中心的狄拉克δ函数，在0<β<1内的度分布可记为：
P(k)=∑f(k,K)n=0(K/2n)(1−β)nβK/2−n(βK/2)k−K/2−n(k−K/2−n)!e−βK/2
ki是第i个节点的边数或称为度。这里k≥K/2，f(k,K)=min(k−K/2,K/2)。
度分布的形状类似于随机图，在k=K处取得明显峰值，对于较大的|k−K|呈指数衰减。
网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。
局限性
该模型的主要局限性是会产生不符实际的度分布。相较而言，现实中的网络通常是非齐次的无标度网络，有中心节点的存在和无标度的度分布。考虑到此，这样的网络可以用优先链接模型（preferential attachment model）来更好的描述，比如BA网络模型。（另一方面，BA模型没有产生真实网络中出现的高集聚特性，而这个弱点是WS小世界模型所不具备的。因此，WS小世界模型和BA模型均不应被看成是完全符合实际的。）WS小世界模型也暗含了固定的节点数，所以也不能用来描述网络的生长。
五、知名学者介绍
五、知名学者介绍
邓肯·瓦茨（ Duncan J. Watts）
图4：Duncan J. Watts
邓肯·瓦茨是宾夕法尼亚大学的第23位宾夕法尼亚综合知识大学教授。除了在安那伯传播学院任职，他还在工程与应用科学学院的计算机与信息科学系任教。其对社交网络和集体动力学的研究已经发表在《自然》、《科学》等各类期刊上。2007年，在 Nature 发表了题为《A twenty-first century science》的文章，这成为计算社会科学时代来临的标志之一。
史蒂芬·斯托加茨（Steven Strogatz）
图5：Steven Strogatz
史蒂芬·斯托加茨美国康奈尔大学应用数学系教授，研究方向是动力系统理论、数学生物学和复杂网络理论。是非线性系统研究的专家，尤以其对动力系统同步问题的研究而知名。其研究涉及数理生物学、复杂网络等众多领域。曾荣获麻省理工E.M. Baker 杰出教师奖，康奈尔大学Tau Beta Pi 卓越教师奖，美国JPBM 教师交流奖。1998年在《自然》期刊刊表的《“小世界”网络中的集体动力学》(Collective dynamics of 'small-world' networks)，被视为学习复杂网络的基础，是1998—2008年，该领域引用次数最高的论文。
六、相关资源推荐
《六度分隔》
邓肯·瓦茨的代表作。这本书以作者的亲身经历向我们娓娓道来。不仅有专业性的模型分析，也有对典型的社会现象的分析。对于具有专业背景的读者，书前半部分的对网络科学主要理论模型的介绍，不失为一个了解网络科学的好入口。对于普通读者来说，对于发生在我们身边的社会现象的有趣探讨又很容易让人手不释卷。
复杂性科学导论Introdution to Complexity
https://campus.swarma.org/course/1349
斑图路径
复杂网络分析入门路径
https://pattern.swarma.org/path?id=2
七、百科项目志愿者招募
七、百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由Iceblaze9527、张朔、宋多多参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页:
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
欢迎扫描下方二维码添加负责人加入集智百科团队！
参考资料：
[1]Watts, D. J.; Strogatz, S. H. (1998). "Collective dynamics of 'small-world' networks" (PDF). Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998.
[2]Erdos, P. (1960). "Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
[3] Ravasz, E. (30 August 2002). "Hierarchical Organization of Modularity in Metabolic Networks". Science. 297 (5586): 1551–1555. arXiv:cond-mat/0209244. Bibcode:2002Sci...297.1551R. doi:10.1126/science.1073374. PMID 12202830.
[4] Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). "Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network". PLOS Computational Biology. 11 (5): e1004264.Bibcode:2015PLSCB..11E4264A.doi:10.1371/journal.pcbi.1004264. PMC 4447291. PMID 26020510.
[5]Albert, R., Barabási, A.-L. (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. arXiv:cond-mat/0106096.Bibcode:2002RvMP...74...47A.doi:10.1103/RevModPhys.74.47.
[6]Barrat, A.; Weigt, M. (2000). "On the properties of small-world network models". European Physical Journal B. 13 (3): 547–560. arXiv:cond-mat/9903411. doi:10.1007/s100510050067.
来源：集智百科 编辑：曾祥轩
推荐阅读
商务合作及投稿转载｜[email protected]
◆ ◆ ◆
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！
👇点击“阅读原文”，探索神奇的“小小世界”！