数学推导与算法

环形规则网格的聚集系数

每个节点与左右各 $K/2$ 个最近邻相连。节点 $i$ 的两个邻居相距（沿环）不超过 $K/2$ 步时彼此相连。分别计数同侧与异侧的邻居对，可得邻居之间的边数 $e_i=\tfrac{3K(K-2)}{8}$，而邻居对总数为 $K(K-1)/2$，于是 $$C=\frac{2e_i}{K(K-1)}=\frac{3(K-2)}{4(K-1)} .$$ 例如 $K=4$ 时 $C=1/2$，$K=10$ 时 $C=2/3\approx0.67$。

BA 模型的平均场推导

把 $k_i$ 看作时间 $t$ 的连续函数。每步新增 $m$ 条边，总度数 $\sum_j k_j \approx 2mt$，于是

$$\frac{dk_i}{dt} = m \cdot \frac{k_i}{2mt} = \frac{k_i}{2t}.$$

以节点 $i$ 加入时刻 $t_i$ 的初值 $k_i(t_i)=m$ 积分得

$$k_i(t) = m\left(\frac{t}{t_i}\right)^{1/2}.$$

所有节点的度都按 $\sqrt{t}$ 增长，越早加入的节点度越大。度小于 $k$ 的节点，就是加入时刻满足 $t_i > m^2 t / k^2$ 的那些节点。由于节点按时间均匀加入，

$$P(k_i < k) = 1 - \frac{m^2}{k^2}, \qquad P(k) = \frac{d}{dk}P(k_i<k) = \frac{2m^2}{k^3}.$$

因此 BA 模型产生 $\gamma = 3$ 的幂律分布，而且指数与 $m$ 无关；$m$ 只决定平均度 $\langle k\rangle = 2m$ 和最小度。

一般化的“平均场配方”：若某个模型给出 $k_i(t)+s=(m+s)(t/t_i)^{\beta}$（$s$ 为常数平移），同样的论证给出 $p_k\propto(k+s)^{-(1+1/\beta)}$，即 $$\gamma=1+\frac{1}{\beta}.$$ 下面几个扩展模型都只需求出各自的 $\beta$。

速率方程与精确度分布

设 $N_k(t)$ 为 $t$ 时刻度为 $k$ 的节点数。每步新节点的 $m$ 条边中，落到某个度为 $k$ 的节点上的期望数为 $m\cdot k/(2mt)=k/(2t)$，于是 $$N_k(t+1)=N_k(t)+\frac{(k-1)N_{k-1}(t)-kN_k(t)}{2t}+\delta_{k,m}.$$ 在长时间极限下 $N_k(t)=t\,p_k$，代入得 $p_k=\dfrac{(k-1)p_{k-1}-kp_k}{2}+\delta_{k,m}$。对 $k=m$：$p_m=\dfrac{2}{m+2}$；对 $k>m$： $$p_k=\frac{k-1}{k+2}\,p_{k-1}\quad\Rightarrow\quad p_k=\frac{2m(m+1)}{k(k+1)(k+2)} .$$ （逐项连乘：$\prod_{j=m+1}^{k}\frac{j-1}{j+2}=\frac{m(m+1)(m+2)}{k(k+1)(k+2)}$。）大 $k$ 时 $p_k\approx2m^2/k^3$，与平均场一致。

无增长模型 A：指数分布

均匀连接时 $\Pi=1/t$，$dk_i/dt=m/t$，积分得 $k_i=m+m\ln(t/t_i)$。度小于 $k$ 等价于 $t_i>t\,e^{-(k-m)/m}$，所以 $P(k_i<k)=1-e^{-(k-m)/m}$，求导得 $p_k=\dfrac{1}{m}e^{-(k-m)/m}=\dfrac{e}{m}e^{-k/m}$。

初始吸引力、内部连边与复制模型的指数

• 初始吸引力 $\Pi\propto k+A$：$\sum_j(k_j+A)\approx(2m+A)t$，所以 $\dfrac{dk_i}{dt}=\dfrac{m(k_i+A)}{(2m+A)t}$，$k_i+A\propto t^{\beta}$，$\beta=\dfrac{m}{2m+A}$，$\gamma=1+\dfrac{2m+A}{m}=3+\dfrac{A}{m}$。
• 双优先内部边：每步总度数增加 $2(m+n)$，节点 $i$ 从新节点的 $m$ 条边中获得 $mk_i/[2(m+n)t]$，从 $n$ 条内部边（每条两个端点）中获得 $2nk_i/[2(m+n)t]$，故 $\beta=\dfrac{m+2n}{2(m+n)}$，$\gamma=1+\dfrac{2(m+n)}{m+2n}=2+\dfrac{m}{m+2n}$。
• 随机内部边：$\dfrac{dk_i}{dt}=\dfrac{mk_i}{2(m+n)t}+\dfrac{2n}{t}$，即 $k_i+s\propto t^{\beta}$，$\beta=\dfrac{m}{2(m+n)}$，$s=\dfrac{4n(m+n)}{m}$；$\gamma=1+\dfrac{2(m+n)}{m}=3+\dfrac{2n}{m}$。
• 复制模型（无向，每步一条边，$L\approx t$）：$\dfrac{dk_i}{dt}=\dfrac{p}{t}+\dfrac{(1-p)k_i}{2t}$，$\beta=\dfrac{1-p}{2}$，$\gamma=1+\dfrac{2}{1-p}=\dfrac{3-p}{1-p}$。

加速增长

设新节点带 $m(t)=m_0t^{\theta}$ 条边，总度数 $\sum_jk_j\approx2m_0t^{1+\theta}/(1+\theta)$。于是 $$\frac{dk_i}{dt}=m_0t^{\theta}\frac{k_i}{\sum_jk_j}=\frac{1+\theta}{2}\frac{k_i}{t},\qquad k_i(t)=m_0t_i^{\theta}\Big(\frac{t}{t_i}\Big)^{\frac{1+\theta}{2}}\propto t^{\frac{1+\theta}{2}}\,t_i^{-\frac{1-\theta}{2}} .$$ 在固定 $t$ 时 $k\propto t_i^{-(1-\theta)/2}$，由 $t_i$ 的均匀分布得 $p_k\propto k^{-1-2/(1-\theta)}$，即 $\gamma=\dfrac{3-\theta}{1-\theta}=3+\dfrac{2\theta}{1-\theta}$。

适应度模型的自洽方程

$\dfrac{dk_i}{dt}=m\dfrac{\eta_ik_i}{\sum_j\eta_jk_j}$。假设长时间后 $\sum_j\eta_jk_j\approx Cmt$（$C$ 为待定常数），则 $k_i=m(t/t_i)^{\eta_i/C}$。把这个解代回求和： $$\sum_j\eta_jk_j\approx\int\!d\eta\,\rho(\eta)\,\eta\int_1^t m\Big(\frac{t}{t_0}\Big)^{\eta/C}dt_0\approx mt\int\rho(\eta)\frac{\eta}{1-\eta/C}\,d\eta ,$$ （要求 $\eta/C<1$，此时 $t_0\to1$ 端的贡献为低阶项。）与 $Cmt$ 比较得 $$1=\int\rho(\eta)\frac{\eta}{C-\eta}\,d\eta .$$ 均匀分布 $\rho(\eta)=1$（$0\le\eta\le1$）时，积分为 $C\ln\dfrac{C}{C-1}-1$，方程化为 $C\ln\dfrac{C}{C-1}=2$，数值解 $C\approx1.255$。右端积分是 $C$ 的减函数，若在允许的最小值 $C\to\eta_{\max}=1$ 处它仍小于 1，方程无解，即为凝聚相。例如 $\rho(\eta)=(\lambda+1)(1-\eta)^{\lambda}$ 时，$\int\rho\,\eta/(1-\eta)\,d\eta=(\lambda+1)B(2,\lambda)=1/\lambda$，于是 $\lambda>1$ 时凝聚。

复制–分化的均场

每步复制一个随机节点，新拷贝以概率 $q$ 保留每条继承边。

• 已有节点 $j$ 的度：每步被复制的节点是 $j$ 的某个邻居的概率为 $k_j/N$，且连向 $j$ 的边以概率 $q$ 被保留，所以 $dk_j/dN=qk_j/N$，$k_j\propto(N/N_j)^{q}$——线性优先连接。
• 总边数：$dE/dN=q\langle k\rangle=2qE/N$，$E\propto N^{2q}$，$\langle k\rangle\propto N^{2q-1}$。$q=1/2$ 是平均度增长与衰减的分界。

这个均场忽略了新节点自身度的涨落与孤立节点的处理，只给出定性结论；精确分析见 Ispolatov 等（2005）。

配置模型：余度分布与 Molloy–Reed 判据

沿一条随机边到达一个节点，它的度为 $k$ 的概率正比于 $k p_k$（度为 $k$ 的节点有 $k$ 个半边），归一化后为 $kp_k/\langle k\rangle$。扣除来时那条边，余度 $k-1$ 的分布为 $q_{k-1}=kp_k/\langle k\rangle$，其均值 $$\langle k_{\text{excess}}\rangle=\sum_k(k-1)\frac{kp_k}{\langle k\rangle}=\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}.$$ 在局部树状的稀疏网络中，从一个节点出发的分支过程每代平均繁衍 $\langle k_{\text{excess}}\rangle$ 个后代。分支过程不灭绝（出现巨连通分支）的条件是 $\langle k_{\text{excess}}\rangle>1$，即 $\langle k^2\rangle-2\langle k\rangle>0$。用同样的分支过程论证，第 $h$ 层邻居数约为 $z_1(z_2/z_1)^{h-1}$，令其等于 $N$ 即得平均距离近似式 $\ell\approx1+\ln(N/z_1)/\ln(z_2/z_1)$。

幂律矩的发散

对 $P(k)=(\gamma-1)k_{\min}^{\gamma-1}k^{-\gamma}$（$k\ge k_{\min}$）， $$\langle k^n\rangle=(\gamma-1)k_{\min}^{\gamma-1}\int_{k_{\min}}^{k_{\max}}k^{n-\gamma}\,dk \propto \frac{k_{\max}^{\,n-\gamma+1}-k_{\min}^{\,n-\gamma+1}}{n-\gamma+1}.$$ 当 $n-\gamma+1>0$ 即 $n>\gamma-1$ 时，$k_{\max}\to\infty$ 使其发散。$2<\gamma<3$ 时，$n=1$ 收敛而 $n=2$ 发散，$\langle k^2\rangle\sim k_{\max}^{3-\gamma}$。

自然截断

最大度 $k_{\max}$ 可估计为“在 $N$ 个节点中，度不小于 $k_{\max}$ 的节点期望只有一个”： $$N\int_{k_{\max}}^{\infty}P(k)\,dk = N\left(\frac{k_{\max}}{k_{\min}}\right)^{-(\gamma-1)} \approx 1 \quad\Rightarrow\quad k_{\max}\approx k_{\min}N^{1/(\gamma-1)} .$$ $\gamma<2$ 时指数 $1/(\gamma-1)>1$，$k_{\max}$ 比 $N$ 增长得快，而简单图中任何节点的度都不超过 $N-1$——这就是反常区在简单图中难以维持的原因。

隐变量模型的度指数

Goh 等的静态模型取 $\eta_i\propto i^{-\alpha}$（$i=1,\dots,N$，$0<\alpha<1$）。权重大于 $\eta$ 的节点是满足 $i<\eta^{-1/\alpha}$ 的那些，所以 $\eta$ 的 CCDF $\propto\eta^{-1/\alpha}$，密度 $\rho(\eta)\propto\eta^{-1-1/\alpha}$。期望度等于 $\eta$，度分布尾部继承同样的指数：$\gamma=1+1/\alpha$，$\alpha$ 从 0 到 1 时 $\gamma$ 从 $\infty$ 降到 2。

幂律指数的最大似然估计

连续幂律 $p(k)=\frac{\gamma-1}{k_{\min}}\left(\frac{k}{k_{\min}}\right)^{-\gamma}$ 下，$n$ 个观测（均 $\ge k_{\min}$）的对数似然为 $$\ell(\gamma)=n\ln(\gamma-1)-n\ln k_{\min}-\gamma\sum_{i=1}^{n}\ln\frac{k_i}{k_{\min}} .$$ 令 $\ell'(\gamma)=\frac{n}{\gamma-1}-\sum_i\ln\frac{k_i}{k_{\min}}=0$，得 $$\hat\gamma=1+n\left[\sum_{i=1}^{n}\ln\frac{k_i}{k_{\min}}\right]^{-1}.$$ 离散度数据常用 $k_{\min}-\tfrac12$ 代替 $k_{\min}$ 作近似修正。$k_{\min}$ 取大时偏差减小、可用样本变少、方差增大；Clauset 等（2009）选择使经验分布与拟合分布之间 KS 距离最小的 $k_{\min}$。估计量的标准误约为 $(\hat\gamma-1)/\sqrt n$。

注意：若真实分布是平移幂律 $p_k\propto(k+s)^{-\gamma}$（初始吸引力、随机内部边等模型都如此），直接对 $k$ 做纯幂律 MLE 会系统性低估 $\gamma$，$s$ 越大偏差越大（代码示例给出了数值对比）。

保度随机化：双边交换

算法 1  双边交换（degree-preserving rewiring）
输入：无向简单图 G，交换次数 T；输出：度序列不变的随机化图
1. repeat T 次:
2.     随机选两条边 (a, b)、(c, d)
3.     若 a、b、c、d 互不相同，且 (a, d)、(c, b) 都不存在:
4.         删除 (a, b)、(c, d)，加入 (a, d)、(c, b)
5. return G

每次交换使四个端点的度都保持不变。交换次数通常取边数的若干倍（例如 $10M$），使网络充分“洗牌”；随机化后再计算 $C_{\text{rand}}$、$L_{\text{rand}}$。

生成算法与复杂度

算法 2  BA 模型的线性时间生成（“边端点列表”法）
输入：节点数 N，每步边数 m；输出：BA 网络
1. 用 m+1 个节点的完全图初始化；把每条边的两个端点都追加到列表 R
2. for t = m+1, ..., N-1:
3.     从 R 中均匀抽取 m 个互不相同的节点作为目标      # 均匀抽 R 的元素 = 按度成比例抽节点
4.     加入边 (t, 目标)，并把 t 与各目标追加到 R
5. return G

列表 $R$ 中节点 $i$ 恰好出现 $k_i$ 次，因此均匀抽一个元素就实现了 $\Pi\propto k_i$，每步代价 $O(m)$，总代价 $O(Nm)$；若每步都按 $k_i/\sum k_j$ 重新计算概率，代价会变成 $O(N^2)$。初始吸引力可以用“以一定概率改为均匀抽节点”的混合抽样实现；适应度模型与非线性优先连接则需要按权重抽样（可用树状累积和结构做到每步 $O(\log N)$）。配置模型的随机配对可以先把半边列表随机打乱再两两相邻配对，代价 $O(L)$。