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.

  • 5
    $\begingroup$ 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, for which no polynomial-time algorithm is known. $\endgroup$
    – joriki
    Jul 18 '11 at 15:45
  • $\begingroup$ @joriki Exactly! That is why I'm only looking for estimates to the exact value of such a measure. $\endgroup$
    – Szabolcs
    Jul 18 '11 at 15:55
  • $\begingroup$ Then you should write "estimate" and not "compute/estimate". $\endgroup$
    – joriki
    Jul 18 '11 at 15:58
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 18 '11 at 18:32
  • $\begingroup$ @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. $\endgroup$
    – Szabolcs
    Jul 19 '11 at 5:43

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."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.