生物医学网络科学Biomedical Network Science
度相关性与网络结构的高阶统计11 / 13

数学推导与算法

阅读
约 1 分钟

A. 细致平衡与中性网络的 knnk_{nn}

由 ekk′e_{kk'} 的两种写法 ekk′=qkP(k′∣k)=qk′P(k∣k′)e_{kk'}=q_kP(k'\mid k)=q_{k'}P(k\mid k') 及 qk=kpk/⟨k⟩q_k=kp_k/\langle k\rangle，得细致平衡 kpkP(k′∣k)=k′pk′P(k∣k′)kp_kP(k'\mid k)=k'p_{k'}P(k\mid k')。

把 knn(k)k_{nn}(k) 按 kpkkp_k 加权求和：

∑kkpkknn(k)=∑k∑k′k′kpkP(k′∣k)=⟨k⟩∑k′k′∑kekk′=⟨k⟩∑k′k′qk′=⟨k2⟩.\sum_k k\,p_k\,k_{nn}(k)=\sum_k\sum_{k'}k'\,k\,p_k\,P(k'\mid k) =\langle k\rangle\sum_{k'}k'\sum_k e_{kk'}=\langle k\rangle\sum_{k'}k'q_{k'}=\langle k^2\rangle .

这一恒等式对任何相关结构都成立。若 ⟨k2⟩\langle k^2\rangle 随 NN 发散，则必有某些 kk 的 knn(k)k_{nn}(k) 发散，矩阵 Ckk′=kP(k′∣k)C_{kk'}=kP(k'\mid k) 的最大特征值也无界，SIS 阈值趋于 0。中性网络中 P(k′∣k)=qk′P(k'\mid k)=q_{k'}，直接得到 knn(k)=⟨k2⟩/⟨k⟩k_{nn}(k)=\langle k^2\rangle/\langle k\rangle。

B. 度相关系数的边列表形式

把每条无向边记为两个有序对 (ji,ki)(j_i,k_i) 与 (ki,ji)(k_i,j_i)，共 2L2L 个。xx 与 yy 的边际分布相同（都是 qkq_k），均值 k‾e=12L∑i(ji+ki)\bar k_e=\frac{1}{2L}\sum_i(j_i+k_i)，方差 12L∑i(ji2+ki2)−k‾e2\frac{1}{2L}\sum_i(j_i^2+k_i^2)-\bar k_e^2，协方差 1L∑ijiki−k‾e2\frac{1}{L}\sum_i j_ik_i-\bar k_e^2。二者之比就是上文的 rr。把求和改写为对度对 (j,k)(j,k) 计数，即得 r=∑jkjk(ejk−qjqk)/σq2r=\sum_{jk}jk(e_{jk}-q_jq_k)/\sigma_q^2。由于 Pearson 相关对平移不变，用度或剩余度结果相同。

C. 结构截断

设 Ekk′E_{kk'} 为连接度 kk 与 k′k' 节点的边数（k=k′k=k' 时计两次），Ekk′=⟨k⟩Nekk′E_{kk'}=\langle k\rangle N e_{kk'}。简单图中它不能超过

mkk′=min⁡{kNk,k′Nk′,NkNk′},m_{kk'}=\min\{kN_k,\;k'N_{k'},\;N_kN_{k'}\},

分别对应“度 kk 一侧的边端总数”“度 k′k' 一侧的边端总数”“两组节点之间的节点对数”。定义 rkk′=Ekk′/mkk′≤1r_{kk'}=E_{kk'}/m_{kk'}\le1。当 k,k′k,k' 足够大（k>Npk′k>Np_{k'} 且 k′>Npkk'>Np_k）时，最小值是 NkNk′=N2pkpk′N_kN_{k'}=N^2p_kp_{k'}。中性网络中 ekk′=kk′pkpk′/⟨k⟩2e_{kk'}=kk'p_kp_{k'}/\langle k\rangle^2，于是

rkk′=⟨k⟩Nkk′pkpk′/⟨k⟩2N2pkpk′=kk′⟨k⟩N.r_{kk'}=\frac{\langle k\rangle N\,kk'p_kp_{k'}/\langle k\rangle^2}{N^2p_kp_{k'}}=\frac{kk'}{\langle k\rangle N}.

令 rksks=1r_{k_sk_s}=1，得 ks=(⟨k⟩N)1/2k_s=(\langle k\rangle N)^{1/2}。它与度分布形式无关。与 kmax∼N1/(γ−1)k_{\max}\sim N^{1/(\gamma-1)} 比较，γ<3\gamma<3 时 kmax≫ksk_{\max}\gg k_s，中性的简单无标度网络不存在。

D. 无相关网络的富人俱乐部系数

在无相关网络中，度为 kik_i 与 kjk_j 的两节点相连的概率约为 kikj/(⟨k⟩N)k_ik_j/(\langle k\rangle N)（不超过 1 时）。富节点集合 R={i:ki>k}R=\{i:k_i>k\} 内的期望边数为

𝔼[E>k]≈12∑i≠j∈Rkikj⟨k⟩N≈(∑i∈Rki)22⟨k⟩N,ϕunc(k)≈k‾R2⟨k⟩N,\mathbb E[E_{>k}]\approx\frac12\sum_{i\ne j\in R}\frac{k_ik_j}{\langle k\rangle N}\approx\frac{\big(\sum_{i\in R}k_i\big)^2}{2\langle k\rangle N}, \qquad \phi_{\text{unc}}(k)\approx\frac{\bar k_R^{\,2}}{\langle k\rangle N},

其中 k‾R\bar k_R 为富节点的平均度，它随阈值 kk 增大，所以 ϕunc(k)\phi_{\text{unc}}(k) 随 kk 单调上升，大致按 k2k^2 增长（直到结构截断使概率饱和）。这就是必须用 ϕran\phi_{\text{ran}} 归一化的原因。

E. 算法

算法 1  邻居平均度函数 k_nn(k)（对数分箱）
输入：无向简单图 G
1. 对每个节点 i：k_nn,i ← (Σ_{j∈N(i)} k_j) / k_i          # O(L)
2. 取对数间隔的度区间 [b_0,b_1), [b_1,b_2), …
3. 对每个区间：k̄ ← 区间内节点度的均值；k_nn ← 区间内 k_nn,i 的均值（节点数 < 3 时跳过）
4. 输出 (k̄, k_nn) 序列；在选定区间内对 log k_nn ~ log k 做线性拟合，斜率为 μ
复杂度：O(L + N)
算法 2  Xulvi-Brunet–Sokolov 重连（保度、保持简单图）
输入：简单图 G，交换次数 S，方向 mode ∈ {同配, 异配}，概率 p
1. 重复直到成功交换 S 次：
2.     随机取两条边 (a,b)、(c,d)；若四个端点有重复，跳过
3.     以概率 p：按度从大到小排序为 v1 ≥ v2 ≥ v3 ≥ v4
4.         同配：新边 (v1,v2)、(v3,v4)；异配：新边 (v1,v4)、(v2,v3)
5.     否则：随机打乱四个端点，两两配对
6.     若新边已存在（会产生重边）：拒绝
7.     删除旧边，加入新边
复杂度：每次尝试 O(1)（用哈希集合判断边是否存在）
算法 3  k-核分解（按当前度剥离）
输入：无向图 G
1. d[v] ← deg(v)；把所有节点放入以 d 为键的桶（或最小堆）
2. k ← 0
3. 当还有未删除节点：
4.     取出当前 d 最小的节点 v；k ← max(k, d[v])；core[v] ← k；删除 v
5.     对 v 的每个未删除邻居 u：d[u] ← d[u] − 1，更新其在桶中的位置
6. 返回 core
复杂度：桶实现 O(L)（Batagelj & Zaversnik）；堆实现 O(L log N)
算法 4  富人俱乐部检验
输入：图 G，度阈值集合 K，随机网络数 M
1. 对每个 k ∈ K：计算 φ_obs(k)
2. 对 m = 1..M：用双边交换生成保度随机网络 G_m（交换次数 ≥ 10L），计算 φ_m(k)
3. φ_ran(k) ← mean_m φ_m(k)；ρ(k) ← φ_obs(k) / φ_ran(k)
4. p(k) ← (1 + #{m: φ_m(k) ≥ φ_obs(k)}) / (M + 1)
5. 多个 k 的检验：用每次置换中 max_k [φ_m(k)/φ_ran(k)] 构造零分布，或预先规定 k 区间
6. 报告 ρ(k) 曲线、N_{>k} 与 p(k)；N_{>k} 很小的区间只作描述

继续阅读