Shortest path metric compare only the number nodes in the two paths. Suppose we have to compare the two paths in terms of number of nodes, nodes ordering etc then what metric is to be used?
This is something called "Graph similarity". For general graphs, the problem is called "graph matching" or "graph isomorphism". Many of litterateurs covered this topic. e.g., http://www.sciencedirect.com/science/article/pii/S0893965907001012
I did the same thing with a very simple algorithm. I just used 'edit distance' to compare two paths. If you imagine a directed path is a sequence of nodes, any sequencing or text matching algorithm can be used. But of course, if it works or not really depends on your purpose....
Thank You Qian Zhang. I too had Graph edit distance in my mind. I needed someone to corroborate it. Thank You.
Yes. I did use Levenshtein distance. I also tried sth like Smith-Waterman alignment algorithm, and longest common subsequence metric. Again, it really depends on your application. So just try and see which makes more sense.
My work is in weighted directed graphs . I need to compare the predicted path with the actual path in the graph in terms of number of nodes as well as path similarity .So I think Levenshtein distance measure is more appropriate as it caters to insertion,deletion and replacement.
I think the Frechet Metric could be extended to arbitrary directed graphs.
This could be helpful
https://easychair.org/publications/preprint_open/GgCH
- Badges
- Science topic
- Similar topics
- Psychology