向量图距离：一种扩展至无向无权图的多维图相似度度量方法

《Scientific Reports》：A novel multidimensional distance measure for graphs

　　

摘要

我们提出了一种新的图之间多维距离度量方法，将我们先前定义的向量树距离（Vectorial Tree Distance, VTD）扩展到了通用无向无权图。我们将这一新的度量方法命名为"向量图距离"（Vectorial Graph Distance, VGD）。该方法通过将基于节点中介中心性构建的有界商图与一种修改后的广度优先搜索（BFS）相结合，将每个图转换为唯一的树结构，从而确保唯一性。转换完成后，利用VTD对所得的树进行比较，得到一个结构化的向量值距离，用以反映图之间的层次差异。我们验证了VGD在区分来自ENZYMES（BRENDA）数据集的分子图和来自蛋白质数据库（Protein Data Bank）的蛋白质数据集所提取的分子图方面的有效性。我们进一步证明，VGD能够成功划分具有不同层次结构的图。该方法能够捕捉有意义的结构差异，并提供一种可解释的、多层次的图相似度度量。