任意度分布网络的生成：配置模型与隐变量模型

很多时候我们并不关心度分布“从哪里来”，只想问：如果网络除了度分布之外完全随机，会是什么样子？这需要能按指定度分布或度序列生成网络的“静态”模型。它们既是研究度异质性效应的理论工具，也是检验真实网络其他结构（聚类、社团、度相关、基序）是否“超出度序列所能解释”的零模型。

配置模型

一个可手算的小例子：度序列 $(2,1,1)$ 有 4 个半边 $a_1,a_2$（节点 1）、$b$（节点 2）、$c$（节点 3）。4 个半边共有 3 种配对方式：$\{a_1a_2, bc\}$ 产生节点 1 的自环加边 2–3；$\{a_1b, a_2c\}$ 与 $\{a_1c, a_2b\}$ 都产生路径 2–1–3。所以按配置模型抽样，有 1/3 的概率得到“带自环”的图——小网络、度大的节点特别容易出现自环与重边。

配置模型的主要性质（稀疏、$N$ 大）：

• 连边概率：节点 $i$、$j$ 之间的期望边数为 $\dfrac{k_ik_j}{2L-1}\approx\dfrac{k_ik_j}{2L}$。这正是模块度定义中的期望项（见社团结构与社区发现）。
• 余度与朋友悖论：沿一条随机边到达的节点，其度为 $k$ 的概率正比于 $kp_k$；去掉来时那条边后的“余度”（excess degree）分布为 $q_k=\dfrac{(k+1)p_{k+1}}{\langle k\rangle}$。随机邻居的平均度是 $\langle k^2\rangle/\langle k\rangle$，总不小于 $\langle k\rangle$——“你的朋友平均比你朋友多”。在 $2<\gamma<3$ 的网络中这个比值随规模发散。
• 巨连通分支：Molloy 与 Reed（1995）证明，当 $$\langle k^2\rangle-2\langle k\rangle>0 \quad\Longleftrightarrow\quad \frac{\langle k^2\rangle}{\langle k\rangle}>2$$ 时出现巨连通分支（ER 网络中即 $\langle k\rangle>1$）。直观上：顺着一条边走到的节点，平均还能再引出 $\langle k^2\rangle/\langle k\rangle-1$ 条新边，大于 1 就能“繁衍”下去。$\langle k^2\rangle$ 发散的无标度网络几乎总满足这个条件，这也是它们对随机删点稳健的原因（见网络鲁棒性、渗流与级联失效）。
• 路径长度：第一层邻居平均 $z_1=\langle k\rangle$ 个，第二层约 $z_2=\langle k^2\rangle-\langle k\rangle$ 个，平均距离近似为 $\ell\approx 1+\dfrac{\ln(N/z_1)}{\ln(z_2/z_1)}$（Newman、Strogatz 与 Watts 2001）。
• 聚集系数：$C=\dfrac{(\langle k^2\rangle-\langle k\rangle)^2}{\langle k\rangle^3N}$，随 $N$ 趋于 0；但当 $\langle k^2\rangle$ 随 $N$ 发散时下降得很慢，度异质性本身就会“制造”一部分三角形。这就是为什么判断小世界性时要用保度随机化而不是 ER 网络作参照。

自环、重边与结构截断

配置模型生成的是多重图。度有限方差时，自环与重边的期望数是 $O(1)$，可以忽略或删除；但在 $\gamma<3$ 的重尾序列中，枢纽之间的期望边数 $k_ik_j/2L$ 可能大于 1，重边大量出现。删除它们会改变度序列，并人为制造“枢纽彼此回避”的负度相关。Boguñá、Pastor-Satorras 与 Vespignani（2004）指出，不想产生这种相关的简单图，最大度应不超过结构截断 $k_s\sim\sqrt{\langle k\rangle N}$；而 $2<\gamma<3$ 时自然截断 $N^{1/(\gamma-1)}$ 大于 $\sqrt N$，两者冲突。因此，在重尾网络中“只由度序列决定、没有度相关”的简单图在数学上本来就难以实现——实际网络中观察到的枢纽间连接偏少，一部分可能只是这种结构约束（见度相关性与网络结构的高阶统计）。

此外，并不是每个整数序列都能实现为简单图：判断一个度序列是否“可图”（graphical）可用 Erdős–Gallai 条件。

保度随机化

如果手头已经有一个真实网络，最常用的做法不是从头配对，而是反复做双边交换：随机选两条边 $(a,b)$、$(c,d)$，改连为 $(a,d)$、$(c,b)$，在不产生自环和重边时接受。每次交换都保持所有节点的度不变，交换足够多次后得到“与原网络度序列相同、其余随机”的简单图（算法见数学推导与算法，零模型选择的系统讨论见网络构建与统计验证）。

隐变量模型

配置模型固定每个节点的确切度。另一类静态模型只固定期望度：给每个节点一个隐变量（权重、适应度）$\eta_i$，节点对 $(i,j)$ 独立地以概率 $$p_{ij}=\min\!\left(1,\ \frac{\eta_i\eta_j}{N\langle\eta\rangle}\right)$$ 连边。这样节点 $i$ 的期望度就是 $\eta_i$，给定 $\eta_i$ 时实际度近似服从均值为 $\eta_i$ 的泊松分布。只要隐变量分布 $\rho(\eta)$ 有幂律尾 $\rho(\eta)\sim\eta^{-\gamma}$，度分布在大 $k$ 处就有同样的尾部 $p_k\sim k^{-\gamma}$。这一类模型有多个名字：Chung–Lu 模型（期望度模型）、Caldarelli 等（2002）的“内禀适应度”模型、Goh、Kahng 与 Kim（2001）的“静态模型”（取 $\eta_i\propto i^{-\alpha}$，得到 $\gamma=1+1/\alpha$）。

隐变量模型的优点是各边独立，期望值可以解析计算，也天然没有重边；缺点与配置模型相同——当 $\eta_i\eta_j/(N\langle\eta\rangle)>1$ 需要截断时，就会引入度相关。它的思想在网络推断中也很常见：“每个节点有一个潜在的活跃度或可结合性，连边概率由两端的潜变量决定”。