瓦茨和斯特罗加茨的论文有个很重要的贡献 他们给出了个简单的模型来说明如何生成小世界模型 也就是,如何生成平均路径长度短,但集聚系数仍然很高的网络 这个模型是这样的 首先,由一个规则的网络开始 我说“规则”的意思是,每个节点的连接模式都一样 例如,这个节点 连接到了两边的每一个邻居 相似地,这个节点也有相同的节点连接模式,等等 然后,总共有 N 个节点 每个节点有 m 个邻居 大写的 M 为链接的数目 对这个例子来说 有 10 个节点 每个节点有 2 个邻居 也就是总共有 10 条链接 将会在这个模型中发生的是 相邻邻居的一些链接 将会被重新连接 也就是,去掉一部分 然后再连接到个距离较远的邻居,来模拟远距离连接的生成 模型中有些参数 叫 beta 是每个链接被重新连接的概率 在这个例子中,让我们使 beta = 0.2 也就是,每个链接都有 0.2 的概率被重新连接 现在,这里要用的方法是 随机选择 beta * M 个链接 算出来会是 0.2 * 2 = 2,所以我选择 2 条链接 现在红色显示的那几条 随机选出来的 然后我将把链接的其中一端重新连接到另一个随机选择的节点上 这就是我怎样去掉现有的一端 然后将其连接到随机选择的节点上去 这就是我们的新网络 大多数的连接都是在相邻的邻居之间的,但有两个例外是长距离连接 像之前一样,我们将会看一下这个模型的 Netlogo 实现 这是这个模型的界面的样子 我们有参数:node-count,也就是有多少个节点 每个节点有多少邻居 还有 beta 参数,重新连接的概率 若进行“设置” 我有 10 个节点 每个都连接到了与其相邻的邻居上,所以每个节点有 2 条链接,2 个邻居 而我现在将 beta 设为 0,所以不会有重新连接——没有链接会被重新连接 现在我们可以看看这里,可以看到 分支度分布 这里说 10 个节点的分支度都为 2,我们已经知道了 这个也同时告诉了我们节点间的全局平均距离,2.5 跳 还有这里的集聚系数 0,这个网络不集聚 还可以做其它一些事 举例来说,我们可以点击这个 show-neighborhood 的按钮,然后点击一个节点 然后这个节点的邻居就出来了 我们还可以显示链接的距离 点击个节点,也就是从这个节点到那个的距离 还有别的东西可以做 我又按了次设置,清除这些东西 好的,现在 我可以更改 beta 如果我将 beta 改到 0.1,也就是这些链接中会有 1 个会被重新连接,会发生什么? 再次设置,你可以看见这个链接被重新连接了 这个例子中,全局平均距离上升了 这只是因为我们的节点数太少了 好的,让我们用个比较真实的数目再做一次。让我们用 100 个节点 beta 设回 0,设置 现在你看到有着相同的规则模式的 100 个节点 全局平均距离是 25 跳 让我们将 beta 设为 5% 按设置。记住 beta 是节点被重新连接的概率 也就是每个节点有 5% 的几率被重新连接 然后,实际上很多会被重新连接 我们看到全局平均距离 大大降低了 从 25 到 9.24 所以,这个相对较小的重连接概率使得距离大幅度下降 分支度分布也变了 现在让我试试重连接 10% 的链接 嗯,上升了,但如果我们再做一次 下降了,因为这是随机的,有许多随机因素。集聚系数依然很低 集聚现象会在邻居更多的时候出现,所以让我们将 neighbor-count 设为 4 beta 设回 0 这里,每个节点都连接到两边的各两个节点 若我改掉 beta……现在,现在的距离是 12.75 让我们再次将 beta 设成 5%,设置 现在 全局平均距离大幅度下降了,集聚系数上升了 你会有机会在作业中玩一下这个小世界模型 让我们通过总结我们学习到了关于小世界网络的什么来结束这个子单元 我们看到,有个网络的渐变光谱,从十分规律到十分随机 规则的网络节点间的平均距离高 以及高集聚系数 高集聚系数来源于你有多于 2 个的邻居,这里我们每个节点有 4 个邻居 然后随机网络平均距离低,但集聚系数低 而小世界网络某种层面上更像现实的网络 有着低平均距离和高集聚系数 与瓦茨和斯特罗加茨所研究的现实网络相似