Given a graph G, and another graph with the same number of vertices G’, one can define a vertex correspondence function f, from the vertex set of G to the vertex set of G’. The correspondence function f needs to be bijective, and it’s purpose is to give information about the relationship between the two graphs. One example of this would be given two isomorphic graphs G and G’, the actual isomorphism would serve as the vertex correspondence function.
I have a large set of data and have turned it in to a graph, and after translating my data and adding some noise, I’d like to find the “best” correspondence between the two graphs from the data (for some sense of the word best).
Are there any documented algorithms for determining a “best” correspondence between vertices in two graphs? I believe I’ve also seen this called the node correspondence problem.
