博文

小世界网络理论25周年

已有 951 次阅读 2023-8-30 17:28 |个人分类:科普|系统分类:科普集锦

小世界网络理论25周年

网络就像是研究许多物理系统的一个明显的数学框架，比如电网、大脑（图1）和社交媒体平台。如今，有大量关于如何组织此类网络的理论工作，但事实并非总是如此。尽管对网络的研究有着悠久的历史，但在很长一段时间里，它最接近于将真实世界的网络描述为随机图，但大多数系统都表现出一定程度的组织性。25年前，正是在这种背景下，Duncan Watts和Steven Strogatz发表了《“小世界”网络的集体动力学》，这篇论文帮助开创了网络科学的现代。

图1 大脑网络示意图

至少从20世纪50年代末开始，人们就开始研究随机图，当时Paul Erdõs和Alfréd Rényi，以及独立的Edgar Gilbert，引入了具有固定数量的随机成对连接节点的图模型。这样的图具有较短的特征路径长度（如果链路的总数高于阈值，则两个节点之间的最短路径中的链路数量较小）。这一特征与现实世界网络的观察结果相匹配。例如，社会心理学家Stanley Milgram在20世纪60年代证明，两个美国人之间的典型联系链长度在2到10之间。

然而，随机图的聚类情况非常少。例如，很少有三角形的节点相互连接，这与现实世界网络的观察结果不匹配。在现实世界网络中，一个人的朋友往往是彼此的朋友。相反，聚类是正则格（regular lattices）的典型。

Watts和Strogatz的贡献是提出了一个在正则格和随机图之间进行插值的模型，方法是取一个环格，并以固定的概率随机重新连接每个链接。他们发现，存在一系列重新布线的可能性，由此产生的网络保留了原始晶格的高聚类，但表现出更短的路径长度。因此，他们有了一个模型，捕捉到了现实世界中网络的两个重要特征。他们引用Milgram的作品，将他们的模型网络称为“小世界”。

Watts和Strogatz写道：“我们希望我们的工作将促进对小世界网络的进一步研究。”可以公平地说，他们的希望已经实现。第二年，Albert-László Barabási和Réka Albert引入了一种生成无标度网络的算法，即一个节点具有一定数量链路的概率由幂律给出。该模型捕捉到了现实世界网络的另一个关键特征，即它们通常包含几个连接到异常多的其他节点的hub。Barabási–Albert模型也比Watts–Strogatz模型更小，因为在Watts–Strogatz模型中，节点之间最短路径的最大长度是系统大小的对数，而在Barabási–Albert模型中是系统大小对数的对数。这两种模型都已成为网络理论的主力军。

最近，人们越来越意识到，有时将系统建模为网络并不一定是最好的方法。例如，Watts和Strogatz通过将同一部电影中出现的两对演员联系起来，构建了一个演员的小世界网络，但人们可以通过他们都属于的更高层次的联系，平等地将一部电影的演员联系起来。由此产生的超图（也称为高阶网络）可以捕捉集体行为，而网络不可能总是这样。

有关小世界网络详细理论见参考文献[2]，基本概念可以参考维基百科（https://en.wikipedia.org/wiki/Small-world_network）。

参考文献

[1] Budrikis, Z. 25 years of small-world network theory. Nat Rev Phys 5, 440 (2023). https://doi.org/10.1038/s42254-023-00628-6

[2] Watts, D. & Strogatz, S. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)

以往推荐如下：

1. 分子生物标志物数据库MarkerDB

2. 细胞标志物数据库CellMarker 2.0

3. 细胞发育轨迹数据库CellTracer

4. 人类细胞互作数据库：CITEdb

5. EMT标记物数据库：EMTome

6. EMT基因数据库：dbEMT

7. EMT基因调控数据库：EMTRegulome