生物医学网络科学Biomedical Network Science
社团结构与社区发现14 / 19

划分比较与基准检验

阅读
约 3 分钟

怎样比较两个划分

评价算法、检查稳定性、与已知分组对照，都需要量化两个划分 XX、YY 的相似程度。设 nn 个节点，nxyn_{xy} 为同时属于 XX 中社团 xx 与 YY 中社团 yy 的节点数（列联表），nxn_x、nyn_y 为边际和。

  • 归一化互信息（NMI，Danon 等 2005）：I(X;Y)=∑xynxynlog⁡nxynnxnyI(X;Y)=\sum_{xy}\frac{n_{xy}}{n}\log\frac{n_{xy}\,n}{n_xn_y}， NMI(X,Y)=2I(X;Y)H(X)+H(Y),\text{NMI}(X,Y)=\frac{2I(X;Y)}{H(X)+H(Y)}, HH 为划分的熵。两划分相同时为 1，独立时为 0。
  • 调整兰德指数（ARI，Hubert 与 Arabie 1985）：统计“节点对”的一致性——两个划分是否都把这对节点放在同组（或都分开），再减去随机期望并归一化： ARI=∑xy(nxy2)−[∑x(nx2)∑y(ny2)]/(n2)12[∑x(nx2)+∑y(ny2)]−[∑x(nx2)∑y(ny2)]/(n2).\text{ARI}=\frac{\sum_{xy}\binom{n_{xy}}{2}-\left[\sum_x\binom{n_x}{2}\sum_y\binom{n_y}{2}\right]\big/\binom n2}{\frac12\left[\sum_x\binom{n_x}{2}+\sum_y\binom{n_y}{2}\right]-\left[\sum_x\binom{n_x}{2}\sum_y\binom{n_y}{2}\right]\big/\binom n2}. 完全一致为 1，随机划分的期望为 0，可以为负。
  • 信息变差（VI，Meilă 2007）：VI=H(X)+H(Y)−2I(X;Y)\text{VI}=H(X)+H(Y)-2I(X;Y)，是划分空间中的一个真正的距离（满足三角不等式），完全一致时为 0。

手算例：6 个节点，真实划分 {0,1,2}{3,4,5}\{0,1,2\}\{3,4,5\}，检测划分 {0,1}{2,3,4,5}\{0,1\}\{2,3,4,5\}（节点 2 被放错）。列联表为 (2103)\begin{pmatrix}2&1\\0&3\end{pmatrix}。H(X)=1H(X)=1 比特，H(Y)=−13log⁡213−23log⁡223≈0.918H(Y)=-\frac13\log_2\frac13-\frac23\log_2\frac23\approx0.918，联合熵 ≈1.459\approx1.459，故 I≈0.459I\approx0.459，NMI≈0.479\text{NMI}\approx0.479，VI=1\text{VI}=1 比特。ARI：∑(nxy2)=1+3=4\sum\binom{n_{xy}}2=1+3=4，∑(nx2)=6\sum\binom{n_x}2=6，∑(ny2)=7\sum\binom{n_y}2=7，(62)=15\binom62=15，期望 =42/15=2.8=42/15=2.8，ARI=(4−2.8)/(6.5−2.8)≈0.324\text{ARI}=(4-2.8)/(6.5-2.8)\approx0.324。一个节点放错就让 ARI 降到 0.32，说明它在小网络上相当严格。

NMI 对社团数敏感：把 200 个节点随机分成 50 组，与真实的 4 组划分之间的 NMI 平均约为 0.17，而 ARI 约为 0（代码示例）。比较社团数相差很大的划分时，应使用 ARI、经过机会校正的调整互信息（AMI），或同时报告社团数。此外，NMI 有多种归一化方式（算术平均、几何平均、最大值），报告时要写明。

基准网络

要判断算法能否找到“正确”的社团，需要事先知道答案的人工网络：

  • GN 基准（Girvan 与 Newman 2002）：128 个节点分成 4 组、每组 32 个，平均度 16；改变组外连边的比例，观察算法何时失效。缺点是所有节点度相近、所有社团等大，与真实网络差距大。
  • LFR 基准（Lancichinetti、Fortunato 与 Radicchi 2008）：节点度和社团大小都服从幂律分布，更接近真实网络。混合参数 μ\mu 是每个节点连向社团外的边所占的比例；μ\mu 越大，社团越难识别。NetworkX 提供 LFR_benchmark_graph。
  • 种植划分 SBM：便于与可检测性理论对照。

Lancichinetti 与 Fortunato（2009）在 GN 与 LFR 基准上比较了十余种算法，Infomap 与 Louvain 等方法表现最好；贪心模块度在 LFR 上表现较差。代码示例在 1000 个节点、平均度 20 的 LFR 网络上复现了类似规律：μ≤0.3\mu\le0.3 时 Louvain、Leiden 与标签传播的 NMI 接近 1，贪心模块度已明显下降；μ=0.4\mu=0.4 时标签传播塌缩为单一社团；μ≥0.6\mu\ge0.6 时所有算法都接近失效。

元数据不是金标准

在真实网络上，人们常把节点元数据（已知复合物、GO 注释、脑区的解剖分区、空手道俱乐部的两派）当作“真实划分”。Peel、Larremore 与 Clauset（2017）指出这样做有三个问题：元数据可能与网络结构无关；可能与网络中的另一种结构相关；网络中也可能同时存在多个合理的划分。他们证明了一个“没有免费午餐”定理：不存在对所有网络都最优的社团发现算法。算法结果与元数据不一致时，不能直接断定算法错了；反之，一致也不能证明算法“正确”。更好的做法是把元数据作为待检验的假设，例如用带元数据的 SBM 检验它是否解释了网络结构。

继续阅读