有向圖中的路徑相似

Question

我想知道是否有人知道圖論算法提供了一個度量來確定通過有向圖的路徑之間的成對相似度？我想象最簡單的算法/度量只計算兩條路徑共有的節點數量，並且在比較不同長度的路徑的情況下做某種加權。

任何指向引用或實現的指針都將非常感謝。

Answer 1

您可以在兩條路徑的頂點序列之間使用Levenshtein distance。