A distance metric between directed weighted graphs
A distance metric between directed weighted graphs
复制标题
有向加权图之间的距离度量
DOI：
10.1109/cdc.2013.6760895
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Carolyn L. Beck
中科院分区：
文献类型：
--
作者：
Yunwen Xu;S. Salapaka;Carolyn L. Beck
有向加权图越来越多地用于对复杂系统和相互作用进行建模，例如相互连接的物理或生物子系统的网络。这些图的分析通常需要某种形式的相异度或距离度量来比较图。在本文中，我们将以前用于比较相同维度的无向无向图的基于连通性的相异度度量扩展为：（1）相同维度的有向加权图和（2）不同维度的有向加权图。据我们所知，这是第一个提出的方法来比较两个图包含不同数量的节点。我们得出的条件下，这种相异性措施是一个伪度量。这种推导提供了新的见解，我们的算法（以前提出）的图聚合优化问题。
Directed weighted graphs are increasingly used to model complex systems and interactions, such as networks of interconnected physical or biological subsystems. The analysis of these graphs often requires some form of dissimilarity, or distance measure to compare graphs. In this paper, we extend connectivity-based dissimilarity measures previously used to compare unweighted undirected graphs of the same dimensions to: (1) directed weighted graphs of the same dimensions and (2) directed weighted graphs of different dimensions. To our knowledge, this is the first approach proposed for comparing two graphs containing different numbers of nodes. We derive the conditions under which this dissimilarity measure is a pseudo-metric. This derivation provides new insights on our algorithms (previously proposed) for the graph aggregation optimization problem.