5
$\begingroup$

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.

  • 0
    @anon yeah, one idea is to do that (even just take the difference of adjacency matrices and count non-zero elements), then use some heuristics to find an approximation to the permutation that minimizes the matrix-difference. That's what I'm trying to do right now.2011-07-19

1 Answers 1

4

When you write, "There are several measures with similar properties," that makes it sound like you are already aware of more than one possible answer to your question - but you don't give any examples, so there is no way for us to know whether you're already aware of something we might think to suggest. Anyway, here's one possibility, for graphs with the same (finite) number of vertices:

To each graph on $n$ vertices, assign a vector $\bf v$ in ${\bf R}^n$ given by the degree sequence of the graph, that is, a list of the degrees of the vertices, sorted from greatest to least. Then, given two graphs, let $s$ be ordinary Euclidean distance between the vectors corresponding to the two graphs.

Good news: this satisfies at least two of your four bullet-points, and should be very easy to compute.

Bad news: it may be zero even for graphs that are not isomorphic (but of course you know that's unavoidable, on current knowledge).

Neither-here-nor-there news: I have no idea whether this is "commonly used."