有向图中的路径相似

Question

我想知道是否有人知道图论算法提供了一个度量来确定通过有向图的路径之间的成对相似度？我想象最简单的算法/度量只计算两条路径共有的节点数量，并且在比较不同长度的路径的情况下做某种加权。

任何指向引用或实现的指针都将非常感谢。

Answer 1

您可以在两条路径的顶点序列之间使用Levenshtein distance。