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

结构截断与结构性异配

阅读
约 2 分钟

简单图与度分布的冲突

在配置模型中，度为 kk 与 k′k' 的两个节点之间的期望边数约为

Ekk′(pair)≈kk′2L=kk′⟨k⟩N.E_{kk'}^{(\text{pair})}\approx\frac{k\,k'}{2L}=\frac{k\,k'}{\langle k\rangle N}.

当两个节点的度都很大时，这个期望值可以超过 1。例如 N=300N=300、L=450L=450 的网络中，两个度为 55 与 46 的枢纽之间“应有”约 2.8 条边。多重图允许这样，网络保持中性；但大多数生物网络被表示为简单图（两节点之间最多一条边），多出的边只能连到别处，主要连到低度节点，网络因此表现出异配。这种完全由约束产生的相关称为结构性异配（structural disassortativity）。

结构截断

结构截断（structural cutoff）ksk_s：度超过 ksk_s 的两个节点在中性网络中的期望边数超过 1，因而在简单图中无法保持中性。对中性网络，

ks∼(⟨k⟩N)1/2.k_s\sim(\langle k\rangle N)^{1/2}.

自然截断（natural cutoff）kmaxk_{\max}：网络中期望的最大度。对 pk∼k−γp_k\sim k^{-\gamma} 的无标度网络，kmax∼kminN1/(γ−1)k_{\max}\sim k_{\min}N^{1/(\gamma-1)}。

比较两个指数即可判断冲突是否存在（Boguñá, Pastor-Satorras & Vespignani, 2004, EPJ B）：

  • γ≥3\gamma\ge3 或泊松度分布：1/(γ−1)≤1/21/(\gamma-1)\le1/2，kmaxk_{\max} 增长不快于 ksk_s，没有冲突；
  • 2<γ<32<\gamma<3：kmax≫ksk_{\max}\gg k_s，度介于两者之间的枢纽必然“缺边”，简单图会表现出异配。

而许多生物网络报告的度指数正落在 2<γ<32<\gamma<3。严格推导见数学推导与算法。

消除结构性相关的办法

  1. 允许重边（多重图），网络回到中性；
  2. 删除度大于 ksk_s 的节点，或在生成模型中把度上限设为 ksk_s；
  3. 最常用：不去“消除”它，而是在相同度序列、同为简单图的随机网络中重新计算度相关，把这部分当作基线（见下一节）。

代码示例“结构截断与伪异配”中，γ=2.2\gamma=2.2、N=5000N=5000 的配置模型保留重边时 r≈−0.01r\approx-0.01，合并重边与自环成为简单图后 r≈−0.14r\approx-0.14；把度上限截在 ksk_s 附近后 rr 回升到约 −0.05-0.05；同平均度的 ER 图 r≈0r\approx0。

熵的视角

Johnson 等（2010, PRL）计算了给定度序列下不同相关程度的网络构型数（熵），发现对高度异质的度序列，熵最大的构型通常是异配的而不是中性的。也就是说，在没有任何特殊机制时，“随机”得到的无标度简单图本来就偏异配；只有偏离这一最大熵预期的相关才提示存在特殊的形成机制。这与下面的保度随机化检验是同一个逻辑。

继续阅读