Metrics for graph comparison: A practitioner’s guide
Metrics for graph comparison: A practitioner’s guide
复制标题
DOI：
10.1371/journal.pone.0228728
复制
发表时间：
2019-04
期刊：
影响因子：
3.7
通讯作者：
Peter Wills;François G. Meyer
中科院分区：
文献类型：
--
作者：
Peter Wills;François G. Meyer
图结构比较是数据分析和机器学习中普遍存在的任务，在神经科学[1]、网络安全[2]、社交网络分析[3]和生物信息学[4]等领域有着广泛的应用。通过发现和比较这些领域的数据中的模块化社区、丰富的俱乐部、中心和树等结构，可以深入了解图的生成机制和功能属性。通常，两个图通过成对距离测量进行比较，距离较小表示结构相似，反之亦然。常见的选择包括光谱距离（也称为 λ 距离）和基于节点亲和力的距离（例如 DeltaCon [5]）。然而，目前还没有对这些距离度量在区分常见图拓扑和不同结构尺度方面的功效进行比较研究。在这项工作中，我们比较了常用的图度量和距离度量，并证明了它们辨别随机图模型和经验数据集中常见拓扑特征的能力。我们提出了图结构的多尺度图，其中考虑了全局和局部结构对距离度量的影响。基于这种多尺度视图，我们就不同距离度量对经验图数据问题的适用性提出建议。最后，我们介绍 Python 库 NetComp，它实现了本工作中使用的图距离。
Comparison of graph structure is a ubiquitous task in data analysis and machine learning, with diverse applications in fields such as neuroscience [1], cyber security [2], social network analysis [3], and bioinformatics [4], among others. Discovery and comparison of structures such as modular communities, rich clubs, hubs, and trees in data in these fields yields insight into the generative mechanisms and functional properties of the graph. Often, two graphs are compared via a pairwise distance measure, with a small distance indicating structural similarity and vice versa. Common choices include spectral distances (also known as λ distances) and distances based on node affinities (such as DeltaCon [5]). However, there has of yet been no comparative study of the efficacy of these distance measures in discerning between common graph topologies and different structural scales. In this work, we compare commonly used graph metrics and distance measures, and demonstrate their ability to discern between common topological features found in both random graph models and empirical datasets. We put forward a multi-scale picture of graph structure, in which the effect of global and local structure upon the distance measures is considered. We make recommendations on the applicability of different distance measures to empirical graph data problem based on this multi-scale view. Finally, we introduce the Python library NetComp which implements the graph distances used in this work.