52、无权重图的增长模型

无权重图的增长模型

1. 无权重图增长模型概述

在图论中，无权重图的增长模型是一类重要的研究对象。这类模型的特点是节点数量和边的数量会随时间变化（通常是增长）。在选择图的表示方法时，需要考虑到这种动态变化。而且，在时间 $t$ 时，新到达的节点 $i$ 与现有节点 $j$ 建立新连接的概率 $\theta_{i→j}$ 并非恒定不变，而是随时间变化。例如，在基于度的优先连接模型中，这个概率取决于节点 $j$ 在节点 $i$ 到达时的度值。理论上，每添加一个节点后，都应该重新计算连接概率向量 $\theta_{i→j}$，这通常需要扫描边的列表并更新图中所有节点的度，一般操作数量的阶为 $O(N^2)$ 或更高。不过，增长图模型通常可以非常高效地实现，通常时间复杂度为 $O(K)$，其中 $K$ 是图中最终的边数。这是因为增长模型的每一步通常只会修改相对较少数量节点的度，所以在每个时间点，只需要更新连接概率向量 $\theta_{i→j}$ 的少数条目。

2. 巴拉巴西 - 阿尔伯特（BA）模型

• 模型原理：BA 模型通过合适的增长机制生成具有幂律度分布 $p_k \sim k^{-\gamma}$（其中 $\gamma = 3$）的图。该模型从一个包含 $n_0$ 个节点的完全图开始，在每个时间 $t$ 添加一个新节点 $n$，并将其连接到 $m \leq n_0$ 个已存在的节点。新节点 $n$ 在时间 $t$ 与现有节点 $i$ 连接的概率 $\theta_{n→i}$ 是节点 $i$ 在时间 $t - 1$ 的度 $k_{i,t - 1}$ 的线性函数，即：
  $\theta_{n→i} = \frac{k_{