Barabási–Albert 优先连接模型

两个要素：增长与优先连接

Barabási 和 Albert 注意到 ER 和 WS 模型都假设节点数固定，而真实网络大多在不断增长：网页不断被创建，论文不断被发表，基因在演化中不断复制。他们提出的模型包含两个要素：

1. 增长（growth）：从 $m_0$ 个节点开始，每个时间步加入一个新节点，新节点带 $m$ 条边（$m \le m_0$）连到已有节点；
2. 优先连接（preferential attachment）：新节点连向已有节点 $i$ 的概率与 $i$ 当前的度成正比：

$$\Pi(k_i) = \frac{k_i}{\sum_j k_j}.$$

直观上这就是“富者愈富”：被引用多的论文更容易被看到、被继续引用。这一思想可以追溯到 Yule、Simon 以及 Price（1965、1976）对引文网络的研究。Price 把它称为“累积优势”（cumulative advantage），并提出了有向的引文生长模型：新论文引用旧论文的概率正比于旧论文已有引用数加一个常数（否则没被引用过的论文永远不会被引用）。BA 模型可以看作 Price 模型的无向版本，常数项取零。

主要结论

平均场分析（推导见数学推导与算法）给出两个结论：

• 每个节点的度按 $k_i(t) = m\,(t/t_i)^{1/2}$ 增长，越早加入的节点（$t_i$ 越小）度越大——先到者优势；
• 度分布为 $P(k) \approx 2m^2/k^3$，即 $\gamma = 3$ 的幂律，而且指数与 $m$ 无关。用速率方程可得精确解 $P(k) = \dfrac{2m(m+1)}{k(k+1)(k+2)}$，大 $k$ 时与平均场结果一致（Dorogovtsev、Mendes 与 Samukhin 2000；Krapivsky、Redner 与 Leyvraz 2000；严格证明见 Bollobás 等 2001）。

由 $k_i(t)=m(t/t_i)^{1/2}$ 还能看出：最大的枢纽是最早的节点，其度 $k_{\max}\sim m\,t^{1/2}=mN^{1/2}$，正好等于 $\gamma=3$ 时的自然截断 $N^{1/(\gamma-1)}$。

本专题页面的 BA 演示可以逐步加点，在双对数图上观察度分布的形成。

两个要素缺一不可

• 只有增长、没有优先连接（Barabási 书中的“模型 A”：新节点均匀随机地连接已有节点）：$dk_i/dt=m/t$，度只按对数增长 $k_i=m+m\ln(t/t_i)$，度分布变为指数分布 $p_k=\dfrac{e}{m}e^{-k/m}$，没有幂律尾巴；
• 只有优先连接、没有增长（“模型 B”：节点数 $N$ 固定，每步按优先连接加一条边）：所有节点的度都近似线性增长 $k_i\approx 2t/N$，度分布先短暂呈长尾，随后变成以平均度为中心的窄峰，最后趋于完全图——幂律只是暂态。

距离与聚集

• 平均距离：$m\ge2$ 时 BA 网络的平均距离按 $\ln N/\ln\ln N$ 增长（Bollobás 与 Riordan 2004；Cohen 与 Havlin 2003），比同规模随机网络还短；$m=1$ 时网络是一棵树，距离按 $\ln N$ 增长。
• 聚集系数：$\langle C\rangle\propto (\ln N)^2/N$（Fronczak 等 2003），比随机网络的 $1/N$ 下降得慢，但随规模增大仍趋于 0，远低于多数真实网络。

BA 模型的局限与扩展

BA 模型只能产生 $\gamma=3$，而真实网络的指数差异很大；它的聚集系数随 $N$ 增大而趋于 0，与真实网络的高聚类不符；它预测“老节点度大”，但现实中后来者常能反超（Google 晚于许多搜索引擎出现）；它也没有说明优先连接本身从何而来。后续的工作沿几个方向展开，本专题依次介绍：

• 优先连接能否从数据中测到，以及非线性时会怎样（测量优先连接与非线性优先连接）；
• 优先连接的局部来源，以及加入三角形闭合以提高聚类（优先连接从何而来）；
• 节点适应度让后来者反超（适应度模型与玻色–爱因斯坦凝聚）；
• 初始吸引力、内部连边、删点、加速增长、老化改变度指数（演化网络的扩展模型）；
• 与生物学关系最密切的复制–分化模型：基因复制后，新基因继承原基因的相互作用伙伴，随后部分相互作用丢失。度大的蛋白有更多邻居，邻居被复制的机会更多，因此复制机制在效果上等价于一种优先连接，同样能产生长尾度分布（复制–分化模型）。