Path Similarity in a Directed Graph

Question

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.

Any pointers to references or implementations would be most appreciated.

Answer 1

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