网络之间的距离与相似性

统计推断与多重比较 讨论的是在边、节点或全局指标层面比较两组网络。另一类问题是直接问“两张网络有多不同”：同一被试两次扫描的网络是否相似，疾病组与对照组的网络整体是否不同，一个模型生成的网络与真实网络是否相像，一个物种的相互作用组与另一个物种的有多大差异。这需要定义网络之间的距离或相似度。

两类问题：节点是否对应

Tantardini 等（2019, Scientific Reports）把网络比较方法分为两类：

已知节点对应时

• 边集合距离：汉明距离 $\sum_{i<j}|A_{ij}-B_{ij}|$（两网络边集合对称差的大小）；Jaccard 距离 $1-|E_A\cap E_B|/|E_A\cup E_B|$ 消除了边数的影响。
• 加权矩阵距离：Frobenius 范数 $\|W_A-W_B\|_F$，或边权向量之间的相关。对功能连接矩阵，也可以把相关矩阵看作正定矩阵流形上的点，在切空间中计算距离；这类做法在个体识别与表型预测中常见。
• 考虑传播的距离：DeltaCon（Koutra 等, 2016, ACM Transactions on Knowledge Discovery from Data）比较节点间“亲和度”矩阵，删去连接两个模块的桥边比删去模块内的冗余边带来更大的距离。

节点无对应时

• 指标向量：把度分布、聚集系数、同配系数等拼成特征向量再比较；简单，但只比较了少数相关的统计量。
• 谱距离：比较邻接矩阵或（归一化）拉普拉斯矩阵的特征值序列，如 $d(G,H)=\|\boldsymbol\lambda(G)-\boldsymbol\lambda(H)\|_2$（Wilson & Zhu, 2008, Pattern Recognition）。特征值与标签无关、计算方便；但存在同谱异构图（不同的图有相同的谱），谱距离为 0 并不说明两图相同。
• 小图（graphlet）方法：统计每个节点参与的各种小连通子图“轨道”的分布。Pržulj（2007, Bioinformatics）提出了基于小图度分布的一致性度量并用于比较蛋白质相互作用网络；Yaveroğlu 等（2014, Scientific Reports）提出小图相关距离。
• 图核（graph kernel）：两图之间的内积 $K(G,H)=\langle\phi(G),\phi(H)\rangle$，$\phi$ 为子结构计数特征。Weisfeiler–Lehman（WL）子树核反复把节点标签与其邻居标签的多重集合并重新编码，再统计各轮标签频数（综述见 Kriege, Johansson & Morris, 2020, Applied Network Science）。网络肖像散度（Bagrow & Bollt, 2019, Applied Network Science）则比较全尺度的最短路径距离分布。

选择距离的原则

不同距离关注不同的结构层次，没有普遍最优的选择。Hartle 等（2020, Proceedings of the Royal Society A）提出用“同一生成模型独立抽取的两个网络之间的期望距离”（集合内图距离）来刻画距离度量本身：如果同类随机网络之间的距离已经很大，那么观测到的大距离不说明什么。代码示例比较了 ER、WS、BA 与随机块模型四类网络：拉普拉斯谱距离与 WL 核的“类内/类间”比约为 0.25，度分布 Jensen–Shannon 散度约为 0.45；节点无对应时 Jaccard 距离对同类随机网络也接近 1；谱距离几乎区分不开 ER 与弱模块的随机块模型。