交通地理学与网络科学/小世界网络

图.1 小世界网络图像 [作者：用户：Sazaedo]

简介

很久以前，由于多种因素（如地形、缺乏交通选择、缺乏工具和缺乏教育），人们的活动范围有限。人员、商品和思想的流动通常依靠人力和畜力。因此，山脉、河流和海洋是流动性的重大障碍。除了这些物理障碍之外，不同国家的人民由于语言障碍而无法轻松沟通。因此，将物品和思想从源头移动到目的地需要很长时间。然而，自那些日子以来，技术已经有了很大的发展。由于发达的交通网络和交通方式（如汽车、飞机），我们可以轻松快捷地移动更长的距离。此外，由于教育的改善和少数标准化语言的传播，我们与外国人的沟通能力也有所提高。此外，我们可以通过电信和计算机网络几乎即时传递信息。世界正在变小。

我们生活在一个网络世界中，许多事物相互连接，这种连接使我们的生活方式更加有效。邓肯和斯特罗加茨指出，现实世界的网络既不是规则网络也不是随机网络，它们存在于规则网络和随机网络之间。他们称这种类型的网络为“小世界网络”。

历史^[3]

• 1929 年：匈牙利作家弗里吉斯·卡林西首次报道了小世界现象。他在他的书《一切都不同》中讨论了小世界属性的主题。

• 1967 年：斯坦利·米尔格拉姆进行了第一个关于小世界现象的实验研究。在这个实验中，他分析了当信件在两个陌生人之间传递时的平均分离程度。

• 1991 年：约翰·瓜尔写了一部戏剧《六度分离》，“六度分离”一词在世界上流行起来。

• 1998 年：邓肯·瓦茨和史蒂文·斯特罗加茨通过分析演员网络、神经网络和电力网网络对“小世界网络”进行了数学分析。他们说明了小世界属性出现在自然和技术网络以及社会网络中。

六度分离

图.2 六度分离图像 [作者：劳伦斯·范·利斯霍特]

世界上任何两个人都在 6 度内相连，即使他们彼此不认识。这意味着每个人都可以通过朋友的网络在 6 度内与名人（如麦当娜、达赖喇嘛和女王）联系起来。 这个想法最初由弗里吉斯·卡林西在 1929 年提出，但在 1969 年进行实验之前被认为是民间传说。1969 年，研究人员斯坦利·米尔格拉姆进行了一项关于“六度分离”想法的第一个实验研究。研究人员要求堪萨斯州威奇托、奥马哈和内布拉斯加州的居民寄一封信，信的目的地是波士顿的股票经纪人或马萨诸塞州的学生。当居民不认识目标人物时，他们必须将信寄给他们的朋友或熟人，而不是目标人物。虽然并非所有信件都送达目标人物，但平均度数为 5.5。 这个结果表明卡林西的想法几乎是正确的。之后，这种现象因约翰·瓜尔的戏剧《六度分离》，以及客厅游戏“六度分离凯文·贝肯” 广为流行。在米尔格拉姆的实验之后，几位研究人员通过改变网络类型来检验“六度分离”的假设。虽然米尔格拉姆的实验仅限于美国，但今天的实验分析的是全球网络。

2008 年，微软研究人员分析了微软 Messenger 的 300 亿条记录，他们发现平均分离度为 6.6。这意味着 78% 的两个人在 7 度内联系，而有些两对人之间相隔 29 度。 2011 年，Facebook 科学家 Lars Backstrom 和米兰大学的研究人员分析了 7.21 亿 Facebook 用户，约占全球人口的 10%。结果显示，平均分离度为 3.74，99.6% 的两个用户在 5 度分离内联系在一起。 这个结果表明 Facebook 的网络比微软 Messenger 的网络显示更小的世界。然而，两个人之间的网络连接程度是不同的，因为微软的研究是基于交换信息；另一方面，Facebook 的研究是基于“朋友”功能。

表 1 显示了平均分离度 [d] 的其他结果。在十个网络中，大肠杆菌代谢网络的平均分离度最小，为 2.98。相反，电力网络的平均分离度最大，为 18.99。 这意味着在电力网络中，任何两个节点之间的距离不超过 19 个节点。这个数字远大于社交网络中的平均分离度。根据这个结果，网络结构因网络类型而异。根据 Barabashi 的研究，如果知道网络的总节点数 [N] 和平均出度（协调数）[k]，就可以计算出任何网络的平均距离（平均分离度）[d]。平均距离大约为 $d\propto \log N/logk$，这个公式表明，网络越稠密，平均距离越小。表 1 显示了该公式的结果，在某些情况下（例如，互联网、移动电话通话），估计值 [log N / log k] 与平均距离 [d] 相似；然而，它并不完美（例如，万维网、电力网络和电子邮件）。例如，在互联网中，平均距离 [d] 为 6.98，而 log N / log k 的估计值为 6.59。另一方面，在电子邮件中，平均距离为 5.88，而 log N / log k 的估计值为 18.4。

表 1 平均分离度列表 [Barabashi]

网络名称	$N$	$L$	$<k>$	$<d>$	$d_{max}$	${\dfrac {logN}{log<k>}}$
互联网	192,244	609,066	6.34	6.98	26	6.59
万维网	325,729	1,497,134	4.60	11.27	93	8.32
电力网络	4,941	6,594	2.67	18.99	46	8.66
移动电话通话	36,595	91,826	2.51	11.72	39	11.42
电子邮件	57,194	103,731	1.81	5.88	18	18.4
科学合作网络	23,133	186,936	8.08	5.35	15	4.81
演员网络	212,250	3,054,278	28.78	-	-	-
引用网络	449,673	4,707,958	10.47	11.21	42	5.55
大肠杆菌代谢网络	1,039	5,802	5.84	2.98	8	4.04
酵母蛋白相互作用网络	2,018	2,930	2.90	5.61	14	7.14

Barabashi 指出，总节点数 [N] 和平均距离 [d] 之间的关系因空间维度而异。Barabashi 的 图 3.10 展示了通过改变维度，它们之间的关系，结果表明，规则网络的平均距离远大于随机网络的平均距离。这是实际平均距离 [d] 与估计值 [log N / log k] 之间存在差异的原因之一。此外，Barabashi 指出，平均距离 [d] 在不同规模的网络中有所不同。Barabashi 的 图 3.11 显示了 Facebook 用户在全球用户和美国用户之间的距离分布，结果表明，美国用户之间的平均距离小于全球用户之间的平均距离。

小世界网络： “Duncan Watts 模型”

规则网络和随机网络的网络结构存在显著差异。Watts 和 Strogatz 指出，现实世界中的网络结构既不是随机网络的结构，也不是规则网络的结构。因此，他们指出，现实世界中的网络介于这两种网络之间，他们称这种类型的网络为“小世界网络”。图 1 显示了环形格子上小世界网络的图像。一个网络有 $N$ 个节点，每个节点连接到 $k$ 个节点，每个节点根据概率 [p] 从最近的节点随机重新连接到另一个节点。在“规则网络”中，概率为零 [p = 0]，所有节点都连接到最近的邻居。随着概率的增加 [0< p < 1]，一些连接以概率 $p$ 随机重新连接到另一个节点，我们将这种连接称为“捷径”。当所有连接都被随机重新连接时 [p=1]，这个网络被称为“随机网络”。

路径长度 [L] 和聚类系数 [C]

为了解释网络结构特征，Watts 和 Strogatz 使用了两个因素：路径长度 [L] 和聚类系数 [C]。 如果每个人都连接到每个人，则 C = 1。

在规则网络中，路径长度 [L] 为 $L\sim N/2k$，聚类系数 [C] 为 $C\sim 3/4$。另一方面，在随机网络中，路径长度 [L] 为 $L\sim ln(N)/ln(k)$，聚类系数 [C] 为 $C\sim k/N$。因此，规则网络具有高度的聚类性，但路径长度较长。另一方面，随机网络聚类性较差，路径长度较短。 存在一些方程式可以解释聚类系数 [C] 和路径长度 [L]。根据 Newman 的说法，聚类系数 [C] 可以通过 $C=3(k-2)/4(k-1)$ 来估计。此外，在考虑维度 [m] 时，聚类系数 [C] 可以通过 $C=3(k-2m)/4(k-m)$ 来估计。

Barrat 和 Weigt 提出了考虑概率 p 的聚类系数 [C] 和路径长度 [L] 的公式。路径长度 [L] 会根据 n 和 p 的变化而显著改变。

$C={\dfrac {3(k-2)}{4(k-1)}}(1-p)^{3}$

$L(n,p)={\dfrac {1}{N(N-1)}}\sum _{i\neq j}d_{ij}$

$d_{ij}$ 是节点 i 和 j 之间的化学距离。

关于连接度分布，规则网络中每个节点都具有相同的连接度 [k]；然而，随着概率 $p$ 的增加，连接度分布变得不均匀，分布变得更广，而平均连接度为 $k$。

小世界效应

“小世界效应”意味着平均距离 [d] 随着节点总数 [N] 的增加而对数增长。这与规则网络中平均距离 [d] 随节点总数 [N] 线性增加的结构不同。另一方面，这与随机网络类似。但是，小世界网络与随机网络并不相同，因为它们表现出聚类性。 小世界网络兼具规则网络和随机网络的特征，因为它们像规则网络一样具有高度的聚类性，并且像随机网络一样具有较小的路径长度。

网络结构特征 [L 和 C] 与概率 [p] 之间的关系

图 5 网络结构特征 [L 和 C] 与概率 [p] 之间的关系 [衍生作品：图片来自 Watts 和 Strogatz]

图 5 显示了网络结构特征 [L 和 C] 与概率 [p] 之间的关系。当 $p$ 很小时，路径长度 [L] 的值迅速下降，而聚类系数 [C] 几乎保持不变。另一方面，当 $p$ 很大时，路径长度 [L] 几乎保持不变，而聚类系数 [C] 大幅下降。 小世界范围是指 $C$ 的值远大于随机网络的值，但 $L$ 的值接近随机网络的值。

Watts 和 Strogatz 分析了三种不同的网络，以检验小世界网络的概念；“电影演员”、“电力网”和“神经网络 (秀丽隐杆线虫)”。在电影演员方面，顶点是演员，当两位演员在同一电影中合作时，就会创建边。在电力网方面，顶点是发电机、变压器和变电站，边是输电线路。在秀丽隐杆线虫方面，顶点是神经元，边是突触或间隙连接连接的链接。

Watts 和 Strogatz 展示了路径长度 [L] 和聚类系数 [C] 的实际值和随机值（表 2）。他们发现，路径长度 [L] 的实际值与随机网络中的值相似，但聚类系数 [C] 的实际值明显大于随机网络中的值。因此，这三种网络都显示出小世界网络的特征。此外，他们还调查了传染病的传播时间，发现传染病在小世界网络中传播速度更快，因为网络中存在捷径。此外，传染病传播时间呈现出与路径长度 [L] 相似的曲线图。 所有这些实证研究表明，现实世界网络与小世界网络具有相似性。

表 2 小世界网络的实证例子 [Watts 和 Strogatz]

	$L_{actual}$	$L_{random}$	$C_{actual}$	$C_{random}$
电影演员	3.65	2.99	0.79	0.00027
电力网	18.7	12.4	0.080	0.005
秀丽隐杆线虫	2.65	2.25	0.28	0.05

小世界网络的类别

Prizmič 指出，现实世界网络中的连通性分布遵循幂律，并以 WWW 网络为例说明。该网络显示出“小世界效应”，因为两个文档之间的最短路径随节点总数 (N) 的对数增长。这意味着，即使网络规模增加，最短路径也不会发生显著变化。这是一种小世界网络。

Amaral 等人 指出，小世界网络有三种类型；1) 无标度网络，2) 广度尺度网络，3) 单尺度网络。

1) 无标度网络：“顶点连通性分布呈幂律衰减”

2) 广度尺度网络：“连通性分布呈现幂律区域，然后是急剧的截止”

3) 单尺度网络：“连通性分布具有快速衰减的尾部”

无标度网络的例子包括 WWW 和科学论文的引用网络。广度尺度网络是电影演员。单尺度网络是电力网、初中友谊、神经网络和聚合物链模型。

小世界网络在交通领域的应用

机场网络

图 6 世界航空路线图-2009 [作者：Jpatokal]

Amaral 等人 分析了机场网络的客运量和货运量。结果表明，机场网络是单尺度网络，因为连通性分布的衰减程度大于无标度网络。作者指出，容量限制是航空网络不显示无标度网络的原因。航空网络具有枢纽辐射结构，航空公司倾向于连接到枢纽机场；但是，每个机场的货运和客运处理能力是有限的。因此，连通性分布不遵循幂律模型。

波士顿地铁网络

图 7 MBTA 波士顿地铁图 [作者：Citynoise]

Latora 和 Massimo 分析了波士顿地铁网络，利用路径长度 [L] 和聚类系数 [C] 来确定该网络是否为小世界网络。他们计算了路径长度 (L=15.55)，但由于某些节点仅连接到网络中的一个节点，因此无法计算聚类系数。因此，他们使用替代因素效率 [E] 来解释小世界网络。当最短路径长度 [d] 更长时，效率 [E] 更低。 $E_{glob}$ 表示“整个网络的效率”，而 $E_{loc}$ 表示“节点邻居子图的平均效率”。作者指出，当 $E_{glob}$ 和 $E_{loc}$ 都很高时，该网络表现为小世界网络。结果 (表 3) 表明波士顿地铁网络没有表现出小世界网络的特征，因为 $E_{loc}$ 较低，而 $E_{glob}$ 较高。另一方面，当作者将公交系统添加到地铁网络中时，$E_{glob}$ 和 $E_{loc}$ 都很高。因此，波士顿交通网络可以建模为小规模网络。

$E={\dfrac {1}{N(N-1)}}\sum _{i\neq j}(1/d_{ij})$

表 3 波士顿地铁网络的全局和局部效率 [Latora 和 Marchiori]

	$E_{glob}$	$E_{loc}$
波士顿地铁	0.63	0.03
波士顿地铁 + 公交	0.72	0.46

不同规模交通网络的自相关统计

图 6 自相关统计 [Moran's I 和 Getis's G] 与概率 [p] 之间的关系 [衍生作品：图片来自 Xu 和 Sui

Xu 和 Sui 介绍了一种方法，用于分析小世界属性与网络自相关统计之间的关系，从而分析“小世界效应”；Moran's $I$ 和 Getis's $G$.

莫兰指数 ($I$) 是自相关统计量之一，莫兰指数 ($I$) 的正值说明了与邻居的相似性；另一方面，$I$ 的负值解释了与邻居的不相似性。在 Getis's $G$ 方面，$G$ 的高值表明高值可能彼此捆绑在一起，而 $G$ 的低值表明低值更集中。在常规网络中，莫兰指数 ($I$) 较高，而 Getis's $G$) 较低；但是，随着概率 [p] 增加，莫兰指数 ($I$) 急剧下降，而 Getis's $G$) 逐渐增加。

此外，这两个值在小世界网络范围内相互交叉。Getis's $G$) 的低值说明节点连接度低可能集中，而莫兰指数 ($I$) 的低值表明全局相关性小。这解释了小世界网络的特征，因此莫兰指数 ($I$) 和 Getis's $G$) 的交点表明小世界网络。

他们将这种方法应用于三个交通网络：国家（美国州际和高速公路网络）、都市（休斯顿-加尔维斯顿地区的道路网络）和城市内（波士顿地铁网络）。结果表明，莫兰指数 ($I$) 和 Getis's $G$) 受滞后距离的影响很大。根据 Xu 和 Sui 的说法，滞后距离的含义是“邻域的大小，即在计算网络自相关统计量时要考虑多少个邻居”。随着滞后距离的增加，莫兰指数 ($I$) 降低；另一方面，Getis's $G$) 升高。此外，当莫兰指数 ($I$) 和 Getis's $G$) 较低时，它们会相互交叉。他们发现交点值在所有交通网络中都相似。

拥堵因子与网络类型之间的关系

吴等人研究了三种类型的网络（小世界、无标度、随机）中拥塞因子与交通量之间的关系。为了分配交通流，使用用户均衡 (UE) 方法，并随机分配链路容量。网络规模为 $400\times 400$，平均协调数 [k] 为 7。

结果表明，当交通量较小时，无标度网络和小世界网络比随机网络更容易拥塞。另一方面，当交通量较大时，随机网络比无标度网络和小世界网络更容易拥塞。这是因为在无标度网络和小世界网络中，大部分流量首先集中在枢纽节点上，但随着交通量的增加，拥塞的增加速度相对较慢。另一方面，在随机网络中，随着交通量的增加，拥塞链路的数量稳定增长。与无标度网络和小世界网络相比，小世界网络更容易发生拥塞。因此，在三种类型的网络中，无标度网络可以处理最大的交通量。此外，他们还分析了拥塞因子与重连概率 [p] 和聚类系数 [C] 之间的关系，结果表明，当概率 [p] 和聚类系数 [C] 较大时，拥塞因子较小。

结论

“小世界网络”介于完全规则网络和随机网络之间。Duncan 和 Strogatz用两个特征对该网络进行了数学解释；路径长度 [L] 和聚类系数 [C]。小世界网络像规则网络一样高度聚类，路径长度像随机网络一样小。根据研究，他们表明现实世界网络在生物、技术和社会网络中具有小世界网络的特征。这是一个重大发现，因为小世界网络有可能对现实世界网络进行建模。

研究人员关注这一主题，因为它对于理解交流（例如，新闻、谣言和时尚的传播）至关重要。尤其是在医疗领域，需要弄清楚疾病（例如，艾滋病毒、非典）传播的特征。此外，该主题还扩展到交通研究领域。现实世界网络结构并不统一，它具有多种类型的网络，因此很难对现实世界网络进行建模。研究是一个正在进行的工作，研究人员试图解释这个复杂的网络。