小世界网络就在你身边，你了解嘛？| 集智百科

Original 集智百科集智俱乐部 2021-02-09

导语

本文将介绍小世界网络的基本定义以及性质。内容来自集智百科，集智百科是复杂系统领域的百科全书，涵盖复杂系统领域的基本概念（持续完善中）。

我们正在组织撰写翻译相应的维基词条，并附上代码实现。想要自己创建词条，一起贡献知识的小伙伴们可以通过链接报名哦。点击「编辑」，做些改变，按下「保存」，你将影响世界！

什么是小世界网络？

小世界网络是一种数学图。在此类图中，绝大多数节点彼此之间并不相邻，但任一给定节点的邻居们却很可能彼此是邻居，并且大多数节点都可以从任意其他节点，用较少的步或跳跃访问到。具体来说，小世界网络的定义如下：如果网络中随机选择的两个节点之间的距离L（即访问彼此所需要的步数），与网络中节点数量N的对数成比例增长，（即: ），且网络的集聚系数（Clustering Coefficient）不小，那么，这样的网络就是小世界网络。

小世界网络的例子 | 中心比其他节点大 平均度3.833 平均最短路径长度1.803 聚类系0.522

在社交网络中，这种网络属性意味着一些彼此并不相识的人，可以通过一条很短的熟人链条被联系在一起，这也就是小世界现象。许多经验网络图都展示出了小世界现象，例如社交网络、互联网的底层架构、诸如Wikipedia的百科类网站以及基因网络等等。

随机图 | 平均度2.833 平均最短路径长度2.109 聚类系数0.167

1998年，Duncan Watts和Steven Strogatz提出，小世界网络是一类随机图。他们指出，这类网络图可以通过两个独立的结构特征，即集聚系数和平均节点间距离（也称作平均最短路径长度）来进行识别。根据Erdős-Rényi（ER）模型构造的纯随机图，会展现出较小的最短路径长度（通常随着节点数对数值的变化而变化）以及较小的集聚系数。Watts和Strogatz验证了这一点，事实上，现实世界中很多网络的平均最短路径长度都较短，而集聚系数又远高于普通随机图。

“小世界”网络模型

Watts和Strogatz随后提出了一种新的图模型（即现在的Watts-Strogatz模型），该模型具备两个特征：(1)平均最短路径长度较小，(2)集聚系数较大。1999年，Barthelemy和Amaral最先描述出了Watts-Strogatz模型中“大世界”（诸如栅格网络）与小世界的交叉点性质。

在此之后，学界又涌现出了大量的相关研究，其中不乏一些较为精确的度量结果 (Barrat and Weigt, 1999; Dorogovtsev and Mendes; Barmpoutis and Murray, 2010)。 Braunstein发现，对于权值分布非常广的加权ER网络，最佳路径长度会显著增长，其增长速度为。

小世界网络的性质

小世界网络中往往会包含团（cliques）以及临近团（near-cliques）——此处的“团”，指的是内部几乎任意两个节点之间都存在连接的子网络。这遵循高集聚系数的定义属性。其次，大多数节点对之间，都至少存在一条短路径。这遵循平均最短路径较小的定义属性。

许多其他属性，通常也会与小世界网络有所关联。通常情况下，网络中会存在很多的中心（hub）——它们是具有很高连接数的节点（即高度（Degree）节点）。这些中心扮演了公共连接的角色，缩短了其他边之间的短路径长度。通过对比，航空航班的小世界网络，都体现出了较短的平均路径长度（例如，在任意两个城市之间飞行，你通常可能只需要乘坐三程或更少的航班数），因为很多航线都可以通过枢纽城市进行中转。这一属性的分析，通常要考虑网络中，具有相同入度的节点的比例（网络的度的分布）。

网络具有较多中心（hub），意味着度值较大的节点占比会更高，因此，在这种网络的度分布中，高度值分布更高，即俗称的厚尾分布（fat-tailed distribution）。具有不同拓扑结构的图，只要满足上述两个定义，就可以被定义为小世界网络。

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

如果 ,网络即为小世界网络。

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

其中，对于所选受测网络而言，L是特征路径长度，C是集聚系数。是等价栅格网络的集聚系数，而则是等价随机网络的的特征路径长度。

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

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

来源：集智百科
地址：
http://wiki.swarma.net/index.php/%E5%B0%8F%E4%B8%96%E7%95%8C%E7%BD%91%E7%BB%9C#.E4.BD.BF.E7.94.A8.E5.8E.9F.E7.94.9F.E6.96.B9.E6.B3.95x.E7.94.9F.E6.88.90.E5.B0.8F.E4.B8.96.E7.95.8C.E7.BD.91.E7.BB.9C
编辑：孟婕

推荐阅读

小世界网络之父邓肯·瓦茨经典回顾

小世界网络、偏好依附机制、跨学科研究

解读幂律与无标度网络 | 网络科学入门

无标度网络理论之父Barabási回应质疑

理论危机 | 无标度网络遭到史上最严重质疑

点击「编辑」，做些改变，按下「保存」，你将影响世界！

推荐课程

PC端:

https://campus.swarma.org/gcou=10388

集智俱乐部QQ群｜877391004

商务合作及投稿转载｜swarma@swarma.org