网络传播：带重启随机游走与热扩散

两种传播的定义

记邻接矩阵 $A$，度矩阵 $D=\operatorname{diag}(k_v)$，列随机转移矩阵 $W=AD^{-1}$，随机游走拉普拉斯 $L=I-W$。

带重启的随机游走：游走者每步以概率 $1-r$ 走到随机邻居，以概率 $r$ 跳回种子分布 $p_0$： $$p_{t+1}=(1-r)Wp_t+rp_0,\qquad p^\ast=r\big(I-(1-r)W\big)^{-1}p_0=r\sum_{\ell\ge0}(1-r)^\ell W^\ell p_0 .$$

热扩散：把 $p_0$ 看作初始热量，按 $\dfrac{dp}{dt}=-Lp$ 扩散时间 $t$： $$p(t)=e^{-tL}p_0=e^{-t}\sum_{\ell\ge0}\frac{t^\ell}{\ell!}W^\ell p_0 .$$

两者都是对所有长度 $\ell$ 的游走加权求和，区别只在权重：RWR 用几何权重 $r(1-r)^\ell$，平均游走长度 $(1-r)/r$；热扩散用泊松权重 $e^{-t}t^\ell/\ell!$，平均长度 $t$。$r$ 越大或 $t$ 越小，传播越局部。热扩散在固定时间截断；HotNet2 所用的“绝热”热扩散（insulated heat diffusion）每一步都有一部分热量留在原处，形式上与 RWR 相同。

归一化方式

• 列随机 $W=AD^{-1}$：保持概率守恒，$\sum_v p^\ast_v=1$；但 $r\to0$ 时 $p^\ast$ 趋于平稳分布 $\pi_v=k_v/2M$，分数正比于度。
• 行随机 $D^{-1}A$：相当于对邻居分数求平均，偏向低度节点。
• 对称归一化 $D^{-1/2}AD^{-1/2}$（PRINCE 采用）：介于两者之间，分数的度依赖较弱，但总量不再守恒。

归一化方式会改变排名，应在方法中写明。

手算例：三节点链

链 $1-2-3$，种子为节点 1，$r=0.5$。$W$ 的列为：节点 1 的全部概率转到 2；节点 2 的概率各一半转到 1 和 3；节点 3 的全部概率转到 2。稳态方程 $$p_1=0.25p_2+0.5,\quad p_2=0.5(p_1+p_3),\quad p_3=0.25p_2,$$ 解得 $p^\ast=(7/12,\,4/12,\,1/12)$。节点 3 离种子两步，得分是节点 2 的四分之一。若把 $r$ 降到 0.1，分数会向平稳分布 $(1/4,1/2,1/4)$ 靠拢，度为 2 的节点 2 反而得分最高——这就是度偏倚的来源。

参数怎么选

• 用留出种子做交叉验证：隐藏一部分已知疾病基因，按召回率（如前 $K$ 名中找回的比例）或 AUROC 选择 $r$ 或 $t$。
• 看稳定性而不只看最优值：在合理范围内结果稳定，才说明结论不依赖参数；报告参数扫描结果。
• 检查分数与度的相关：过度扩散时，排名会退化为按度排序。

代码示例在埋入 60 个模块节点（公开 30 个为种子）的 2000 节点合成网络中扫描参数：RWR 在 $r=0.2$–0.8、热扩散在 $t=0.5$–2 时，前 30 名可找回 14–15 个隐藏模块成员；$r=0.05$ 时只找回 6 个、分数与度的 Spearman 相关升到 0.86；$t=20$ 时一个也找不回，相关达 0.93。用 200 组度匹配随机种子把 $r=0.05$ 的分数转成 $z$ 分数后，与度的相关降到 0.10，命中数升到 10。这些数字只说明趋势，具体值依赖合成网络。