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

Question

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

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

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

我的问题是：

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

谢谢

Answer 1

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

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

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

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