REF · 经典模型

优先连接模型THE PREFERENTIAL ATTACHMENT MODEL

Barabási–Albert,1999 — 「富者愈富」的网络版;更早的形式见 Yule(1925)、Simon(1955)、Price(1976)

被引用于:Topic 22 无标度与优先连接

01它问的是什么问题(The Question It Poses)

1990 年代之前,网络研究的默认模型是随机图(random graph):把点两两之间随机连线。它有个明确的预测——一个点连了几条边(这个数叫度数,degree)应该有个典型值,绝大多数点都挤在平均值附近,最大的也大不了几倍。

可是一抬眼,现实完全不是这样:极少数网页被上百万个页面链接,极少数机场连着上百条航线,极少数论文拿走大部分引用。这些点不是稍微大一点,是大出几个数量级。

于是问题变得很具体:要给「随机连线」补上什么,巨头才会自己长出来?而且尽量少补——补得越少,结论能覆盖的系统越多。这个模型给出的回答是:补两条就够。

02规则本身(The Rules)

  1. 从一小撮已经连好的点开始(几个就行,怎么连都无所谓,最终结果不受它影响)。
  2. 每一步加入一个新点,它带来 m 条边(m 是个固定的小数字,比如 2)。
  3. 新点连谁?选中某个老点的概率 = 那个老点当前的度数 ÷ 全网所有点的度数之和。这一条就叫优先连接(preferential attachment)。
  4. 连好之后,进入下一步,再加一个新点。网络就这样一直长下去。
  5. 已有的边永不删除、永不改接;已有的点永不退出。

第 3 条是全部的机关:它没有说新点"喜欢"谁,只说了概率跟对方已有的边数成正比。第 5 条则是最强的一条假设,也是这个模型在现实里最先破掉的地方。

新来的点要选一个老点连上 — 每个老点占的宽度就是它现在的边数Ak = 542%Bk = 325%Ck = 217%Dk = 18%Ek = 18%新来的点没有人在偏爱谁 — A 被选中的机会大,只是因为它占的格子多
把选择过程画成一条按度数分格的带子:谁占的格子多,谁被随机指到的机会就大。「优先」在这里是概率上的偏向,不是任何人的偏好。

03跑起来会看到什么(What You See When It Runs)

跑出来的度数分布是一条幂律(power law):连了 k 条边的点的数量正比于 k 的负三次方。这个指数 3 是从规则里推出来的——它跟 m 是几无关,也跟一开始那撮点怎么连无关。

下面这张图是真跑出来的:两边各 30000 个点、每个新点带 2 条边,唯一的差别是「选谁」。随机挑的时候,最大度数是 27;按边数挑的时候,最大度数是 616。而两边的平均度数完全相同,都是 4.0

各跑 30000 个点、每点 2 条边 — 只有「选谁」这一条不同110100110⁻110⁻210⁻310⁻4度数 k(对数)→有多少点至少这么大(对数)优先连接(按边数挑)随机挑两条线的平均度数完全相同(都是 4.0)同样 30000 个点:随机挑时最大度数是 27,优先连接时是 616
纵轴是「度数至少这么大的点占多少比例」,两轴都取了对数。这种坐标下幂律是直线,而随机挑出来的分布迅速掉到地上——它有典型值,直线那条没有。

还能算出单个点的成长曲线:第 i 个进场的点在网络长到 t 个点时,度数是 ki(t) = m·√(t/ti)。所有点在模型里长得一模一样,唯一的差别是进场顺序,而这个顺序被时间以平方根的速度放大。早到的点永远在前面,晚到的永远追不上。

最后一件很重要但常被略过的事:这两条规则缺一不可。只保留增长、新点随机挑,出来的是指数分布,没有枢纽;只保留优先连接、点数固定不长,度数分布根本不稳定,边越加越多,最后整张网连成一片。是「增长中的系统按存量分配增量」这个组合在起作用。

04它解释了现实中的什么(What It Explains)

它解释的是一件事:为什么在「一直在长、且新来者按可见度选择」的系统里,规模分布是重尾的而不是钟形的——网页链接、论文引用、机场航线、软件包依赖、蛋白质相互作用,都有这个结构。

它给出三条可以被数据否掉的预期:① 度分布重尾;② 新边分配到某个点的速率随该点度数线性上升;③ 早进场的点系统性地更大。第 ② 条尤其有用,因为它可以直接测——Jeong、Néda 和 Barabási 2003 年就这么干了,结果是引用网络和互联网接近线性,而演员合作网和科学合著网是次线性的。

它还替掉了一个很流行的坏解释。看到某个节点特别大,默认的说法是「因为它更好」;这个模型说明,在满足上面两条规则的系统里,就算所有节点完全一样,也一定会出现一批巨头——所以「它大」本身不构成「它好」的证据。至于早期的一点随机领先会不会真的滚成后来的巨大差距,van de Rijt 等人 2014 年在 Kickstarter、Wikipedia 等平台上做了随机实验:随机给一点初始成功,后续成功率显著提高,但边际递减。

它不能解释什么(What It Cannot Explain)

延伸阅读(Further Reading)