10
$\begingroup$

Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(Let's denote the set of all graphs over the vertices $V$ with $\mG$, so $G_1, G_2 \in \mG$).

Now I'd like to measure how similar (up to isomorphism) those graphs are, so ideally we'd have a metric

$$d: \mathbb G \times \mathbb G \to \mathbb R_{\geq 0}.$$

This should satisfy all the usual axioms of a metric

  1. $d(G, H) = 0 \iff G \simeq H$ (Here we consider isomorphy as equality.)
  2. $d(G, H) = d(H, G)$
  3. $d(G, H) + d(H, I) \geq d(G, I)$

Is there a "useful" example of such a metric?

I know this is a little bit vague, but what I mean by that is that it should not be the trivial metric, and somehow relate to what we intuitively think would make sense: For example it would be nice if the distance if you remove one edge is smaller than if you remove two or more edges, or (I'm not sure if it actually makes sense, so it certainly is not necessary) that the distance between the empty graph and the complete graph is maximal.

For the sake of simplicty you can assume that $V$ is finite.

$\endgroup$
15
$\begingroup$

One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost of a transformation from one to the other (the costs need to be symmetrical for this to be a distance, e.g. the cost of deleting is equal to the cost of adding, and are usually taken to be unitary).

There are applications outside of pure graph theory such as pattern recognition or in bioinformatics (generalisations of string edit distance useful for DNA analysis).

Note that usually we don't consider "edit distance up to isomorphism" as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.

| cite | improve this answer | |
$\endgroup$
12
$\begingroup$

A very natural metric for graphs on the vertex set $[n]$ is $$ d(G,H) = \min_{\sigma \in S_n} |G \Delta H^\sigma|, $$ where $|G \Delta H|$ is the size of the symmetric difference between the edge sets of $G$ and $H$, and $H^\sigma$ is the graph obtained from $H$ by renaming the vertices according to the permutation $\sigma$.

I believe it satisfies all your properties.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for the answer! I believe the suggestion of @eru-cs of using the "graph edit distance" coincides with yours if we also minimize over the vertex permutations, right? $\endgroup$ – flawr Oct 23 at 12:17
  • 1
    $\begingroup$ That definition is more general, since it allows different costs for insertion and deletion; but to get a symmetric function, the costs need to be the same, and so you essentially obtain my definition. $\endgroup$ – Yuval Filmus Oct 23 at 12:51
  • $\begingroup$ Ah I see, thank you very much! $\endgroup$ – flawr Oct 23 at 12:54

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.