I am looking for some numerical measure $s$ that can tell me how "similar" two graphs are, and it is relatively easy to compute/estimate its value.
I know this is not a very precise question, so here's some more info. For example, something like this is useful:
- if the graphs are isomorphic, then $s=0$.
- if the graphs are not isomorphic, then $s>0$.
- if only a few edges are changed (added/removed) in a graph, the value of similarity between the old and new graph is small
- if the graphs differ more, then $s$ is large
There are several measures with similar properties. I'm wondering if there are any commonly used ones that are easy to estimate on a computer.
Links, suggestions, or just keyword suggestions to search for are most welcome. I am in particular interested in any previous results on this.
EDIT It's also useful for me to have something that only works between graphs of equal vertex count. One possibility would be using some type of edit distance. But estimating this edit distance is not a simple problem at all due to the difficulty of choosing a "matching" vertex labelling between the two graphs.