联合度分布与条件度分布

从“随机抽一个节点”到“随机抽一条边”

度相关的所有定义都以边为抽样单位。在无向网络中随机选一条边，再随机选它的一端，到达度为 $k$ 的节点的概率不是 $p_k$，而是

$$q_k=\frac{k\,p_k}{\langle k\rangle},$$

因为度为 $k$ 的节点有 $k$ 条边可以“被抽中”。$q_k$ 称为边端度分布。在 Newman 的原始定义中使用的是“剩余度”（excess degree，即除去来时那条边后剩下的边数 $k-1$），这只是把度平移 1，不影响后面的相关系数。

$e_{jk}$ 与 $P(k'\mid k)$ 满足细致平衡（detailed balance）条件

$$k\,p_k\,P(k'\mid k)=k'\,p_{k'}\,P(k\mid k'),$$

两边都等于 $\langle k\rangle e_{kk'}$。它说明联合分布不能随意指定：一旦给定度分布，条件分布必须与之相容。这一约束在后面推导传播阈值时起关键作用。

从计数到概率：一个可手算的例子

设 $N_k$ 为度为 $k$ 的节点数，$E_{kk'}$ 为连接度 $k$ 与度 $k'$ 节点的边数（$k=k'$ 时计两次），$L$ 为总边数。则

$$e_{kk'}=\frac{E_{kk'}}{2L},\qquad q_k=\frac{kN_k}{2L},\qquad P(k'\mid k)=\frac{E_{kk'}}{kN_k}.$$

以 4 个节点的路径图 $1-2-3-4$ 为例：度序列为 $(1,2,2,1)$，$L=3$。两条端边连接度 1 与度 2，中间一条边连接度 2 与度 2。于是 $E_{12}=E_{21}=2$，$E_{22}=2$（一条边计两次），$e_{12}=e_{21}=e_{22}=1/3$，$e_{11}=0$。边端度分布 $q_1=1/3$、$q_2=2/3$。如果网络是中性的，应有 $e_{11}=q_1^2=1/9$，$e_{22}=4/9$；实际上度 1 节点之间没有边，而度 1 与度 2 节点之间的边比中性预期多（$2/3$ 对 $4/9$），这是一个轻度异配的小网络。

为什么需要压缩描述

$e_{jk}$ 是完整的两点度相关描述，但它有约 $k_{\max}^2/2$ 个自由参数，真实网络中大部分格子只有零星几条边，直接比较两张网络的 $e_{jk}$ 噪声很大。因此实践中常用两类压缩：一个函数 $k_{nn}(k)$，或一个数 $r$。另一条路线是 dK 序列（dK-series; Mahadevan 等, 2006）：0K 保留平均度，1K 保留度分布，2K 保留联合度分布 $e_{jk}$，3K 再保留三节点子图的度组合。Orsini 等（2015, Nature Communications）用 dK 随机网络逐级比较真实网络，发现不少网络的许多常用指标在 2K 或 2.5K（再加上聚集谱）层面就已基本被再现，从而可以判断某个指标是否“超出了低阶统计的解释”。

友谊悖论

中性网络中，沿一条边到达的节点平均度为 $\sum_k k\,q_k=\langle k^2\rangle/\langle k\rangle\ge\langle k\rangle$，等号只在所有节点度相同时成立。这就是 Feld（1991, American Journal of Sociology）描述的友谊悖论：平均而言，你的朋友的朋友比你多。它不是度相关造成的，而是“按边抽样偏向高度节点”的直接结果。在度分布重尾的网络中，$\langle k^2\rangle/\langle k\rangle$ 可以远大于 $\langle k\rangle$。下一节的 $k_{nn}(k)$ 正是在这一基线上判断相关。