[Nauty] Measuring similarity between graphs

[Noah Giansiracusa]

Does anyone know what methods are available for determining how similar two graphs are?  I know there are naive approaches, such as looking at the degrees of the vertices in the two graphs, but I would like a way to tell how 'close' two graphs are from being isomorphic.  I can imagine one way would be to look at how many subgraphs from the two graphs are isomorphic to each other.  Or perhaps there is some way to do this by finding out how many edges and/or vertices must be removed from either graph so that they become isomorphic.  However, I'm not sure how easy either of these approaches would be to implement, and what other methods exist.

Noah Giansiracusa