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 direc开发者_高级运维ted 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.

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