Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) typically used that get the distance between two networks? There are plenty of summary statistics such as connectivity distributions, etc. However, is there any "fine-grained" metric that only vanishes for identical networks, is symmetric, and satisfies the triangle inequality?

Clarifications: this question asks about the distance between two networks, **not** the classical graph-distance between two nodes in a network. Networks are considered "identical" if the adjacency matrices of A and B can be made identical.

Edit: This is a generalization of the Graph Isomorphism Problem, which is not known in P. So the question becomes: are there any estimators sensitive to the "fine-grained" details?

graph edit distance(GED)? E.g.: Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li, "A survey of graph edit distance,"Pattern Analysis and Applications13.1 (2010): 113-129. $\endgroup$ – Joseph O'Rourke Apr 21 '14 at 20:42