Algorithm to compare similarity of directed paths through directed graph

Question

I have a directed graph with two directed paths in it.

I want an algorithm to determine the similarity between the two paths.

This post mentions using the Levenshtein distance to determine an approximate similarity. I also realize that the Hamming distance uses a similar metric.

My question is:

How do you handle the case where two paths run parallel to each other. That is if the two paths have no similar nodes, yet would be considered 'similar' because their paths travel in the same direction very close to each other.

Thanks

Answer 1

The simple answer is that this is a very hard question, and relies a lot on your definition of what 'similar' means in a graph. In most graphs you could rearrange the nodes of two disjoint paths in a planar fashion so as to appear to run 'parallel'.

A good place to start looking at more advanced similarity metrics would be to consider the graph's adjacency matrix, and look at various matrix similarity algorithms.

Edit: Restricting the question to Euclidian graphs

There's plenty of active research on this question when restricting the domain to Euclidian graphs, as this is an applicable topic to areas like GIS, machine learning applications to robotics, and collaborative filtering on social networks / artificial networks like the web. Check out the articles on google scholar.