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

Question

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

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

这篇文章提到使用Levenshtein 距离来确定近似相似度。我也意识到汉明距离使用了类似的度量。

我的问题是：

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

谢谢

Answer 1

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

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

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

在将域限制为欧几里得图时，有很多关于这个问题的积极研究，因为这是一个适用于 GIS 等领域的主题，机器人的机器学习应用程序，以及社交网络/人工网络（如网络）上的协同过滤。查看谷歌学者上的文章。