交通地理学与网络科学/网络形成

网络形成模型

本节将讨论网络形成模型，也称为“生成网络模型”。这些模型解释了为什么网络应该具有某些预先确定的参数（例如幂律度分布）。也就是说，它们模拟创建网络的机制，并探索某些假设的生成机制所产生的网络结构。“如果结构类似于我们在现实世界中观察到的网络结构，它表明 - 尽管没有证明 - 类似的生成机制可能在现实网络中发挥作用。”(Newman，2010)

优先连接

观察到许多网络的度分布近似遵循幂律，至少在分布的尾部是这样。在 1970 年代，Derek Price 首次提出了一个解释这种现象的网络形成模型，该模型受到了经济学家 Herbert Simon 和统计学家 Udny Yule（Yule 过程）作品的启发。Price 扩展了 Simon 对“富者愈富”（也称为幂律分布）在网络背景下的数学解释，将其称为“累积优势”（在 1999 年由 Barabasi 和 Albert 称为优先连接）。

Price 模型

Price 特别将此过程应用于引文网络模型。在这个模型中，论文不断出版（逐个添加），但并不一定以恒定的速度出版，较新的论文引用较旧的论文。该网络中的边是定向的，可以创建但永远不会销毁。Price 模型的核心假设是，新出现的论文以与已引用次数成正比的概率引用以前出现的论文，再加上一个常数 a，其中 a>0。考虑一个 Price 模型网络，其中 $q_{i}$ 表示顶点 i 的入度。现在假设一个新顶点被添加到网络中。那么引用特定顶点（例如 *i*）的概率与 $q_{i}+a$ 成正比。对上述项进行归一化，我们得到由新引入的顶点引用特定顶点（例如 *i*）的概率为：

$p_{i}={\frac {q_{i}+a}{\sum (q_{i}+a)}}$

如果给定论文的平均引用次数为 c，根据网络属性，具有一定的方差，那么随着网络规模变得非常大，网络中具有入度 q 的顶点的比例变为：(Newman，2010 pp- 490-494)

$p_{q}={\frac {B(q+a,2+a/c)}{B(a,1+a/c)}}$

其中

q=入度

a=常数

c=网络的平均出度（或平均参考文献大小）

其中 Beta 函数定义为 $B(x,y)={\frac {\Gamma (x)\Gamma (y)}{\Gamma (x+y)}}$

而 Gamma 函数为 $\Gamma (x)=\int _{0}^{\infty }t^{x-1}e^{-t}\,dt$

此外，Beta 函数对于 x 的大值会以幂律下降，指数为 y。应用此公式，我们发现对于 q 的大值 (q>>a)，度分布变为

$p_{q}\sim q^{-(2+{\frac {a}{c}})}$

因此，Price 对引文网络的模型产生了具有幂律尾部的度分布。更一般地说，每篇论文可以被视为一个节点，每个引文是一个链接。这里，链接以与到达该节点的链接数量成正比的概率添加到现有节点中。

Barabasi 和 Albert 模型

巴拉巴西-阿尔伯特模型在 1990 年代独立开发，是当今最知名的生成网络模型。与普莱斯模型类似，顶点被逐个添加到一个不断增长的网络中，并连接到现有顶点。然而，这些连接是无向的，并且每个顶点所做的连接数量恰好为 c（与普莱斯模型不同，普莱斯模型允许 c 在每次步骤中发生变化）。连接的比例与无向度 k 成正比。通过将巴拉巴西-阿尔伯特模型视为普莱斯模型的一个特例，纽曼在 2010 年证明了：

$p_{k}={\frac {2c(c+1)}{k(k+1)(k+2)}}$

对于 k ≥ c

其中

c=每个顶点所做的连接数

k=顶点的度数

$p_{k}$ 是具有 k 度的顶点的比例。

在这种情况下，当 k 变得非常大时，度数分布变为：

$p_{k}\sim k^{-3}$

优先依附模型的扩展和进一步特性

模型属性/扩展	直观原理	结果分布	贡献者
加入创建时间	通过优先依附，较早的顶点将有更多时间获得链接。	包含领先的代数因子，不遵循幂律分布	(Dorogovsev, Mendes, & Samukhim, 2000)
入射组件的大小	从顶点 i 可以通过遵循有向路径到达的顶点集的分布	对于组件大小 << 网络大小，遵循幂律分布	(Newman, 2010)
增加额外边	在两个现有顶点之间添加连接	幂律分布	(Krapivsky, Rodgers, & Redner, 2001)
删除边	考虑反向优先依附，度数越高，越有可能失去一条边	到一定程度上的幂律分布，然后是拉伸指数	(Moore, Ghoshal, & Newman, 2006)
非线性优先依附	考虑顶点度的非线性依附过程，而不是线性过程	拉伸指数	(Krapivsky, Redner, & Leyvraz, Connectivity of Growing Random Networks, 2000)
质量或吸引力不同的顶点	质量和吸引力被纳入依附过程	取决于“适应度”值的分布	(Bianconi & Barabasi, 2001)

思考问题

还有什么其他网络的形成可以用优先依附来准确描述（考虑普莱斯模型或巴拉巴西-阿尔伯特模型）？

在线模拟

NetLogo 模型库：优先依附

顶点复制模型

虽然优先处理提供了对幂律度数分布的合理解释，但它并不是网络增长的唯一方法（纽曼，2010）。假设新添加的顶点复制了现有顶点的一部分连接，而其余部分由其他现有顶点填充（例如，一篇新论文复制了现有论文的一部分参考文献）。正如纽曼在 2010 年分析的那样，在这个模型下，大型网络的度数分布将渐近地遵循幂律分布（纽曼，2010）。

网络优化模型

以前的网络结构主要基于连续的随机过程，这些过程对正在创建的大规模结构视而不见。一种可能更适合交通网络的网络增长机制是结构优化。在这种情况下，优化涉及旅行时间和成本之间的权衡。这种机制最简单的形式之一是由费雷尔·坎乔和索尔在 2003 年开发的。该模型试图最小化以下质量函数（费雷尔·坎乔和索尔，2003）

$E(e,l)=\lambda e+(1-\lambda )l$

其中

e=网络中的边数

l=顶点对之间的平均测地距离（不满意度量）

λ=范围为 0≤λ≤1 的参数

在这个模型中，维护网络的成本用变量 m 表示。这与说运营航空公司的成本与它运营的航线数量成正比是一样的，例如。以航空公司为例，变量 l 将是完成一次旅程所需的平均航段数量。这显然是对复杂网络的简化。参数 λ 在具有尽可能少边的网络和完全连接的网络之间提供平衡。从该模型可以看出，通过将中等权重置于 λ 上，l 被最小化，最优结果是星形图。这解释了为什么中心枢纽系统如此高效的简单原因（纽曼，2010）。事实证明，非星形图解仅在以下情况下出现： $\lambda <{\frac {2}{n^{2}+2}}$ .

如费雷尔·坎乔和索尔所确定的，该模型的度数分布随着 λ 值的变化从指数分布到幂律分布不等。这仅针对局部最小值提出。

Gastner 和纽曼在 2006 年通过考虑旅程的航段数量以及所走过的地理距离，对费雷尔·坎乔和索尔提出的模型进行了概括（纽曼，2010）。术语 l 被 t 代替，其中 t=u+vr（纽曼，2010）。在这个表达式中，u 和 v 是与链接上的固定时间和速度（1/速度）相关的常数，r 是在链接上行驶的距离。例如，u 可以被认为是机场的登机、等待、滑行等时间，速度是飞行过程中平均速度的倒数。这将空间方面引入模型，而以前只考虑了拓扑考虑因素。然而，该模型也仅产生数值结果。

思考问题

通过改变 Gastner 和 Newman 模型中 u 和 v 的值，可以对所得网络的几何形状得出什么假设？

进一步阅读

网络形成模型综述：稳定性和效率作者：Matthew O. Jackson

计量学和其他累积优势过程的通用理论作者：Derek de S. Price

运输网络中层次结构的出现作者：Bhanu M. Yerra 和 David M. Levinson

另请参见

参考文献

Barabasi, A.-L. 和 Albert, R. (1999). 随机网络中缩放的出现。科学，286，509-512。

Bianconi, G. 和 Barabasi, A.-L. (2001). 复杂网络中的玻色-爱因斯坦凝聚。物理评论快报，86，5632-5635。

Dorogovsev, S. N.，Mendes, J. F. 和 Samukhim, A. N. (2000). 具有优先连接的增长网络的结构。物理评论快报，85，4633-4636。

Ferrer i Cancho, R. 和 Sole, R. V. (2003). 复杂网络的统计力学 (第 625 卷)。(R. Pastor-Satorras、M. Rubi 和 A. Diaz-Guilera 编辑) 柏林：施普林格出版社。

Gastner, M. T. 和 Newman, M. E. (2006). 空间分布网络的最佳设计。物理评论 E，74，016117。

Jackson, M. O. (2005). 网络形成模型综述：稳定性和效率。在 G. Demange 和 M. Wooders (编辑) 中，经济学中的群体形成：网络、俱乐部和联盟 (第 1 章)。剑桥：剑桥大学出版社。

Krapivsky, P. L.，Redner, S. 和 Leyvraz, F. (2000). 增长随机网络的连接性。物理评论快报，85，4629-4632。

Krapivsky, P. L.，Rodgers, G. J. 和 Redner, S. (2001). 增长网络的度分布。物理评论快报，86，5401-5404。

Moore, C.，Ghoshal, G. 和 Newman, M. E. (2006). 节点添加和删除的演化网络模型的精确解。物理评论 E，74 (3)，036121。

Newman, M. E. (2010). 网络：导论。纽约州纽约：牛津大学出版社。

Price, D. d. (1976). 计量学和其他累积优势过程的通用理论。美国信息科学学会期刊，27，292-306。

Rodrigue, J.-P.，Comtois, C. 和 Slack, B. (2009). 运输系统地理学 (第二版)。纽约州纽约：劳特里奇出版社。

Simon, H. A. (1955). 关于一类偏态分布函数。生物统计学，42 (3/4)，425-440。

Wilensky, U. (2005). NetLogo 优先连接模型。http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment. 连接学习与计算机建模中心，西北大学，伊利诺伊州埃文斯顿。

Wilensky, U. (1999). NetLogo。http://ccl.northwestern.edu/netlogo/. 连接学习与计算机建模中心，西北大学，伊利诺伊州埃文斯顿。

Yerra, B. M. 和 Levinson, D. M. (2005). 运输网络中层次结构的出现。区域科学年鉴，39，541-553。