The Small World Hypothesis
17:25 Share

Kyle 讨论了小世界假说的历史和证据。</context> <raw_text>0 前几天我一直在想，离我距离最远的人是谁？不是地理位置上的距离，而是社会网络上的距离。我想了一会儿。我想出的最好的答案是金正恩。

他不是我的朋友，也不是我朋友的朋友，但我的意思是，让我们想象一个科幻的前提。我从未来回来了，我必须给他带个消息来拯救世界。我能把这个消息传达给他吗？我的意思是，我没有他的电话号码，电子邮件地址，但我参与了一些政府研发项目。我认识一些低调的政治家。也许这些人中有人认识国务院的人。

这些人中有人认识联合国谈判代表，其中有人认识一些去过朝鲜的人道主义救援人员。在我们的文化中，人们常说任何两个人之间只有六步之遥，即使是我和金正恩之间也是如此。

这不是阴谋论。这是一个数学真理。它被称为小世界假说。它断言，地球上几乎每个人都只与其他人隔着几个联系。如果你一直在关注这个赛季，你可能已经多次听到 Asaf 提到了随机网络与现实世界网络看起来完全不同。

好的，但是如果我需要模拟数据呢？也许我需要测试用例来查看我正在处理的一些图形项目的可扩展性。随机图是行不通的。今天的节目将会有一个小小的历史课，但主要是对三种不同模型的探索。Erdos-Renyi 模型、Watts-Strogatz 模型和 Barabasi-Albert 模型。您正在收听 Data Skeptic，图和网络。

该播客探讨了图数据结构如何影响科学、工业以及其他领域。因此，让我们从这个看似简单的问题开始。随机图是什么样的？先撇开我们已经知道它不一定像现实世界的网络一样，这不是一个显而易见的见解。如果我们回溯到 20 世纪 50 年代后期，匈牙利数学家 Paul Erdos 和 Alfred Rényi 开始着手回答这个问题。

Erdos 是一位非常著名的人物，以与众多贡献者在广泛的主题上发表论文而闻名。甚至还有你 Erdos 数的概念。如果你和他一起发表过论文，我认为你有一个 1，也许是 0。如果你与和他一起发表过论文的人一起发表过论文，你的数字就会比这多一个，以此类推。本身就是一个非常有趣的网络。但无论如何，这是单独的。

他们在 50 年代的想法在当时是相当大胆的。人们了解图，他们当然已经研究了很长时间，但这里的关键见解之一是提出这样一个问题：如果我们研究所有可能图的整个空间会怎样？好主意，我们怎么做呢？他们的方法是将连接视为随机事件。因此，他们提出了一个我将要描述的关于如何生成随机图的模型。

你的网络中有多少个节点，然后你遍历每个可能的配对并抛硬币。正面连接，反面不连接。这是第一个正式的随机网络模型。而且它在数学上是易于处理的，你必须承认这一点。因此，即使我们知道它与现实不符，Erdos-Renyi 模型也首次将随机性和网络放在了同一个讨论中。

这开启了一系列全新的问题。例如，需要添加多少个链接（随机添加），才能使整个网络完全连接？某些给定节点最终被隔离的几率是多少？以及，我想平均而言，那个巨大的集群（我们现在称之为巨型连通分量），它通常何时看似凭空出现？

而这些不仅仅是学术上的好奇心。流行病学家对此很感兴趣。也许他们可以估计病毒传播的情况。对网络感兴趣的计算机科学家看到了他们如何应用这一点。并且与物理学有关，因为数学家们终于可以谈论网络结构中的相变了。系统仅仅通过轻微调整一个参数就从一种行为转变为另一种行为的那一刻。

所以这是一个有前景的模型，可计算的，易于理解，易于使用。抛硬币也可以用概率加权的方式进行。

但是当科学家试图将 Erdos-Renyi 模型应用于现实世界系统（如社交网络和交通网络）时，它却失之毫厘。它未能捕捉到一些至关重要的东西，那就是网络的结构。现实世界的网络充满了紧密的社区，每个人都与其他人相连的小群体。这些集群似乎总是出现。

但它们也有捷径。偶尔会出现远程连接，从而大大缩短两个非常遥远点之间的步数。Erdos-Renyi 确实提供了一些短路径，但集群很少。而这并不是我们在现实世界中看到的。所以问题变得很清楚。如何构建与现实世界网络不太容易区分的随机网络？或者换句话说，在什么生成过程中我们可以随机生成具有我们正在寻找的属性的图？

在这种情况下，通常存在短路径并且存在高度的聚类。信不信由你，直到大约 1998 年，据我所知，才发生了下一个飞跃。这就是 Watts-Strogatz 模型。因此，Duncan Watts 和 Steve Strogatz 发表了一篇论文，悄然改变了一切。

他们的见解很简单但很强大。你从一个高度聚集的网络开始，比如环形晶格。在这种网络中，每个节点都连接到其最近的邻居。这就是我们初始化网络的方式。然后我们随机重新连接一小部分这些边。不是全部，只是一些。

遵循这个简单的过程，他们发现的结果令人震惊。即使只有少量随机捷径，节点之间的平均路径长度也会急剧下降，而他们开始时的高聚类则保持不变。换句话说，他们在两个极端之间架起了一座桥梁。他们创造了规则网络的秩序，并且保持了我们在先前模型和现实世界网络中看到的短路径。

因此，Watt-Strogatz 模型向前迈进了一步，至少如果你的目标是生成符合现实生活、高聚类、短路径的随机网络的话。但是如果我们可以说这种方法播下了第一个的种子，那么它就引出了一个问题，什么可能比 Watt-Strogatz 更好？或者换句话说，它在哪些方面有改进的空间？

所以这是一个不错的模型，这是一个参数模型。你可以控制初始化时连接的 k 个最近邻居的数量以及随机重新定向边的随机因素。如果你运行聚类算法，它会找到集群。但最不足的地方在于它的不均匀性。

现实世界的网络很混乱。Watt-Strogettes 网络仍然感觉有点规则。你知道，在现实世界中，让我们以社交网络为例。有些人有数百个连接，而其他人只有几个。有些节点是中心节点，连接到各个地方。其他节点则深埋在很少访问的小子网络中。Watt-Strogettes 没有考虑到这一点。

在他们的模型中，每个节点都从相同数量的连接开始，即使你对它添加了一点高斯噪声。它仍然过于统一，过于平等。现实世界的网络表现出我们经常谈论的幂律。应该有一些节点获得大部分链接。这并不意味着 Watt-Strogatz 没有用。它当然表明了仅仅几个远程连接就可以使网络感觉很小。

因此，这将我们引向今天要介绍的第三个模型，Barabasi-Albert 模型。他们的见解是，与其像前两种方法那样重新连接网络，不如随着时间的推移来增长网络。所以从，好吧，我想从一个空图开始，添加一个节点，无法立即添加任何边，然后添加第二个节点。关键的见解是，新节点更倾向于连接到已经连接良好的节点。

因此，正如你所想象的那样，仅仅是偶然，当你添加节点时，在某些时候会发生一些密度。也许如果你添加了十个节点，其中一个节点有五个（好吧，我想是九个）其他节点连接到它。这意味着未来的节点更有可能连接到这个已经很受欢迎的节点。这种方法的结果是，你得到了无标度网络，有很多小的节点，但也有几个巨大的中心节点。

所以我们讨论了三个简单的模型，现在让我们抛开理论，更多地谈谈小世界假说的经验证据。身份盗窃可不是闹着玩的。仅去年，数据泄露就增加了 72%，保护您的个人信息比以往任何时候都更加重要。但事实是这样的，它不仅仅是关于强密码了。数据经纪人正在收集和出售您的信息，使您容易受到诈骗和身份盗窃的攻击。

这就是为什么我很高兴告诉你 Incogni。他们专门负责自动从这些数据经纪人网站删除您的个人数据。想想看。与其花费无数时间试图追踪您的信息在哪里被出售，Incogni 会为您完成所有工作。他们与数百家数据经纪人合作，发送删除请求并处理任何阻力。

有了他们的家人和朋友计划，您也可以为您的亲人提供保护。这就像拥有一个全天候工作的个人隐私团队。要获得 Incogni 年度计划的独家 60% 折扣优惠，请在结账时使用我们的代码 DATASKEPTIC。这是一个词，DATASKEPTIC。或访问 incogni.com/dataskeptic。I-N-C-O-G-N-I，Incogni。现在让我们抛开理论。

并更多地讨论小世界假说的经验证据。在一个纸面上模拟一个小世界是一回事。足以证明我们实际上生活在一个小世界中。所以我们将倒回几十年。同样，最早也是最具标志性的尝试来证明这个理论是在 1967 年，当时心理学家斯坦利·米尔格拉姆试图使用美国邮政服务来测量美国社会的关联性。米尔格拉姆有一个非常简单的想法。你给中西部的一个随机人一封信。

你要求他们只通过个人联系将它转发给波士顿的目标人物。所以不要随便寄给任何人。除非你认识他们，否则不要直接寄给他们。相反，想想，我认识波士顿的任何人吗？我能寄到那里吗？或者也许你认识住在俄亥俄州但在波士顿上过学的人。如果那是你最好的选择，把它寄给那个人，并要求他们转发。我想我们都知道结果，但在开始时，我想这些信可能会在邮件中丢失。只是回溯。

在全国各地反弹，从未到达他们的目标。但米尔格拉姆发现，平均链接数，即转发尝试次数，米尔格拉姆发现，平均需要六次尝试，六次转发，链条中的六个链接才能将信从那个随机的中西部人送到波士顿的特定目标。因此，我们的文化中根深蒂固了这种六度分隔的概念，后来被凯文·培根游戏推广。

事实上，米尔格拉姆的研究很有趣，但也有一些问题。它的样本量很小，而且有很多断链，也就是说信件从未到达目标。你可以争辩说存在地理偏差，而且我对米尔格拉姆监狱实验的所有了解都让我对其持怀疑态度，所以我不知道这对于这项工作意味着什么。好吧，我们还有什么证据？快进到更接近现在的时间。

让我们回到 2003 年，当时哥伦比亚大学的社会学家彼得·多兹和他的同事决定重新审视米尔格拉姆的想法，但这次是用电子邮件。

参与者被要求通过电子方式转发邮件，而不是物理信件。并且再次，只使用他们的现实世界联系。在 DODS 实验中，有 18 个不同的指定目标个体分布在 13 个国家。所以他们不是随机的人，他们分布在不同的职业、大陆甚至社交圈中。所以 DODS 让大约 60,000 人参与其中。再一次，出现了一些相当引人注目的东西。算术平均值，即常规平均值，

到达目标所需的步骤数为 5.5。这略小于跨越海洋、语言和社会界限的六次数字握手。与米尔格拉姆的实验非常相似，但数据更多，严谨性更高，而且这次是在全球范围内进行的。这是迄今为止对小世界效应最强的证据，而且它不仅仅是美国的一种怪癖。它似乎是全世界人类网络的一种普遍结构特性。

我接下来能找到的见解来自 2011 年的 Backstrom 等人的研究。所以是 2011 年，社交网络爆炸了。Facebook 声称拥有 7.21 亿活跃用户和超过 690 亿个友谊链接。可以说，这可能是迄今为止汇编的最全面的社交网络数据集。因此，由 Lars Backstrom 领导的 Facebook 研究人员能够提出一些非常深刻的问题。

地球上任何两个用户之间到底有多少步？他们分析了整个 Facebook 图表。7.21 亿活跃用户。伙计，我希望我能和他们谈谈这背后的工程。这不可能容易。他们发现了什么？两个用户之间的平均距离不是 6。不是 5.5。是 4.72。

所以“六度分隔”这个说法不仅是真的，而且已经过时了。这里发生了什么？世界在缩小吗？我们越来越互联了吗？或者也许我们现在只是更好地测量事物了。我们拥有以前没有的数字数据集。这可能是以上所有原因。米尔格拉姆和多兹依赖于人的判断。你认为谁更接近目标？Facebook 拥有实际的网络。好吧，这让我们处于什么位置？

我们有一些生成随机图的方法。Barabasi-Albert 方法似乎与现实世界数据最一致。我们有经验证据相信小世界假说是正确的。好的，我们该怎么办？如果你接受我们生活在一个小世界中，它会引发一系列新的问题。短路径和紧密集群不仅描述了网络，还塑造了该网络的行为方式。

在一个小世界结构中，谣言或模因，甚至行动呼吁都可以以令人难以置信的速度传播。它不一定需要大规模的营销推广，它只需要正确的捷径。病毒（生物病毒或数字病毒）也是如此。小世界网络使病原体很容易从一个集群跳到另一个集群，绕过了地理或社会距离通常提供的障碍。对于核心计算机科学来说，也有一些严重的意义。

当你学习算法时，你通常会讨论最坏情况下的运行时间，即大 O 分析。我知道平均情况分析也有很多好的工作，但碰巧的是，广度优先搜索和 Dijkstra 算法之类的算法在平均路径长度较短时运行效率会更高。甚至通常被认为是难处理的 NP-hard 问题，其中一些在小世界数据集上运行时也会表现不同。

研究的不仅仅是最坏情况，还有典型情况，这很有趣。你知道，从理论到实际发生的事情。现在，在经典算法之外，小世界结构会影响复杂性。所以现在让我们引用卡尔·波普尔的思想，并提出一个关键问题：如何证伪这个假设？什么数据可以使小世界假说失效？

一种方法是表明在现实世界的网络中，人们并非通过短路径连接。实际上，平均距离很大。大多数节点都是孤立的或生活在结构性死区。我不知道，也许蜘蛛就是这样？它们不是隐居的吗？也许有一些奇怪的动物的社交网络具有这种结构，但我不知道。另一种方法是反驳聚类方面。

表明现实世界的网络实际上并没有形成紧密的社区。但是，无论是在社会、生物还是技术领域，总是可以看到密集的局部分组。所有这一切都带给我们一个深刻的真理：小世界假说可能不是一个定律，而是一种模式。像任何好的模式一样，它的力量不在于普遍为真，而在于足够真实以塑造我们的思维方式。

仅仅通过扩展这种奇妙的数据结构，这些涌现特性就会发生，难道这既好奇又奇妙吗？因此，小世界假说是真正经受住怀疑论者检验的一个假设。