I understand graph isomorphism to be a direct type of equality between
two graph structures.

1. What do you call it when two graphs are not isomorphic but similar?
i.e. generated from empirical data.

2. If several possible mapping exists between two not quite isomorphic
graphs how can I determine which mapping is optimal.

3. Are there algorithms related to this problem? If so what are they called?

I'm not sure if you have a clear understanding of what graph
isomorphism means.  It is not that the two graphs are "equal" in the
absolute sense, but rather that there exists a 1-to-1 mapping between
the two graphs' sets of vertices/nodes such that an edge exists
between two nodes in one graph if and only if an edge exists between
the corresponding two nodes in the other graph.

That being said, determining whether two graphs are isomorphic can be
a hard problem.  There are many easy cases, such as when two graphs
have different numbers of nodes, in which one sees quickly that the
graphs are _not_ isomorphic.  But with a large number of nodes of the
same "degree" in both graphs, the problem can become computationally
intractable.

I should say that what I'm discussing is the notion of isomorphism for
undirected simple graphs.  That is where the edge between two nodes
has no specific "direction" and where we only allow one edge between
two distinct nodes.  Various generalizations are possible in which
edges may be labelled to indicate a direction, to allow more than one
edge between the same pair of nodes, or even to allow an edge from a
node to itself (a self-edge or loop).  All of these generalizations
have found useful applications, and to the extent that such features
are incorporated in our notion of a graph (which is usually indicated
by the term "digraph" if directed edges are permitted, or "multigraph"
if more than one edge on a pair of nodes or self-edges are allowed),
we must make a corresponding adjustment in our notion of graph
isomorphism.

Now, with respect of what to "call it when two graphs are not
isomorphic but similar", there is an important notion of embedding one
graph in another, when the graphs may clearly be non-isomorphic (eg.
one graph has more nodes or more edges than the other).

What might make one "embedding" of a graph better than another,
possibly leading to a notion of "best" mapping?  This suggests a
context in which there is more to the graph structure than just nodes
and edges.  For example, we may have some numeric data attached to the
nodes (or to the edges), and we want the image of mapping one graph
into another to match the numeric data as well as possible.

Knowing more about the specific application you have in mind would be
helpful to address the issue of whether there are algorithms related
to your problem.


regards, mathtalk-ga

You are right, isomorphism is not really what I'm looking for, I'm
looking for something related to mapping one graph to another. It is
true that the graphs I'm comparing will be directed and have numerical
data, in this case vectors associated with edges, (though like the
structure of the graph this numeric data will only be similar not and
exact match). The two graphs might not have quite the same number of
nodes and even if they do every node might not map to another node in
the optimal mapping.

I will restate my questions below. The answers I'm looking for are
related to focusing my own continued research, I'm not looking for a
specific algorithm or solution at this time. I'm more interested in
''specific keywords'' that will guide me into further reading on this
subject without having to get a degree in graph theory. When I know a
little bit more about what I'm talking about I might post a more
specific question related to the specific application.

So I can restate my three questions,

1. What nomenclature can be used to describe attempting to map one
graph to another, what is the name of the problem?

2. If there is more than one way to map one graph onto another what
are some methods of determining which mapping between two graphs is
superior?  What is this problem called?

3. What are some names of algorithms that exist to compare graphs, map
one graph to another, or compare mappings?

Thanks.