经典论文难度：入门

随机网络中标度律的涌现

Emergence of scaling in random networks

Barabási A-L, Albert R · Science 1999 · DOI: 10.1126/science.286.5439.509

无标度幂律度分布增长优先连接BA 模型平均场

一句话

报告多个真实网络的度分布尾部近似幂律，并提出“增长 + 优先连接”模型，用平均场方法推出指数 γ=3。

相关专题：小世界与无标度网络模型、生物分子网络与拓扑特征

VIDEO讲解视频

随机网络中标度律的涌现5 分 3 秒

文字稿

大家好，这一期我们精读 Barabási 和 Albert 1999年发表在Science上的论文。它提出了增长加优先连接的模型，解释了网络中枢纽节点的来历。

ER 随机图和 WS 小世界模型有个共同点，度分布都集中在均值附近，几乎不可能出现枢纽。而演员合作网和万维网等大型网络的完整拓扑显示，度分布都有一条很长的尾巴。第一个问题是，真实网络的度分布是否普遍呈幂律？第二个问题是，什么样的生成机制能产生这种分布？

先看两种度分布的差别，左边是随机网络，度集中在平均值附近。右边这种网络，少数节点的度远远大于平均值。在线性坐标下，它的分布几乎贴着横轴，看不清那条长尾。换成双对数坐标后，右边的点近似落在一条直线上，这就是幂律分布。作者测得演员合作网的指数约为2.3，万维网入度约为2.1，引文网络为3。美国西部电网规模较小，标度区不明显，指数近似为4，所以指数大致落在2.1到4之间。

作者指出，此前的模型忽略了真实网络的两个共同特点，一是增长，二是优先连接。增长是说网络不断加入新节点，就像新演员、新网页、新论文不断出现。优先连接是说，新节点连向某个已有节点的概率，正比于这个节点当前的度。画面中橙色是刚加入的节点，节点大小代表度，红色是度很大的枢纽。越早加入的节点积累的连接越多，这就是富者愈富。右边是双对数坐标下的累积度分布，随着网络长大，尾巴越拉越长。

第一行是优先连接的概率，节点的度除以全网度的总和。平均场推导把度当作连续变量，解出节点的度随时间的平方根增长，加入越早，度越大。再假设节点在时间上均匀加入，就得到稳态分布，它与度的三次方成反比。也就是说指数等于3，而且与每个新节点带入的边数无关。数值模拟得到的指数是2.9，分布形状也不随网络规模变化。

对照模型 A 保留增长、去掉优先连接，度分布变成了指数分布。对照模型 B 保留优先连接、去掉增长，早期像幂律但不稳定，最终网络变成完全图。非线性优先连接的模拟显示，只有连接概率与度成正比时，才会出现标度律。作者还指出，如果一部分边是有向的，指数可以变得小于3。

原文的指数来自双对数图上的直线拟合，今天看来统计上不够严格。2009年 Clauset 等人提出了最大似然估计加拟合优度检验的流程。2019年用这套方法检验近千个网络，发现严格的无标度网络是少数，许多生物网络更接近对数正态。Barabási 等人回应说，有限规模、度相关和测量偏倚会让理想幂律变形。此外，模型能产生幂律，并不说明真实网络就是这样生成的。这场争论至今仍有分歧，阅读时要区分重尾和严格幂律。

BA 模型本身过于简化，它只能给出等于3的指数。它的聚集系数随网络增大趋于0，与真实网络的高聚类不符。它预测越老的节点度越大，无法解释后来者居上，后续工作因此引入了适应度和老化等机制。对蛋白质相互作用网络，基因复制和分化模型提供了另一种同样能产生重尾的机制。

本文提出的枢纽概念，是后来许多生物网络研究的起点。2000年 Albert 等人比较了无标度网络对随机故障和蓄意攻击的耐受性。2001年 Jeong 等人又研究了蛋白质的致死性与中心性之间的关系。讨论蛋白质网络是否无标度时，既要用到本文的模型，也要用到后来的统计检验方法。

总结一下，作者发现多个真实网络的度分布尾部近似幂律。增长和优先连接两个要素结合，就能自发产生少数枢纽，缺一不可。平均场方法推出指数等于3，与每次加入的边数无关。而真实网络是否严格无标度，需要用最大似然等方法认真检验。建议跟着正文，把指数等于3的推导亲手推一遍。

一句话看懂

如果网络不断增长，并且新节点更愿意连向已经连接很多的节点（“富者愈富”），那么网络的度分布会自发形成幂律 $P(k)\sim k^{-\gamma}$ ，出现少数连接极多的枢纽；两个要素缺一不可。

研究背景与问题

ER 随机图和 WS 小世界模型有一个共同点：度分布在均值附近集中，大度节点出现的概率随 $k$ 指数衰减，几乎不可能出现枢纽。20 世纪 90 年代末，计算机化的数据采集让研究者第一次拿到了大型网络的完整拓扑，例如电影演员合作网和万维网。作者发现这些网络的度分布都有一条很长的尾巴，而现有模型都无法产生这种分布。

论文要回答两个问题：真实网络的度分布是否普遍呈幂律？什么样的生成机制能产生它？

核心思想与方法

作者指出 ER 和 WS 模型都忽略了真实网络的两个共同特点：

增长（growth）：真实网络是开放的，节点数不断增加（新演员、新网页、新论文）；
优先连接（preferential attachment）：新节点连向已有节点的概率不是均匀的，更倾向于连向“知名”的节点。

BA 模型：从 $m_0$ 个节点开始，每一步加入一个新节点，带 $m\ (\le m_0)$ 条边连到 $m$ 个不同的已有节点；连到节点 $i$ 的概率为 $\Pi(k_i)=\frac{k_i}{\sum_j k_j}.$ $t$ 步后网络有 $t+m_0$ 个节点、 $mt$ 条边。

平均场推导的核心是把 $k_i$ 当作连续变量： $\partial k_i/\partial t = k_i/(2t)$ ，解得 $k_i(t)=m\,(t/t_i)^{0.5}$ ，其中 $t_i$ 是节点 $i$ 加入的时刻——越早加入的节点度越大。再假设节点在时间上均匀加入，计算 $P(k_i(t)<k)$ 并对 $k$ 求导，得到稳态解 $P(k)=\frac{2m^2}{k^3},$ 即 $\gamma=3$ ，且与 $m$ 无关。

为证明两个要素都必要，作者构造了两个对照模型：模型 A 保留增长、去掉优先连接（均匀连接），模型 B 保留优先连接、去掉增长（节点数固定，只加边）。

主要发现

真实网络的幂律尾部：演员合作网 $\gamma_{\text{actor}}=2.3\pm0.1$ ；万维网的入度 $\gamma_{\text{www}}=2.1\pm0.1$ ；美国西部电网（4941 个节点）规模较小，标度区不明显，近似 $\gamma_{\text{power}}\approx4$ ；论文引用网络（引用 Redner 的结果） $\gamma_{\text{cite}}=3$ 。作者据此认为指数大致落在 2.1 到 4 之间。
模型产生稳态幂律：数值模拟得到 $\gamma_{\text{model}}=2.9\pm0.1$ ，且分布形状不随网络规模变化。
两个要素缺一不可：模型 A 给出指数分布 $P(k)\sim e^{-\beta k}$ ；模型 B 早期像幂律但不稳定，大约 $N^2$ 步后网络变成完全图。
“富者愈富”： $k_i(t)\propto t^{0.5}$ ，老节点以牺牲新节点为代价持续积累连接。
指数可调：作者指出若一部分边是有向的，指数可变为 $\gamma(p)=3-p$ ；非线性优先连接 $\Pi(k)\sim k^\alpha$ 的模拟显示只有 $\alpha=1$ 时出现标度律。

怎样读这篇论文

先读引言最后一段（作者对全文论点的概括），然后看图 1 的三个实证分布——注意它们都是在双对数坐标上用直线拟合的；接着读模型定义和图 2（模型的度分布、对照模型、 $k_i(t)$ 的标度）；最后跟着正文把 $\gamma=3$ 的推导自己推一遍，这是全文最值得动手的部分。结尾关于社会与经济不平等的讨论可以略读。

局限与后续工作

幂律证据的统计强度：原文的指数来自双对数图上的直线拟合，这在今天看来不够严格。Clauset、Shalizi 与 Newman（2009）提出了最大似然估计加拟合优度检验的流程；Broido 与 Clauset（2019）用这套方法检验近千个网络，发现严格意义上的无标度网络是少数，许多生物网络更接近对数正态或带截断的分布。Barabási 等人则回应：有限规模、度相关性和测量偏倚会使理想幂律变形。这场争论至今仍有分歧，阅读时要区分“重尾”与“严格幂律”。
模型过于简化：BA 模型只能给出 $\gamma=3$ ；它的聚集系数随网络增大趋于 0，与真实网络的高聚类不符；它预测“越老的节点度越大”，无法解释后来者居上。后续工作引入了节点适应度（fitness）、非线性优先连接、边的增删、老化等机制。
机制与现象的区分：模型能产生幂律，并不说明真实网络就是这样生成的。对于蛋白质相互作用网络，基因复制–分化模型提供了另一种同样能产生重尾分布的机制。

关联知识

Barabási–Albert 优先连接模型、 $\gamma=3$ 的推导和小世界与无标度的统计判别中“无标度是否普遍”的讨论都以本文为起点；小世界与无标度网络模型中的交互演示可以直接观察优先连接如何产生枢纽。
分子网络的拓扑特征讨论 PPI 网络的“无标度之争”时，需要用到本文的模型和后来的统计检验方法（该专题的数学推导与算法给出了最大似然拟合的完整流程）。
本文的枢纽概念直接引出了 Albert 等（2000）的鲁棒性研究和 Jeong 等（2001）的致死性–中心性研究，见结构鲁棒性与致死性与中心性：枢纽蛋白假说及其争议。

延伸思考

对蛋白质相互作用网络，“新节点加入”和“优先连接”分别可能对应什么生物学过程？这个类比在哪里会失效？
原文把电网的指数估计为约 4，而电网只有 4941 个节点。用今天的统计方法，你会如何判断这么小的网络是否支持幂律？
BA 模型中 $\gamma$ 与 $m$ 无关。如果改为“新节点以概率 $q$ 均匀连接、以概率 $1-q$ 优先连接”，你预期 $\gamma$ 会怎样变化？可以用平均场方法试推一下。