第 02 章精校翻译：随机图模型
第 2 章 随机图模型（Random Graph Models）
本章致力于介绍复杂网络的基本模型。我们引入若干类重要的随机图模型，并展示和研究这些模型的一些统计性质，例如度分布与连通性。
记号 在后文中，$G = (V, E)$ 表示一个图，其中 $V = \{1, \ldots, n\}$ 是顶点（节点）集，$E$ 是边（连接）集。如果图 $G$ 由某个随机图模型生成，我们称 $G$ 为随机图（random graph）。随机图模型指的是所有图所构成集合上的一个概率分布。
我们用 $d_i$ 表示节点 $i$ 的度（degree）。向量 $d = (d_1, \ldots, d_n)$ 称为节点的度序列（degree sequence）。给定一个随机图模型，节点 $i$ 的度 $d_i$ 是一个随机变量，服从某个概率分布。当所有的度同分布时（即 $d_1, \cdots, d_n$ 都服从同一概率分布 $\mathcal{D}$），我们称图 $G$ 中的度服从度分布（degree distribution）$\mathcal{D}$。
2.1 Erdős–Rényi 随机图（Erdős–Rényi Random Graphs）
2.1.1 定义（Definition）
设 $n$ 为整数，$P = (p_{ij})_{1 \leq i < j \leq n} \in [0, 1]^{n \times n}$ 为一组概率。伯努利随机图（Bernoulli random graph） $G = (V, E)$ 是满足以下条件的无向、无权重图 $G$：
- $V = \{1, \ldots, n\}$；
- 对所有满足 $1 \leq i < j \leq n$ 的节点对 $(i, j)$，$\mathbb{P}\big((i, j) \in E\big) = p_{ij}$。
我们记 $G \sim \mathcal{G}(n, (p_{ij}))$。在伯努利随机图中，每个节点对 $(i, j)$ 以概率 $p_{ij}$ 由一条边相连，且独立于所有其他节点对。
若 $G \sim \mathcal{G}(n, (p_{ij})_{1 \leq i < j \leq n})$，则 $G$ 的邻接矩阵（adjacency matrix） $A$ 是一个对称随机矩阵，其各元素独立分布，满足 $A_{ij} = A_{ji} \sim \mathrm{Ber}(p_{ij})$ 且 $A_{ii} = 0$。
设 $G \sim \mathcal{G}(n, (p_{ij}))$，$A$ 为其对应的邻接矩阵。则有：
$$ \mathbb{P}(A) = \prod_{i < j} p_{ij}^{A_{ij}} (1 - p_{ij})^{1 - A_{ij}} . $$ 在学习笔记中查看逐步完整证明边抽样过程的独立性保证了
$$ \mathbb{P}(A) = \prod_{1 \leq i < j \leq n} \mathbb{P}\left(A_{ij}\right) . $$此外，
$$ \mathbb{P}\left(A_{ij}\right) = \left\{ \begin{array}{ll} p_{ij} & \text{若 } A_{ij} = 1 \\ 1 - p_{ij} & \text{若 } A_{ij} = 0 \end{array} , \right. $$而这可以方便地改写为 $\mathbb{P}(A_{ij}) = p_{ij}^{A_{ij}} (1 - p_{ij})^{1 - A_{ij}}$。
设对所有 $i, j$ 都有 $p_{ij} = p$。此时 $\mathcal{G}(n, (p_{ij}))$ 称为 Erdős–Rényi 模型1，传统上记作 $\mathcal{G}(n, p)$ 或 $\mathcal{G}_{n, p}$。
设 $G \sim \mathcal{G}_{n, p}$，$A$ 为其对应的邻接矩阵。则有
$$ \mathbb{P}(A) = (1 - p)^{\frac{n(n-1)}{2}} \left( \frac{p}{1 - p} \right)^{|E|} , $$其中 $|E|$ 是 $G$ 的边数。
在学习笔记中查看逐步完整证明利用命题 2.1，可以写出
$$ \mathbb{P}(A) = \prod_{i < j} p^{A_{ij}} (1 - p)^{1 - A_{ij}} = \prod_{i < j} (1 - p) \left( \frac{p}{1 - p} \right)^{A_{ij}} . $$注意到 $|E| = \sum_{i < j} A_{ij}$ 即得结论。
算法 1 给出了一种生成 Erdős–Rényi 随机图的简单方法：遍历所有可能的节点对 $(i, j)$，并以概率 $p$ 把 $(i, j)$ 加入边列表。
输入：节点数 $n$，连边概率 $p \in [0, 1]$。
输出：边列表 $E$。
过程：
- $E \leftarrow \emptyset$；
- for $i = 1$ to $n - 1$ do
- for $j = i + 1$ to $n$ do
- $x \leftarrow$ 0 与 1 之间的随机数；
- if $x < p$ then 把边 $(i, j)$ 加入 $E$。
- for $j = i + 1$ to $n$ do
返回：$E$。
算法 1 的空间复杂度为 $O(|E|)$（对应于存储 $|E|$ 条边），而其时间复杂度为 $O(n^2)$。特别地，当 $p$ 很小时它非常低效：事实上，此时大多数节点对 $(i, j)$ 不会相连，而我们测试它们就是在浪费时间。换句话说，从节点 $i$ 出发，节点对 $(i, i+1), \dotsc, (i, i+k-1)$ 都不会相连，而节点对 $(i, i+k)$ 会产生一条边。这个数 $k$ 表示一列独立伯努利随机变量中首次成功出现之前的失败次数，因此它服从参数为 $p$ 的几何分布。基于这一观察，Batagelj 和 Brandes（2005）提出了算法 2，用于高效生成稀疏（sparse）的 Erdős–Rényi 图。它的空间复杂度和时间复杂度都是 $O(|E|)$。
输入：节点数 $n$，连边概率 $p \in [0, 1]$。
输出：边列表 $E$。
过程：
- $E \leftarrow \emptyset$；
- $i \leftarrow 0$；
- for $i = 1$ to $n - 1$ do
- $v \leftarrow i$；
- while $v \leq n$ do
- $k \leftarrow$ 参数为 $p$ 的几何随机变量的一个实现；
- $v \leftarrow v + k$；
- if $v \leq n$ then 把边 $(i, j)$ 加入 $E$。
返回：$E$。
2.1.2 度分布（Degree Distribution）
设 $G \sim \mathcal{G}(n, p)$，$d_i$ 为节点 $i$ 的度。则 $d_i$ 服从二项分布 $\mathrm{Bin}(n, p)$。特别地，图的平均度 $\bar{d}$ 等于 $np$。
在学习笔记中查看逐步完整证明与有限样本口径事实上，节点 $i$ 的度记为 $d_i$，等于 $\sum_{j = 1}^{n} A_{ij}$，其中 $A_{ij}$ 是参数为 $p$ 的独立同分布伯努利随机变量。
人们观察到，许多真实图的度分布是重尾（heavy-tailed）的（例如幂律（power law）），而非二项分布（参见第 1.2 节的讨论）。一个直观的论证如下：由于二项分布集中性很好，Erdős–Rényi 图不会允许存在太多枢纽（hub，即度远高于平均度的节点），而我们在真实网络中却往往能看到这样的节点（例如，在社交网络中，一些人的连接数远多于其他人，并扮演着“网红”或枢纽的角色）。因此，基本的 Erdős–Rényi 随机图并不是许多真实网络的合适模型。
2.1.3 相变现象（Phase Transition Phenomena）
启发式讨论（Heuristic）
本节考虑 Erdős–Rényi 图序列 $(G_1, \dots, G_n, \dots)$，其中 $G_n$ 有 $n$ 个节点，连边概率 $p_n$ 依赖于 $n$。换句话说，$G_n \sim \mathcal{G}(n, p_n)$。我们特别强调两种标度情形（regime）：
- 情形 $p_n = \frac{a}{n}$，其中 $a$ 为常数；
- 情形 $p_n = a \frac{\log n}{n}$，其中 $a$ 为常数。
由于期望度 $\bar{d}_n = n p_n$ 在第一种情形等于 $a$、在第二种情形等于 $a \log n$，2 这两种标度情形分别称为常数度情形（constant degree regime）与对数度情形（logarithmic degree regime）。图 2.1 与图 2.2 分别展示了给定 $n = 100$ 时，常数度情形与对数度情形下 Erdős–Rényi 图的例子。在常数度情形下，我们观察到以下现象：
- 当 $\bar{d}_n < 1$ 时，大多数节点是孤立的——这在意料之中，因为 $\bar{d}_n < 1$ 意味着一个节点平均只有不到一个邻居；
- 当 $\bar{d}_n > 1$ 时，似乎存在一个包含大多数节点的连通分量（connected component）。我们称这个分量为巨分量（giant component）。
另一方面，在对数度情形下，我们看到：
- 若 $\bar{d}_n < \log n$，图看起来不连通，因为仍有一些孤立节点或孤立边；
- 相反，当 $\bar{d}_n > \log n$ 时，图看起来是完全连通的。
这些观察进一步由图 2.3 得到加强。在常数度情形 $p_n = \frac{a}{n}$ 下，图 2.3(a) 显示：当 $a < 1$ 时，最大连通分量中的节点比例微乎其微；但一旦 $a > 1$，这一比例就变得不可忽略，并随 $a$ 稳步增大。类似地，在对数度情形 $p_n = a \frac{\log n}{n}$ 下，图 2.3(b) 显示：一旦 $a$ 大于 1，图连通的经验概率就从 0 跳到 1。
主要命题（Main statements）
现在给出两条主要命题，为之前的启发式观察提供严格依据。
设 $G \sim \mathcal{G}(n, p_n)$ 为 Erdős–Rényi 图，其中 $p_n = \frac{a}{n}$，$a$ 为常数。以下结论几乎必然成立：
- (a) 若 $a < 1$，则不存在规模大于 $O(\log n)$ 的连通分量；
- (b) 若 $a = 1$，则存在一个规模为 $O(n^{2/3})$ 的大分量；
- (c) 若 $a > 1$，则存在唯一一个规模为 $O(n)$ 的分量。这个分量称为巨分量。
定理 2.1 的证明较为复杂，本书不予呈现。我们推荐感兴趣的读者参考 (Hofstad, 2016)。
设 $G_n \sim \mathcal{G}(n, p_n)$ 为 Erdős–Rényi 随机图序列。记 $\bar{d}_n = n p_n$。以下结论成立：
- (a) 若存在序列 $(\omega_n)_n$ 满足 $\omega_n \to +\infty$，使得 $\bar{d}_n < \log n - \omega_n$，则 $G_n$ 几乎必然不连通。更精确地说，图 $G_n$ 几乎必然含有至少一个孤立节点；
- (b) 若存在序列 $(\omega_n)_n$ 满足 $\omega_n \to +\infty$，使得 $\bar{d}_n > \log n + \omega_n$，则 $G_n$ 几乎必然连通。
设 $\bar{d}_n = \log n + \log \log n$，$G_n \sim \mathcal{G}(n, p_n)$。则定理 2.2 表明，渐近地 $G_n$ 几乎必然连通（可取 $\omega_n = \log \log n$）。
若 $\bar{d}_n = a \log n$（$a$ 为常数），则定理 2.2 以 $\omega_n = (a - 1) \log n$ 适用。因此 $a > 1$ 时 $G_n$ 将连通，$a < 1$ 时将不连通。特别地，这证实了图 2.3(b) 中的启发式观察。
连通性相变的证明（Proof of the connectivity phase transition）
在证明定理 2.2 之前，先看下面这个关于 Erdős–Rényi 图中孤立节点存在性的引理。
Erdős–Rényi 图 $G_n \sim \mathcal{G}(n, p_n)$ 含有至少一个孤立节点的概率满足
$$ \lim_{n \to \infty} \mathbb{P}(\exists\ \text{孤立节点}) = \left\{ \begin{array}{ll} 0 & \text{若对某个 } \omega_n \to +\infty \text{ 有 } p_n \geq \frac{\log n + \omega_n}{n} , \\ 1 & \text{若对某个 } \omega_n \to +\infty \text{ 有 } p_n \leq \frac{\log n - \omega_n}{n} . \end{array} \right. $$ 在学习笔记中查看逐步完整证明该引理表明：若 $p_n \leq \frac{\log n - \omega_n}{n}$，则图几乎必然含有一个孤立节点，因而图几乎必然不连通。这恰好对应定理 2.2 的 (a) 部分。
记 $A_i$ 为事件“节点 $i$ 是孤立的”，令 $I_n = \sum_{i = 0}^{n} \mathbf{1}(A_i)$ 为孤立节点的数目。回忆 $\bar{d}_n = n p_n$ 是平均度。我们有
$$ \mathbb{P}(A_i) = (1 - p_n)^{n-1} = \left(1 - \frac{\bar{d}_n}{n}\right)^{n-1} \sim \exp\left(-\bar{d}_n\right) \sim \frac{1}{n} \exp(\mp \omega_n) , $$从而
$$ \mathbb{E}\left(I_n\right) = \sum_{i = 0}^{n} \mathbb{P}(A_i) = n \mathbb{P}(A_1) \sim e^{\mp \omega_n} . $$(i) 若 $\bar{d}_n = \log n + \omega_n$，则 $\mathbb{E}(I_n) \sim e^{-\omega_n} \to 0$。既然孤立节点的期望数目趋于 $0$，就可以用一阶矩方法（first moment method）完成证明。事实上，回忆马尔可夫不等式（见命题 A.6 与推论 A.2）给出：
$$ \mathbb{P}\big(\exists\ \text{孤立节点}\big) = \mathbb{P}(I_n \geq 1) \leq \frac{\mathbb{E} I_n}{1} \longrightarrow 0 . $$(ii) 若 $\bar{d}_n = \log n - \omega_n$，则 $\mathbb{E}(I_n) \sim e^{+\omega_n} \to +\infty$，孤立节点的期望数目趋于无穷。不幸的是，这不足以对孤立节点的存在概率得出任何结论，我们需要二阶矩方法（second moment method）。事实上，我们必须证明随机变量 $I_n$ 在其均值附近集中得很好；由于其均值发散到无穷，结论即可由此推出。为此，我们将使用切比雪夫不等式（命题 A.7）。我们有
$$ \operatorname{Var}\left(I_n\right) = \mathbb{E}\left(I_n^2\right) - (\mathbb{E} I_n)^2 . $$注意
$$ \mathbb{E}\left(I_n^2\right) = \mathbb{E}\left(\sum_i \sum_j \mathbf{1}(A_i) \mathbf{1}(A_j)\right) = \sum_i \sum_j \mathbb{P}\left(A_i, A_j\right) = n \mathbb{P}\big(A_1\big) + n(n-1) \mathbb{P}\big(A_1 \cap A_2\big) . $$这里需要小心，因为 $A_1$ 与 $A_2$ 并不独立。事实上，知道节点 1 孤立意味着节点 1 与节点 2 之间没有边，从而（弱）增加了节点 2 孤立的概率。我们有：
$$ \mathbb{P}\big(A_1 \cap A_2\big) = \mathbb{P}\big(A_2 \mid A_1\big) \, \mathbb{P}\big(A_1\big) = (1 - p_n)^{n-2} \, \mathbb{P}\big(A_1\big) = \frac{1}{1 - p_n} \big(\mathbb{P}\big(A_1\big)\big)^2 , $$因为 $\mathbb{P}\big(A_1\big) = (1 - p_n)^{n-1}$。最后，
$$ (\mathbb{E} I_n)^2 = \left(\sum_i \mathbb{P}\left(A_i\right)\right)^2 = \sum_i \sum_j \mathbb{P}(A_i) \mathbb{P}(A_j) = \sum_i \sum_j \mathbb{P}(A_1)^2 = n^2 \mathbb{P}(A_1)^2 . $$把所有部分拼在一起，得到
$$ \begin{aligned} \operatorname{Var}(I_n) &= n \mathbb{P}\big(A_1\big) + n(n-1) \mathbb{P}\big(A_1 \cap A_2\big) - n^2 \mathbb{P}(A_1)^2 \\ &= n \mathbb{P}\big(A_1\big) + \frac{n(n-1)}{1 - p_n} \mathbb{P}\big(A_1\big)^2 - n^2 \mathbb{P}\big(A_1\big)^2 \\ &\leq n \mathbb{P}\big(A_1\big) + \frac{n^2}{1 - p_n} \mathbb{P}\big(A_1\big)^2 - n^2 \mathbb{P}\big(A_1\big)^2 \\ &= n \mathbb{P}\big(A_1\big) + n^2 \mathbb{P}\big(A_1\big)^2 \left(\frac{1}{1 - p_n} - 1\right) \\ &= \mathbb{E}\left(I_n\right) + (\mathbb{E} I_n)^2 \frac{p_n}{1 - p_n} . \end{aligned} $$因此，由二阶矩方法（见推论 A.5），
$$ \mathbb{P}(I_n = 0) \leq \frac{\operatorname{Var}(I_n)}{\big(\mathbb{E}(I_n)\big)^2} \leq \frac{1}{\mathbb{E}(I_n)} + \frac{p_n}{1 - p_n} . $$由于 $\mathbb{E} I_n \to \infty$ 且 $p_n \to 0$，当 $n$ 趋于无穷时，最后这个量趋于零。
现在可以证明定理 2.2 的 (b) 部分。
设 $\bar{d}_n \geq \log n + \omega_n$。此时引理 2.4 表明孤立节点的数目 $I_n$ 为零。要证明 $G_n$ 确实连通，需要证明
$$ \mathbb{P}\left(G_n \text{ 不连通且 } I_n = 0\right) \to 0 . $$若 $G_n$ 不连通且没有孤立节点，则 $G_n$ 含有一个规模满足 $2 \leq k \leq \lfloor n / 2 \rfloor$ 的连通分量 $\mathcal{C}_k$。直接数规模为 $k$ 的分量的期望数目是困难的，因为它们出现的概率取决于其内部边数的确切数目（若 $\mathcal{C}_k$ 是一棵树，边数可低至 $k - 1$；若 $\mathcal{C}_k$ 是完全图，边数可高达 $\frac{k(k-1)}{2}$）。为避开这一困难，我们注意分量 $\mathcal{C}_k$ 含有生成树。所谓 $\mathcal{C}_k$ 的生成树（spanning tree），是指 $\mathcal{C}_k$ 的一个子图，它是一棵包含 $\mathcal{C}_k$ 全部顶点的连通树。注意 $\mathcal{C}_k$ 可以含有不止一棵生成树。
记 $X_k$ 为规模为 $k$ 的生成树的数目。由上面的观察，$X_k$ 不小于规模为 $k$ 的连通分量的数目。此外，若 $G_n$ 不连通且没有孤立节点，则必存在某个 $k \in \{2, \ldots, \lfloor n / 2 \rfloor\}$ 使得 $X_k \geq 1$。因此，由并界（union bound）与一阶矩方法，
$$ \mathbb{P}\left(G_n \text{ 不连通且 } I_n = 0\right) \leq \mathbb{P}\left(\bigcup_{k = 2}^{\lfloor n / 2 \rfloor} \{X_k \geq 1\}\right) \leq \sum_{k = 2}^{\lfloor n / 2 \rfloor} \mathbb{P}\left(X_k \geq 1\right) \leq \sum_{k = 2}^{\lfloor n / 2 \rfloor} \mathbb{E} X_k . \tag{2.1} $$我们需要界定 $\mathbb{E} X_k$。首先，从 $n$ 个节点中选取 $k$ 个顶点 $(v_1, \ldots, v_k)$ 有 $\binom{n}{k}$ 种方式。选定这 $k$ 个顶点后，由凯莱定理［见 (Hofstad, 2016) 的定理 3.17］，包含这些顶点的树可能有 $k^{k-2}$ 棵。由于这 $k$ 个顶点在 $G_n$ 中构成一棵树，它们由 $k - 1$ 条边相连，其发生概率为 $p_n^{k-1}$。最后，图 $G_n$ 在这棵树与其余部分之间不应含有任何边：其概率为 $(1 - p_n)^{k(n-k)}$。综上，
$$ \mathbb{E} X_k = \binom{n}{k} k^{k-2} p_n^{k-1} (1 - p_n)^{k(n-k)} . $$应用 Stirling 界 $k! \geq k^k e^{-k}$，有 $\binom{n}{k} \leq (n e / k)^k$。此外 $(1 - p_n)^{k(n-k)} \leq e^{-p_n k(n-k)} \leq e^{-k n p_n / 2}$，且 $n p_n \geq 1$。于是
$$ \mathbb{E} X_k \leq n \frac{e}{k^2} \left(n p_n e\right)^{k-1} e^{-k n p_n / 2} \leq n \left(n p_n e^{1 - n p_n / 2}\right)^k . $$注意函数 $f(x) = x e^{1 - x / 2}$ 在 $x \geq 2$ 时递减。由于 $n p_n = \log n + \omega_n$，对充分大的 $n$ 有 $n p_n \geq \log n$。因此
$$ \mathbb{E} X_k \leq n \left(\log n \, e^{1 - \log n / 2}\right)^k \leq n \left(\frac{e \log n}{2 \sqrt{n}}\right)^k , $$并且对任意 $m \geq 1$，
$$ \sum_{k = m}^{\lfloor n / 2 \rfloor} \mathbb{E} X_k \leq n \left(\frac{e \log n}{2 \sqrt{n}}\right)^m \left(\frac{1}{1 - \frac{e \log n}{2 \sqrt{n}}}\right) \leq 2 n \left(\frac{e \log n}{2 \sqrt{n}}\right)^m , $$其中用到了对充分大的 $n$ 有 $\frac{e \log n}{2 \sqrt{n}} \leq \frac{1}{2}$。上面的估计是粗糙的，但已足以证明 $\sum_{k = 2}^{\lfloor n / 2 \rfloor} \mathbb{E} X_k$ 收敛到零。证明 $\mathbb{E} X_1$ 趋于零是直接的（immediate），回到式 (2.1) 即得
定理 2.2 的 (b) 部分由此得证。
2.2 其他随机图模型（Other Random Graph Models）
2.2.1 配置模型（Configuration Model）
本节的目标是构造一个拟合给定度序列 $d = (d_1, \ldots, d_n)$ 的随机图 $G_n$。这意味着图 $G_n$ 应有 $n$ 个节点，且边的抽取使得节点 $i$ 的度为 $d_i$。先作几点说明。
- 我们可以假设 $d_i \geq 1$，因为 $d_i = 0$ 意味着节点 $i$ 是孤立的。
- 存在一个满足度要求的图并不是显然的。事实上，这样的图不一定存在。例如，若假设图是无权重的，则 $\sum_{i = 1}^{n} d_i$ 必须是偶数（因为这个和等于边数的两倍）。
- 即使假设 $\sum_{i = 1}^{n} d_i$ 是偶数，这样的图也不总是能够构造出来。为避免这些问题，我们将允许自环（self-loop）与重边（multi-edge）。
设 $d = (d_1, \ldots, d_n)$ 是一个满足 $\sum_{i = 1}^{n} d_i$ 为偶数的序列。在每个节点 $i \in \{1, \ldots, n\}$ 上挂上 $d_i$ 条半边（half-edge，又称 stub）。然后把这些半边均匀地随机两两配对。所得的图称为度序列为 $d$ 的配置模型（configuration model），简记为 $\mathrm{CM}_n(d)$。
该模型允许重边与自环。此外，按惯例一个自环在节点的度中计为 2，因为它来自两条半边。算法 3 生成一个配置模型图。
输入：度序列 $(d_1, \ldots, d_n)$。
输出：边列表 $E$。
过程：
- if $\sum_{i = 1}^{n} d_i$ 为奇数 then 返回一个错误；
- else
- $E \leftarrow \emptyset$；$L \leftarrow \emptyset$；
- for $i = 1$ to $n$ do for $k = 1$ to $d_i$ do 把 $i$ 加入列表 $L$；
- 打乱 $L$ 中元素的顺序；
- $j \leftarrow 0$；
- while $j \leq |L|$ do 把边 $\big(L[j], L[j+1]\big)$ 加入 $E$；$j \leftarrow j + 2$。
返回：$E$。
若 $d_1 = \cdots = d_n = d$，则得到一个随机 $(n, d)$-正则图（random $(n, d)$-regular graph）（即一个有 $n$ 个节点、且所有节点的度都等于 $d$ 的随机图）。我们在图 2.4 中画出了一些例子。
若随机变量 $X$ 几乎必然取值于 $\{1, \cdots, n\}$，且对 $k \in [n]$ 有 $\mathbb{P}(X = k) = C^{-1} k^{-s}$，其中 $C = \sum_{k = 1}^{n} k^{-s}$ 为归一化常数，则称 $X$ 服从参数为 $n$ 与 $s$ 的 Zipf 分布（Zipfian distribution）。图 2.5 画出了取自配置模型的一些图，其中 $d_i$ 采样自 Zipf 分布。
2.2.2 优先连接模型（Preferential Attachment Model）
动机（Motivation）
之前的模型都是静态的，即节点数目是固定的。此外，它们也没有解释真实图中那些有趣性质（重尾度分布等）是如何产生的。本节给出一个增长式随机图的例子，其中节点与边随时间逐步加入。
第一种可能是构造一个图序列 $(G_n)_{n \in \mathbb{N}}$，使每个 $G_n$ 都是一个 Erdős–Rényi 图 $\mathcal{G}(n, p)$。图 $G_{n+1}$ 由 $G_n$ 按如下方式构造：$G_n$ 中的边被复制到 $G_{n+1}$，而形如 $(i, n+1)$（$i = 1, \cdots, n$）的边以概率 $p$ 独立加入。于是新图 $G_{n+1}$ 是一个 $\mathcal{G}_{n+1, p}$，且 $G_n$ 是 $G_{n+1}$ 的子图。问题在于其度序列是二项分布，因而不能拟合我们在大多数真实网络中观察到的现象。
优先连接（preferential attachment）范式为我们在现实中似乎观察到的幂律度分布提供了一个直观的解释。在这一范式中，新节点 $n+1$ 将通过若干条新增的边与已有的 $n$ 个节点相连。这些新边 $(i, n+1)$ 独立抽取，其概率正比于顶点 $i$ 当时的度。因此，新节点 $n+1$ 更可能与度大的节点相连。
在时刻 $t$，一个新节点将以正比于已有节点 $i$（在时刻 $t$）的度 $d_i(t)$ 的概率与该已有节点相连。
由这个定义，我们可以作出以下评注：
- 老节点的度将倾向于比新节点更高；
- “富者愈富”（the rich gets richer）现象：新节点倾向于连接度大的老节点。特别地，我们预期会形成枢纽。
图将含有枢纽这一事实使我们猜想：度分布将不是二项分布，而可能呈现幂律。我们将在命题 2.3 中确立这一点，在此之前先给出该模型的严格定义。
“优先连接”一词来自 Barabási 和 Albert（1999），他们提出了一个类似的模型，尽管定义并不严格。他们的模型实际上与更早的 Yule（1925）和 Solla Price（1976）的工作相近。关于完全严格的处理，我们参考 Bollobás et al.（2001）和 Hofstad（2016）。
模型定义（Model definition）
若图序列 $\left\{ G_t = (V_t, E_t),\ t \in \mathbb{N} \right\}$ 满足以下条件，则称其取自优先连接模型（Preferential Attachment Model）：
- $|V_1| = 1$ 且 $|E_1| = 1$：在时间步 $t = 1$，我们有一个节点 $v_1$，带有一个自环；
- 在时间步 $t + 1$，我们把节点 $v_{t+1}$ 加入图中。该节点将与一个（且仅一个）节点相连。新节点与节点 $v_i$ 相连的概率为 $$ \mathbb{P}\Big( (v_{t+1}, v_i) \in E_{t+1} \,\big|\, G_t \Big) = \left\{ \begin{array}{ll} \frac{1}{2t + 1} & \text{若 } v_i = v_{t+1} \\ \frac{d_i(t)}{2t + 1} & \text{其他} , \end{array} \right. \tag{2.2} $$
其中 $d_i(t)$ 是节点 $v_i$ 在时刻 $t$ 的度（回忆按惯例，一个自环使度增加 2）。
我们在图 2.6 中展示了一些取自优先连接模型的图。
经过 $t$ 个时间步后，优先连接模型得到一个具有 $|V_t| = t$ 个节点和 $|E_t| = t$ 条边的网络。特别地，式 (2.2) 定义了一个概率分布。
在学习笔记中查看逐步完整证明事实上，每个时间步我们加入一个节点，所以 $|V_t| = t$。此外，每个时间步只加入一条边。最后，由于 $\sum_{i = 1}^{t} d_i(t) = 2 |E_t| = 2t$，有 $\sum_{i = 1}^{t + 1} \mathbb{P}\Big( (v_{t+1}, v_i) \in E_{t+1} \,\big|\, G_t \Big) = 1$。
Hofstad（2016）中描述了优先连接模型的一个更一般的版本。定义 2.4 对应于那里 $m = 1$ 且 $\delta = 0$ 的情形。
优先连接模型的度分布（Degree distribution of the preferential attachment model）
现在考察取自优先连接模型的图的度分布。图 2.7 给出了度的直方图。特别地，我们看到在 log-log 尺度下曲线似乎是线性的。记 $N_k$ 为度为 $k$ 的节点数目。图 2.7(b) 似乎表明 $\log N_k = -\alpha \log k + C$，其中 $\alpha = -3$，$C$ 为常数。这进而蕴含 $N_k \propto k^{-3}$，即度分布服从指数为 3 的幂律。命题 2.3 的确证明了这一点。
当 $t \to +\infty$ 时，优先连接模型呈现指数为 3 的幂律度分布。
查看学习笔记中的严格化推导与证明边界设 $s \in \{1, \ldots, t\}$，记 $p(k, s, t)$ 为顶点 $v_s$ 在时刻 $t$ 度为 $k$ 的概率。$p(k, s, t)$ 的演化由主方程（master equation）描述：
$$ p(k, s, t + 1) = \frac{k - 1}{2t + 1} p(k - 1, s, t) + \left(1 - \frac{k}{2t + 1}\right) p(k, s, t) , \tag{2.3} $$初始条件为 $p(k, 1, 1) = \delta_{k, 1}$，边界条件为 $p(k, t, t) = \delta_{k, 1}$。其中 $\frac{k - 1}{2t + 1}$ 表示新节点 $v_{t+1}$ 在时刻 $t + 1$ 与节点 $v_s$ 相连的概率（从而使 $s$ 的度增加 1），$\left(1 - \frac{k}{2t + 1}\right)$ 是新节点 $v_{t+1}$ 不与节点 $v_s$ 相连的概率。
记 $P(k, t)$ 为整个网络的总度分布，即 $p(k, s, t)$ 在时刻 $t$ 存在的所有节点 $v_s \in [t]$ 上的平均。我们有
$$ P(k, t) = \frac{1}{t} \sum_{s = 1}^{t} p(k, s, t) . $$利用式 (2.3)，得到
$$ (t + 1) P(k, t + 1) = \frac{k - 1}{2t + 1} \, t P(k - 1, t) + \left(1 - \frac{k}{2t + 1}\right) t P(k, t) . $$因此，$P(k, t)$ 的时间演化可以写成
$$ (t + 1) P(k, t + 1) - t P(k, t) = \frac{t}{2t + 1} \Big( (k - 1) P(k - 1, t) - k P(k, t) \Big) + \delta_{k, 1} . $$当 $t \to +\infty$ 时，这个关于平稳分布的方程化为
$$ P(k) + \frac{1}{2} \Big( k P(k) - (k - 1) P(k - 1) \Big) = \delta_{k, 1} , $$其中 $P(k)$ 表示 $\lim_{t \to +\infty} P(k, t)$。
最后这个方程是微分方程
$$ P(k) + \frac{1}{2} \frac{\mathrm{d} \, k P(k)}{\mathrm{d} k} = 0 $$的离散版本，该微分方程的解为
$$ P(k) = C k^{-3} , $$归一化因子 $C$ 使得 $\sum_k P(k) = 1$（即 $C = \sum_{k = 1}^{\infty} k^{-3}$）。
上述证明并不完全严格，因为其中涉及一些需要严格论证的近似。不过，它很好地解释了优先连接过程的本质。关于一个数学上更深入（但严格）的证明，以及关于优先连接模型的其他更深刻结果，我们参考 Hofstad（2016）。特别地，更复杂的模型（新节点与多个节点相连，或/和每个时间步加入多个新节点）会产生各种指数的幂律。
查看学习笔记对主方程推导严格性问题的注记
2.2.3 空间网络：随机几何图等（Spatial Networks: Random Geometric Graphs, etc）
在许多情形中，节点位于一个度量空间内（例如 $\mathbb{R}^2$ 或球面 $\mathbf{S}_2$），两个节点之间的相互作用直接取决于它们在该空间中的距离。例子包括无线与传感器网络中的基站——两个设备只要相距不太远就会相连。此外，在许多网络中，节点带有属性或特征（如性别、年龄、年级、类型等），这些属性也可以表示为某个度量空间中的位置，并影响连边的形成。例如在社交网络中，年龄和/或性别相近的用户通常联系更多。
空间嵌入随机网络（Spatially Embedded Random Network，SERN）模型定义如下。设 $(\mathcal{S}, d)$ 为度量空间，$(X_1, \ldots, X_n)$ 为表示 $n$ 个节点在 $\mathcal{S}$ 中位置的随机向量。设 $\gamma : \mathbb{R}^{+} \to [0, 1]$ 为连通函数（connectivity function）。则对每个节点对 $(i, j)$，我们以概率 $\gamma\left(d(X_i, X_j)\right)$ 在 $i$ 与 $j$ 之间抽取一条无向边，其中 $d(X_i, X_j)$ 表示节点 $i$ 与 $j$ 之间的距离。
在随机几何图（Random Geometric Graph，RGG）模型中，假设 $X_1, \ldots, X_n$ 独立同分布且在 $\mathcal{S}$ 上均匀分布，而 $\gamma(x) = \mathbf{1}(x \leq r)$。换句话说，两个节点相连当且仅当它们之间的距离小于某个阈值 $r$。
我们在图 2.8 中画出了一些 RGG 的例子。可以看到，当 $n$ 较大时，网络由若干稠密连接的部分组成，各部分之间是空白区域。此外，该图不是小世界（small-world）的，因为连接两个相距很远的节点需要经过很多条边。
Waxman 模型（Waxman model）是一个 SERN，其中 $X$ 在 $\mathcal{S}$ 上均匀分布，且 $\gamma(x) = \min\left(1, q e^{-\alpha x}\right)$，$q, \alpha > 0$ 为参数。
图 2.9 展示了 Waxman 图的一些实现，我们观察到与 RGG 不同的行为。特别地，Waxman 图看起来像小世界网络。事实上，与随机几何图不同，相距很远的节点仍能以很小但非零的概率相连。
最后，阈值为 $r$ 的 RGG 可以表示为 Waxman 模型的极限：取 $\alpha \to \infty$ 且 $q = e^{\alpha r}$（见图 2.10）。
在定义 2.5 所定义的空间网络中，随机变量 $(A_{ij})_{i < j}$ 仍然两两独立，但一般不再相互独立。事实上，$i$ 与 $j$ 之间以及 $j$ 与 $k$ 之间边的存在会影响 $i$ 与 $k$ 之间边的概率。最简单的例子是随机几何图：已知 $A_{ij} = A_{jk} = 1$ 意味着 $d(X_i, X_j) \leq r$ 且 $d(X_j, X_k) \leq r$，于是三角不等式给出 $d(X_i, X_k) \leq 2r$；也就是说，节点 $k$ 不可能离节点 $i$ 任意远，这增加了 $i$ 与 $k$ 之间存在边的可能性。
2.2.4 小结（Summary）
我们在表 2.1 中总结了本章介绍的随机图模型所满足的基本性质。
2.3 具有社区结构的随机图：分块模型（Clustered Random Graphs: Block Models）
本节讨论具有社区结构的随机图（clustered random graph）模型。这指的是每个节点都带有社区（community）属性、且这些社区属性影响相互作用概率的情形。分块模型（block model）范式认为，节点被划入若干社区（称为块，block），$i$ 与 $j$ 之间连边的概率取决于 $i$ 和 $j$ 的社区标签（还可能取决于 $i$ 和 $j$ 的一些额外特征，如它们的空间位置）。
2.3.1 随机分块模型（Stochastic Block Model）
随机分块模型（Stochastic Block Model，SBM）是最简单、研究最多的具有社区结构的随机图。它是 Erdős–Rényi 模型的直接推广。
设 $n$ 为节点数，$K$ 为社区数，$\pi = (\pi_1, \ldots, \pi_K)$ 为概率向量，$P$ 为元素取值于 $[0, 1]$ 的 $K \times K$ 对称矩阵。若满足以下条件，则称二元组 $(z, G)$ 取自参数为 $(n, \pi, P)$ 的随机分块模型（Stochastic Block Model，SBM）：
- $z \in [K]^n$ 是各元素独立同分布的随机向量，满足 $\mathbb{P}(z_i = k) = \pi_k$；
- $G$ 是有 $n$ 个节点的无向图，节点 $i$ 与 $j$ 以概率 $P_{z_i z_j}$ 相连，且独立于其他节点对。
我们记 $(z, G) \sim \mathrm{SBM}(n, \pi, P)$。
图 2.11 给出了一些取自 SBM 的图的例子。
对 $z \in [K]^n$ 与 $k \in [K]$，记 $C_k^z = \{ i \in [n] : z_i = k \}$ 为节点标记 $z$ 给出的社区集合。设 $(z, G) \sim \mathrm{SBM}(n, \pi, P)$。则
$$ \mathbb{P}(z) = \prod_{k = 1}^{K} \pi_k^{|C_k^z|} , $$ $$ \mathbb{P}(G \mid z) = \prod_{1 \leq i < j \leq n} p_{z_i z_j}^{A_{ij}} (1 - p_{z_i z_j})^{1 - A_{ij}} \tag{2.4} $$ $$ = \prod_{1 \leq k \leq \ell \leq K} \left(p_{k\ell}\right)^{N_{k\ell}(1)} \left(1 - p_{k\ell}\right)^{N_{k\ell}(0)} \tag{2.5} $$其中 $N_{k\ell}(a) = \sum_{1 \leq i < j \leq n} \mathbf{1}(A_{ij} = a) \mathbf{1}(z_i = k) \mathbf{1}(z_j = \ell)$ 是社区 $k$ 与社区 $\ell$ 之间的边数（若 $a = 1$）或非边数（若 $a = 0$）。
在学习笔记中查看逐步完整证明与计数修正由节点社区标签的独立性，有
$$ \mathbb{P}(z) = \prod_{i = 1}^{n} \pi_{z_i} = \prod_{k = 1}^{K} \pi_k^{|C_k^z|} . $$而式 (2.4) 是命题 2.1 的推论。
$\mathrm{SBM}(n, \pi, P)$ 的邻接矩阵可以看作一个分块矩阵，其每个块都是一个 Erdős–Rényi 图。这一观察对于高效模拟稀疏 SBM 特别有用（见算法 2，或 networkX、iGraph 的实现）。
若一个 SBM 满足
$$ p_{z_i z_j} = \left\{ \begin{array}{ll} p_{\mathrm{in}} & \text{若 } z_i = z_j \\ p_{\mathrm{out}} & \text{其他} , \end{array} \right. $$设 $(z, G)$ 取自一个同质 SBM。则
$$ \begin{aligned} \mathbb{P}(G \mid z) &= \left(\frac{p_{\mathrm{in}}}{1 - p_{\mathrm{in}}}\right)^{|E|} \left(1 - p_{\mathrm{in}}\right)^{\frac{n(n-1)}{2}} \times \\ &\quad \times \left(\frac{1 - p_{\mathrm{out}}}{1 - p_{\mathrm{in}}}\right)^{\sum_{1 \leq k < \ell \leq n} |C_k^z| \cdot |C_\ell^z|} \left(\frac{p_{\mathrm{out}}}{1 - p_{\mathrm{out}}} \frac{1 - p_{\mathrm{in}}}{p_{\mathrm{in}}}\right)^{N_{\mathrm{out}}^z} \end{aligned} $$其中 $N_{\mathrm{out}}^z = \sum_{1 \leq i < j \leq n} \mathbf{1}(A_{ij} = 1) \mathbf{1}(z_i \neq z_j)$ 是社区间边的数目。
在学习笔记中查看逐步完整证明与恒等式校正由式 (2.5)，有
$$ \mathbb{P}(G \mid z) = \prod_{1 \leq k \leq \ell \leq K} \left(p_{k\ell}\right)^{N_{k\ell}(1)} \left(1 - p_{k\ell}\right)^{N_{k\ell}(0)} . $$我们注意到 $N_{k\ell}(0) + N_{k\ell}(1) = \sum_{i < j} \mathbf{1}(z_i = k) \mathbf{1}(z_j = \ell)$。因此，
$$ N_{k\ell}(0) + N_{k\ell}(1) = \left\{ \begin{array}{ll} |C_k^z| \cdot |C_\ell^z| & \text{若 } k \neq \ell , \\ \dfrac{|C_k^z| \cdot \left(|C_k^z| - 1\right)}{2} & \text{其他} , \end{array} \right. $$并且
$$ \begin{aligned} \mathbb{P}(G \mid z) &= (1 - p_{\mathrm{in}})^{\sum_{k = 1}^{K} \frac{|C_k^z| \cdot (|C_k^z| - 1)}{2}} (1 - p_{\mathrm{out}})^{\sum_{1 \leq k < \ell \leq K} |C_k^z| \cdot |C_\ell^z|} \times \\ &\quad \times \left(\frac{p_{\mathrm{in}}}{1 - p_{\mathrm{in}}}\right)^{\sum_{k = 1}^{K} N_{kk}(1)} \left(\frac{p_{\mathrm{out}}}{1 - p_{\mathrm{out}}}\right)^{\sum_{1 \leq k < \ell \leq K} N_{k\ell}(1)} . \end{aligned} $$由于 $\sum_{k = 1}^{K} |C_k^z| = n$，则 $\left(\sum_{k = 1}^{K} |C_k^z|\right)^2 = n^2 - 2 \sum_{1 \leq k < \ell \leq n} |C_k^z| \cdot |C_\ell^z|$，并且
$$ \begin{aligned} \mathbb{P}(G \mid z) &= (1 - p_{\mathrm{in}})^{\frac{n(n-1)}{2}} \left(\frac{1 - p_{\mathrm{out}}}{1 - p_{\mathrm{in}}}\right)^{\sum_{1 \leq k < \ell \leq n} |C_k^z| \cdot |C_\ell^z|} \times \\ &\quad \times \left(\frac{p_{\mathrm{in}}}{1 - p_{\mathrm{in}}}\right)^{\sum_{k = 1}^{K} N_{kk}(1)} \left(\frac{p_{\mathrm{out}}}{1 - p_{\mathrm{out}}}\right)^{\sum_{1 \leq k < \ell \leq K} N_{k\ell}(1)} . \end{aligned} $$最后，由于 $N_{\mathrm{out}}^z = \sum_{1 \leq k < \ell \leq K} N_{k\ell}(1)$ 且 $|E| = \sum_{1 \leq k \leq \ell \leq K} N_{k\ell}(1)$，我们有 $\sum_{k = 1}^{K} N_{kk}(1) = |E| - N_{\mathrm{out}}^z$，命题陈述成立。
设 $(z, G) \sim \mathrm{SBM}(n, \pi, P)$ 为节点标签均匀的同质 SBM 图，即 $\pi = \left(\frac{1}{K}, \ldots, \frac{1}{K}\right)$。则任一节点的期望度 $\bar{d}$ 为
$$ \bar{d} = \left(\frac{n}{K} - 1\right) p_{\mathrm{in}} + n \frac{K - 1}{K} p_{\mathrm{out}} . $$ 在学习笔记中查看逐步完整证明与两种口径证明与命题 2.2 的证明类似。给定节点在其社区内有 $\frac{n}{K} - 1$ 个潜在邻居，在其他社区中有 $\frac{n}{K}(K - 1)$ 个潜在邻居。
2.3.2 度校正随机分块模型（Degree-corrected Stochastic Block Model）
对 Erdős–Rényi 模型建立的结果（巨分量、连通性等）对随机分块模型同样成立。此外，对 Erdős–Rényi 图提到的局限性也同样适用于 SBM，特别是度分布上的局限。为了在度分布中引入更多异质性，Karrer 和 Newman（2011）提出了度校正 SBM（degree-corrected SBM，DC-SBM）。在该模型中，每个节点 $i$ 除了社区标签 $z_i$ 外，还有一个刻画其受欢迎程度（popularity，即节点 $i$ 连边的倾向）的度参数 $\theta_i$。正式定义如下。
设 $n$ 为节点数，$K$ 为社区数，$\pi = (\pi_1, \ldots, \pi_K)$ 为概率向量，$P$ 为 $K \times K$ 对称矩阵。此外，设 $\theta = (\theta_1, \ldots, \theta_n) \in \mathbb{R}_{+}^{n}$ 为度校正参数向量。若满足以下条件，则称二元组 $(z, G)$ 取自参数为 $(n, \pi, P, \theta)$ 的度校正随机分块模型（Degree-corrected Stochastic Block Model，DC-SBM）：
- $z = (z_1, \dots, z_n) \in [K]^n$ 是各元素独立、且按 $\pi$ 分布的随机向量；
- 给定 $z$ 时，$G$ 是有 $n$ 个节点的无向图，节点 $i$ 与 $j$ 以概率 $\min(\theta_i \theta_j P_{z_i z_j};\ 1)$ 相连，且独立于其他节点对。
后文中，我们将始终假设对所有 $(i, j)$ 都有 $\theta_i \theta_j P_{z_i z_j} < 1$。由定义 2.8 可见：把所有满足 $z_i = k$ 的 $\theta_i$ 乘以一个常数 $c$，并相应地把 $P_{k\ell}$（$k \neq \ell$）除以 $c$、把 $P_{kk}$ 除以 $c^2$，得到的是同一个模型。因此，在采样得到社区标记 $z$ 之后，我们对 $\theta_i$ 做归一化，使得 $\sum_i \theta_i \mathbf{1}(z_i = k) = n \pi_k$，其中 $n \pi_k$ 是块 $k$ 中节点的期望数目。在这一归一化选择下，若对所有 $i$ 都有 $\theta_i = 1$，就回到了 SBM 模型。此外，参数 $\theta_i$ 可以解释为节点 $i$ 在图中的相对重要性。另一种广泛使用的归一化是令 $\sum_i \theta_i \mathbf{1}(z_i = k) = 1$。
与 SBM 类似，当矩阵 $P$ 的元素只取两个值——$P_{kk} = p_{\mathrm{in}}$，且 $k \neq \ell$ 时 $P_{k\ell} = p_{\mathrm{out}}$——时，我们定义同质 DC-SBM。
考虑取自同质 DC-SBM $(n, \pi, P, \theta)$ 的二元组 $(z, G)$。设 $i \in [n]$ 为社区 $k$ 中的一个节点。$i$ 的期望度为
$$ \mathbb{E} d_i = \theta_i \, n \sum_{\ell = 1}^{K} \pi_{\ell} P_{k\ell} . $$ 在学习笔记中查看逐步完整证明与无自环修正设 $A$ 为 $G$ 的邻接矩阵。我们有 $d_i = \sum_{j = 1}^{n} A_{ij}$，其中 $A_{ij}$（$j = 1 \cdots n$）是服从 $\mathrm{Ber}\left(\theta_i \theta_j P_{z_i z_j}\right)$ 的独立随机变量。因此，对 $z$ 取条件，得到
$$ \mathbb{E}\left(d_i \mid z\right) = \sum_{j = 1}^{n} \sum_{j = 1}^{n} \theta_i \theta_j P_{z_i z_j} = \theta_i \sum_{\ell = 1}^{K} \left(\sum_{j = 1}^{n} \mathbf{1}(z_j = \ell) \, \theta_j\right) P_{k\ell} . $$利用归一化 $\mathbb{E} \sum_{j = 1}^{n} \mathbf{1}(z_j = \ell) \, \theta_j = n \pi_{\ell}$ 即得结论。
为了让某些计算更容易，有时定义 Poisson 度校正分块模型（Poisson Degree-Corrected Block Model）会更方便。这指的是边服从 Poisson 分布的随机图 $G$。更精确地说，$A_{ii} = 0$，且对 $i \neq j$ 有
$$ A_{ij} = A_{ji} \sim \mathrm{Poi}(\theta_i \theta_j \omega_{z_i z_j}) , \tag{2.6} $$
其中 $\mathrm{Poi}(\lambda)$ 表示参数为 $\lambda$ 的 Poisson 随机变量，其概率质量函数为
$$ \mathbb{P}(X = k) = e^{-\lambda} \frac{\lambda^k}{k!} , \quad k = 0, 1, 2, \ldots . $$
$\theta_i$ 是度校正参数，$\omega_{k\ell}$ 是块 $k$ 与块 $\ell$ 之间的边密度。注意此时 $A_{ij}$ 是取整数值的随机变量。与 DC-SBM 类似，我们假设对所有 $k \in [K]$ 有 $\sum_i \theta_i \mathbf{1}(z_i = k) = n_k$。当所有 $\theta_i$ 都等于 1 时，便回到了 SBM 的 Poisson 版本，即
$$ A_{ij} = A_{ji} \sim \mathrm{Poi}\left(\omega_{z_i z_j}\right) . \tag{2.7} $$
尽管这些随机图模型因允许取整数值的边而不同于标准 SBM 与度校正 SBM，我们注意到，当 $n \omega_{k\ell} \ll 1$ 时，Poisson 分布与具有同样参数 $\theta_i \theta_j \frac{\omega_{k\ell}}{n}$ 的伯努利分布很接近，因此在实际中两个模型是相似的。Poisson 框架的优点在于它使一些计算更容易。特别地，对 Poisson 版本有
$$ \begin{aligned} \mathbb{P}\left(A \mid z, \theta, \omega\right) &= \prod_{i < j} \frac{\left(\theta_i \theta_j \omega_{z_i z_j}\right)^{A_{ij}}}{A_{ij} !} \, e^{-\theta_i \theta_j \omega_{z_i z_j}} \\ &= \frac{\prod_i \theta_i^{d_i}}{\prod_{i < j} A_{ij} !} \prod_{1 \leq k \leq K} \omega_{kk}^{m_{kk}} e^{-\frac{n_k^2}{2} \omega_{kk}} \prod_{1 \leq k < \ell \leq K} \omega_{k\ell}^{m_{k\ell}} e^{-n_k n_{\ell} \omega_{k\ell}} \end{aligned} \tag{2.8} $$
其中 $n_k = \sum_i \mathbf{1}(z_i = k)$ 为块 $k$ 中的节点数，$m_{k\ell} = \sum_{i, j} A_{ij} \mathbf{1}(z_i = k) \mathbf{1}(z_j = \ell)$ 表示从社区 $k$ 连向社区 $\ell$ 的边数（若 $k = \ell$ 则为该数的两倍）。
2.3.3 受欢迎度调整分块模型（Popularity Adjusted Block Model）
虽然 DC-SBM 能通过强制设定节点度参数来精确拟合度分布，但它迫使一个受欢迎的节点在所有社区中都受欢迎。事实上，若 $\theta_i$ 很大，节点 $i$ 就会被期望在每个社区中都有很多朋友。受欢迎度调整分块模型（Popularity Adjusted Block Model，PABM）绕开了这一限制，允许节点的受欢迎程度同时随节点与社区而变化。
设 $n$ 为节点数，$K$ 为社区数，$z \in [K]^n$ 为节点标记向量。令 $\Lambda = (\lambda_{ik})_{i \in [n], k \in [K]} \in [0, 1]^{n \times K}$。若 $V = [n]$、边独立生成，且
$$ \mathbb{P}\left( (i, j) \in E \right) := \lambda_{i z_j} \lambda_{j z_i} , $$则称图 $G = (V, E)$ 取自受欢迎度调整分块模型。换句话说，$\lambda_{ik}$ 是节点 $i$ 与社区 $k$ 中节点连边的倾向。
对每个 $i \in [n]$ 与每个 $k \in [K]$ 令 $\lambda_{ik} = \sqrt{P_{z_i k}}$，便回到了 SBM。
对每个 $i \in [n]$ 与每个 $k \in [K]$ 令 $\lambda_{ik} = \theta_i \sqrt{P_{z_i k}}$，便回到了 DC-SBM。
2.3.4 软几何分块模型（Soft Geometric Block Model）
正如 SBM 推广了 Erdős–Rényi 模型，软几何分块模型（Soft Geometric Block Model，SGBM）推广了软几何随机图（即 SERN）。
设 $(\mathcal{S}, d)$ 为度量空间，$(\gamma_{k\ell})_{1 \leq k, \ell \leq K} : \mathbb{R}_{+} \to [0, 1]$ 为一组连通函数，满足 $\gamma_{k\ell} = \gamma_{\ell k}$。我们为每个节点指定一个位置 $X_i \in \mathcal{S}$ 和一个社区标记 $\sigma_i \in [K]$。则
$$ \mathbb{P}\left( A \mid X, \sigma \right) = \prod_{i < j} \gamma_{\sigma_i \sigma_j}\left(d\left(X_i, X_j\right)\right)^{A_{ij}} \left(1 - \gamma_{\sigma_i \sigma_j}\left(d\left(X_i, X_j\right)\right)\right)^{1 - A_{ij}} . $$该模型假设两个节点 $i, j$ 之间的连边概率同时取决于它们的位置与社区归属。
进一步限制 $\gamma_{k\ell}(x) = q_{k\ell}$ 为常数（对所有 $k, \ell$），便回到了 SBM。
几何分块模型（Geometric Block Model，GBM）限制 $\gamma_{k\ell}(x) = \mathbf{1}(x \leq r_{k\ell})$，其中 $r_{k\ell} \geq 0$ 为参数。
最后，若
$$ \gamma_{k\ell} = \left\{ \begin{array}{ll} \gamma_{\mathrm{in}} & \text{若 } k = \ell , \\ \gamma_{\mathrm{out}} & \text{其他} , \end{array} \right. $$
则称该模型是同质的。
2.4 指数随机图模型（Exponential Random Graph Model）
2.4.1 定义与首批例子（Definition and First Examples）
指数随机图模型（Exponential Random Graph Model，ERGM）为解释各种网络中观察到的不同网络统计量提供了一个方便的框架。网络统计量的例子包括：度的异质性、关系的传递性（朋友的朋友倾向于成为朋友）、同质性（homophily，即与具有相同属性的节点连边的倾向）、（有向网络中）连边的互惠性（reciprocity），等等。
设 $n$ 为节点数，$\theta = (\theta_1, \ldots, \theta_q) \in \mathbb{R}^{q}$ 为参数向量，$g = (g_1, \dotsc, g_q)$ 为网络统计量向量。ERGM 的邻接矩阵具有以下概率分布
$$ \mathbb{P}\left(A \mid \theta\right) = \frac{\exp\left(\theta^{T} g(A)\right)}{\kappa(\theta)} , $$其中 $\kappa(\theta)$ 为归一化常数。
考虑伯努利随机图模型，其中 $A_{ij}$ 相互独立，$A_{ij} = A_{ji} \sim \mathrm{Ber}(p_{ij})$。则
$$ \mathbb{P}(A) = \prod_{i < j} p_{ij}^{A_{ij}} (1 - p_{ij})^{1 - A_{ij}} = \frac{\exp\left(\sum_{i < j} \theta_{ij} A_{ij}\right)}{\kappa(\theta)} = \frac{\exp\left(\theta^{T} g(A)\right)}{\kappa(\theta)} , $$其中 $\theta_{i, j} = \log \frac{p_{ij}}{1 - p_{ij}}$，$\kappa(\theta) = \left(\prod_{i < j} (1 - p_{ij})\right)^{-1}$，$\theta = (\theta_{ij})_{1 \leq i < j \leq N}$，且 $g(A) = A_{ij}$（共有 $q = \binom{N}{2} = \frac{N(N-1)}{2}$ 个网络统计量）。
在这个例子中我们注意到 $\theta_{ij} = \log \frac{\mathbb{P}\left(A_{ij} = 1\right)}{\mathbb{P}\left(A_{ij} = 0\right)} = \operatorname{logit} \mathbb{P}\left(A_{ij} = 1\right)$，其中 $\operatorname{logit}(x) = \log \frac{x}{1 - x}$。这类与对数几率（log-odds / logit）的关系在后面的例子中还会多次出现。
由于 Erdős–Rényi 图、SBM 和 DC-SBM 都是伯努利随机图的特例，它们也都可以表示为 ERGM。例如，对 Erdős–Rényi 随机图 $\mathcal{G}_{n, p}$，$\theta_{ij} = \operatorname{logit}(p)$ 与 $i$ 和 $j$ 无关，于是上例化为
$$ \mathbb{P}\left(A\right) = \frac{\exp\left(\theta g(A)\right)}{\kappa(\theta)} , $$
其中 $\theta = \log \frac{p}{1 - p}$，$g(A) = \sum_{i < j} A_{ij} = |E|$ 为边数，且 $\kappa(\theta) = (1 - p)^{-\frac{n(n-1)}{2}}$。
2.4.2 p₁ 模型（The p₁ Model）
现在考虑有向图 $A$，并令 $X_{ij} = (A_{ij}, A_{ji})$。假设 $(X_{ij})_{i < j}$ 相互独立，并定义
$$ \begin{aligned} \mathbb{P}\left(X_{ij} = (1, 1)\right) &= r_{ij} , \\ \mathbb{P}\left(X_{ij} = (1, 0)\right) &= s_{ij} , \\ \mathbb{P}\left(X_{ij} = (0, 0)\right) &= t_{ij} . \end{aligned} $$
注意 $r_{ij} = r_{ji}$、$t_{ij} = t_{ji}$，且 $r_{ij} + s_{ij} + s_{ji} + t_{ij} = 1$。此外，
$$ \mathbb{P}(A) = \prod_{i < j} r_{ij}^{A_{ij} A_{ji}} \prod_{i \ne j} s_{ij}^{A_{ij} (1 - A_{ji})} \prod_{i < j} t_{ij}^{(1 - A_{ij}) (1 - A_{ji})} . $$
这可以重新表示为指数形式：
$$ \mathbb{P}\left(A\right) = \exp\left(\sum_{i < j} \rho_{ij} A_{ij} A_{ji} + \sum_{i \neq j} \mu_{ij} A_{ij}\right) \prod_{i < j} t_{ij} , $$
其中 $\rho_{ij} = \log\left(\frac{r_{ij} t_{ij}}{s_{ij} s_{ji}}\right)$，$\mu_{ij} = \log\left(\frac{s_{ij}}{t_{ij}}\right)$。我们注意到
$$ \mu_{ij} = \log\left(\frac{\mathbb{P}\left(A_{ij} = 1 \mid A_{ji} = 0\right)}{\mathbb{P}\left(A_{ij} = 0 \mid A_{ji} = 0\right)}\right) = \operatorname{logit}\left(\mathbb{P}\left(A_{ij} = 1 \mid A_{ji} = 0\right)\right) $$
刻画了 $i$ 与 $j$ 之间非对称连边的概率。类似地，
$$ \begin{aligned} \rho_{ij} &= \log\left(\frac{\mathbb{P}\left(A_{ij} = 1 \mid A_{ji} = 1\right)}{\mathbb{P}\left(A_{ij} = 0 \mid A_{ji} = 1\right)}\right) - \log\left(\frac{\mathbb{P}\left(A_{ij} = 1 \mid A_{ji} = 0\right)}{\mathbb{P}\left(A_{ij} = 0 \mid A_{ji} = 0\right)}\right) \\ &= \operatorname{logit}\left(\mathbb{P}\left(A_{ij} = 1 \mid A_{ji} = 1\right)\right) - \mu_{ij} \end{aligned} $$
与给定 $A_{ji} = 1$ 时 $A_{ij} = 1$ 的概率相关，即 $i$ 与 $j$ 之间的互惠力（force of reciprocation）。
Holland 和 Leinhardt（1981）的 p₁ 模型（p₁ model）进一步限制 $\rho_{ij} = \rho$ 与 $\mu_{ij} = \mu + \alpha_i + \beta_j$，从而
$$ \mathbb{P}\left(A\right) = \frac{\exp\Big(\rho R + \mu M + \sum_{i} \alpha_i A_{i+} + \sum_{j} \beta_j A_{+j}\Big)}{\kappa(\rho, \mu, \alpha, \beta)} , \tag{2.9} $$
其中 $A_{+i} = \sum_{j} A_{ji}$ 表示节点 $i$ 的入度（in-degree），$A_{i+} = \sum_{j} A_{ij}$ 表示节点 $i$ 的出度（out-degree），$M = \sum_{i, j} A_{ij}$ 为边数，$R = \sum_{i, j} A_{ij} A_{ji}$ 为互惠边（reciprocated edge）的数目。我们可以如下解释式 (2.9)：
- 参数 $\mu$ 控制（有向）边的密度。特别地，若 $\rho = \alpha_i = \beta_j = 0$ 而 $\mu \neq 0$，则回到有向 Erdős–Rényi 随机图，其连边概率 $p$ 满足 $\mu = \operatorname{logit} p$；
- 若 $\alpha_i$ 很大，节点 $i$ 将倾向于形成出边。因此可以把 $\alpha_i$ 称为节点 $i$ 的产出力（productivity）；
- $\beta_i$ 表示节点 $i$ 的吸引力（attractiveness），因为很大的 $\beta_i$ 会促使许多节点形成指向 $i$ 的入边；
- 最后，参数 $\rho$ 是连边的互惠力。
2.4.3 θ 与对数几率的关系（Relationship Between θ and the log-odds）
我们在例 2.12 中注意到 $\theta_{ij} = \operatorname{logit} \mathbb{P}\left(A_{ij} = 1\right)$，p₁ 模型中也出现了类似的关系。下面的命题把它推广到任意 ERGM。
考虑定义 2.11 中的 ERGM。记 $A_{ij}^{+} = \{A \text{ 且 } A_{ij} = 1\}$ 为把边 $(i, j)$ 置为 1 的图，$A_{ij}^{-} = \{A \text{ 且 } A_{ij} = 0\}$ 为把边 $(i, j)$ 置为 0 的图，$A_{ij}^{c} = \{A_{uv} : (u, v) \neq (i, j)\}$ 为除 $A_{ij}$ 外所有边与非边的集合。则有
$$ \operatorname{logit} \mathbb{P}\left(A_{ij} = 1 \mid A_{ij}^{c}\right) = \theta^{T} \left( g(A_{ij}^{+}) - g(A_{ij}^{-}) \right) . $$ 在学习笔记中查看逐步完整证明注意
$$ \mathbb{P}\left(A_{ij} = 1 \mid A_{ij}^{c}\right) = \frac{\mathbb{P}\left(A_{ij}^{+}\right)}{\mathbb{P}\left(A_{ij}^{+}\right) + \mathbb{P}\left(A_{ij}^{-}\right)} = \frac{\exp\big(\theta^{T} g(A_{ij}^{+})\big)}{\exp\big(\theta^{T} g(A_{ij}^{+})\big) + \exp\big(\theta^{T} g(A_{ij}^{-})\big)} . $$类似地，
$$ \mathbb{P}\left(A_{ij} = 0 \mid A_{ij}^{c}\right) = \frac{\exp\big(\theta^{T} g(A_{ij}^{-})\big)}{\exp\big(\theta^{T} g(A_{ij}^{+})\big) + \exp\big(\theta^{T} g(A_{ij}^{-})\big)} , $$因此
$$ \operatorname{logit} \mathbb{P}\left(A_{ij} = 1 \mid A_{ij}^{c}\right) = \theta^{T} \left[ g(A_{ij}^{+}) - g(A_{ij}^{-}) \right] . $$进一步阅读（Further Notes）
本章很好的一份补充读物是 Barabási（2016）（在线互动版本见 http://networksciencebook.com/），以及（按相关度排序）：Hofstad（2016）；Durrett（2007）；Chung 和 Lu（2006）。最后，其他关于随机图的经典著作（更侧重于数学证明）有 Janson et al.（2011）和 Bollobás（2001）。
随机图模型有很多。一个值得提及但本章未覆盖的模型是小世界模型（Watts and Strogatz, 1998）。关于 SBM 的完整综述见 Abbe（2018）。关于随机几何图，我们推荐读者参考 Penrose（2003）。
一类有用的、具有标度自由度分布的随机几何图变体是双曲几何图模型（hyperbolic geometric graph model，例如见 Krioukov et al., 2010）。