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.

  • 4
    Regarding "compute" as oppose to "estimate", there is unlikely to be a "relatively easy" way to do that, since computing such a function would solve the [graph isomorphism problem](http://en.wikipedia.org/wiki/Graph_isomorphism_problem), for which no polynomial-time algorithm is known.2011-07-18
  • 0
    @joriki Exactly! That is why I'm only looking for estimates to the exact value of such a measure.2011-07-18
  • 0
    Then you should write "estimate" and not "compute/estimate".2011-07-18
  • 2
    An essential point is whether the vertices of your graph are labelled or not. If "yes" and the labels have to correspond then the question is much simpler, if "no" then a practical implementation of your measure would have to include a test for an isomorphism between any two unlabelled graphs.2011-07-18
  • 0
    @Christian, they are not labelled. I don't really want to complicate things by doing a proper test for isomorphism. That's why I said it's OK to have an approximation to the value of this measure. Also, I should have mentioned that my graphs are unlikely to have many symmetries, making the isomorphism problem a little easier.2011-07-19
  • 0
    My first thought was to use some matrix norm on the difference between a matrix associated with each graph (e.g. adjacency, Laplacian) but then that isn't invariant under permutations of vertices, so eh.2011-07-19
  • 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."