Quantifying change in a graph

Question

I need to a way to express a change in the structure of a given graph G, such that the original graph is G and the changed graph is G'. A change in the graph can be the addition or removal of any number of vertices and/or edges.

Currently, my thought is to express the change as two percentages: the number of vertices in G' as a percentage of the number of vertices in G, and the same for edges. However, it occurs to me that removing a vertex also means removing all edges connected to it.

Are there any standard ways of quantifying the change in a graphs structure?

Answer 1

If you only allow addition or deletion of edges, then there is a way of measuring how "far apart" two graphs are. If $G$ and $G'$ are two graphs on the same vertex set, the edit distance between $G$ and $G'$ is the smallest number of edges of $G$ that must be deleted and non-edges of $G$ that must be added in order to transform $G$ into $G'$. In symbols, $$d(G, G') = \lvert E(G) \triangle E(G') \rvert,$$ where $A \triangle B$ denotes the symmetric difference of $A$ and $B$.

Edit distance was introduced by Axenovich, Kezdy, and Martin in this paper.

Answer 2

This paper describes a metric based on maximal common subgraphs, which the authors claim is superior to the edit distance in some applications.