在有向图路径相似 [英] Path Similarity in a Directed Graph

问题描述

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

I was wondering if anyone knows of a graph-theoretic algorithm that provides a metric for determining the pairwise similarity between paths through a directed graph? I imagine the simplest algorithms/metrics just counts the number of nodes common to both paths and does some sort of weighting in the case of comparing paths of different lengths.

任何指针引用或实现将是最AP preciated。

Any pointers to references or implementations would be most appreciated.

推荐答案

您可以使用 Levenshtein距离两个路径的顶点序列之间

You could use the Levenshtein distance between the vertex sequences of the two paths.

这篇关于在有向图路径相似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！