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

度相关对网络过程的影响

阅读
约 3 分钟

度相关改变的不只是一个描述性数字,它会改变发生在网络上的过程。下面的结论多来自模型网络,在真实生物网络中往往与模块、空间约束等因素同时存在。

巨连通分支与鲁棒性

Newman(2002)求解了具有给定 ejke_{jk} 的随机网络的渗流问题:巨分支在矩阵 mjk=kejk/qjm_{jk}=k\,e_{jk}/q_j(以剩余度为下标)的最大特征值达到 1 时出现。无相关时 mm 是秩 1 矩阵,条件退化为熟悉的 Molloy–Reed 判据 ⟨k2⟩/⟨k⟩=2\langle k^2\rangle/\langle k\rangle=2。结论是:

  • 同配网络更早形成巨分支(高度节点相互连接,在稀疏时就能连成一片),对删除高度节点也更稳健(枢纽彼此冗余);
  • 但在边较多时,同配网络的巨分支反而更小,因为大量低度节点只与低度节点相连,未被枢纽“收编”;
  • 异配网络在删除枢纽时更脆弱:每个枢纽带走一批只连向它的低度节点。Vázquez 与 Moreno(2003, PRE)给出了相关网络上点渗流与键渗流阈值的一般表达式。

代码示例“度相关如何改变……”中,同一张 ER 图(N=2000N=2000,⟨k⟩=4\langle k\rangle=4)重连后,保留 30% 的边时同配版巨分支占 0.34、异配版 0.26;保留 90% 时顺序反过来(0.964 对 0.973)。网络在蓄意攻击下的崩解见网络鲁棒性、渗流与级联失效。

流行病传播

异质平均场 SIS 模型中,度为 kk 的节点感染比例 ρk\rho_k 满足

dρkdt=−ρk+λk(1−ρk)∑k′P(k′∣k)ρk′.\frac{d\rho_k}{dt}=-\rho_k+\lambda k(1-\rho_k)\sum_{k'}P(k'\mid k)\rho_{k'} .

在无病态附近线性化,传播阈值由矩阵 Ckk′=kP(k′∣k)C_{kk'}=k\,P(k'\mid k) 的最大特征值 Λm\Lambda_m 决定:λc=1/Λm\lambda_c=1/\Lambda_m(Boguñá & Pastor-Satorras, 2002, PRE)。无相关时 Λm=⟨k2⟩/⟨k⟩\Lambda_m=\langle k^2\rangle/\langle k\rangle,回到度异质性与流行病阈值中的结果。几个要点:

  • 同配性使高度节点形成相互感染的“储库”,通常降低阈值、使疾病在整体稀疏时也能持续;但由于传播主要局限在这个高度节点核心内,最终波及的范围可能更小(Newman, 2002);
  • Boguñá、Pastor-Satorras 与 Vespignani(2003, PRL)证明:只要度分布的二阶矩发散,无论同配还是异配,无标度网络的传播阈值都趋于 0;其原因是细致平衡强制 ∑kkpkknn(k)=⟨k2⟩\sum_k k\,p_k\,k_{nn}(k)=\langle k^2\rangle(推导见数学推导与算法);
  • 在有限网络上,淬火平均场阈值约为 1/λ11/\lambda_1(λ1\lambda_1 为邻接矩阵最大特征值)。代码示例中,同配重连使 λ1\lambda_1 从 5.23 升到 5.93,异配重连降到 4.92。

同步

可同步性常用拉普拉斯矩阵特征值比 λN/λ2\lambda_N/\lambda_2 衡量(越小越容易同步,见拉普拉斯谱与可同步性)。同配使高度节点聚成核心、低度节点形成长链,λ2\lambda_2 变小,可同步性变差;di Bernardo、Garofalo 与 Sorrentino(2007, IJBC)系统研究了度相关对振子网络同步的影响。代码示例中三张度序列相同的网络,λN/λ2\lambda_N/\lambda_2 依次为 173(同配)、94(原始)、59(异配)。同配网络的平均路径长度略短而直径更长,也与这一图景一致(Barabási 书第 7.7 节)。

可控性

结构可控性中驱动节点数由最大匹配决定(见结构可控性与最大匹配)。Pósfai 等(2013, Scientific Reports)发现,聚集与模块性对驱动节点数没有明显影响,而度相关的作用取决于是哪一种有向相关(入-入、出-出、出-入等):驱动节点数可以随相关系数线性变化、二次变化或不变。因此在比较两张调控网络的驱动节点比例时,应检查它们的有向度相关是否不同。