path - 通过有向图比较有向路径相似度的算法

Question

我有一个有向图，其中有两条有向路径。

我想要一种算法来确定两条路径之间的相似性。

This post使用 Levenshtein distance 提及确定近似相似度。我也意识到Hamming distance使用类似的指标。

我的问题是:

您如何处理两条路径彼此平行的情况。也就是说，如果两条路径没有相似的节点，但会被认为是“相似的”，因为它们的路径在相同的方向上彼此非常接近。

谢谢

Answer 1

简单的答案是，这是一个非常困难的问题，并且很大程度上取决于您对图中“相似”含义的定义。在大多数图形中，您可以以平面方式重新排列两条不相交路径的节点，以使其看起来“平行”运行。

开始查看更高级的相似性度量的一个好地方是考虑图的邻接矩阵，并查看各种 matrix similarity算法。

编辑:将问题限制为欧几里得图

在将领域限制为欧几里得图时，有很多关于这个问题的积极研究，因为这是一个适用于 GIS、机器学习应用到机器人技术以及社交网络/人工网络(如网络)上的协同过滤等领域的主题。查看 google scholar 上的文章.