6

I am looking for (or attempting to design) a technique for matching nodes from very similar graphs based on the structure of the graph*. In the examples below, the top graph has 5 nodes, and the bottom graph has 6 nodes. I would like to match the nodes from the top graph to the nodes in the bottom graph, such that the "0" nodes match, and the "1" nodes match, etc. This seems logically possible, because I can do it in my head for these simple examples. Now I just need to express my intuition in code. Are there any established algorithms or patterns I might consider?

(* When I say based on the structure of the graph, I mean the solution shouldn't depend on the node labels; the numeric labels on the nodes are only for demonstration.)

UPDATE: It has been correctly pointed out that using the structure alone, most of these graphs can't be solved with 100% accuracy. I've added some thoughts to each graph.

I'm also interested in the performance of any potential solutions. How well will they scale? Could I merge graphs with millions of nodes?

In more complex cases, I recognize that the best solution may be subject to interpretation. Still, I'm hoping for a "good" way to merge complex graphs.

(These are directed graphs; the thicker portion of an edge represents the head.)

Example 1 This graph is a cycle with 1 node "attached to the outside." After attaching a second node to the outside it's not possible to determine whether the new node (node 5) is attached to node 1 or 3. The 4 nodes composing the cycle can't be perfectly matched either. Example 2 Nodes 1 and 5 can be swapped in the bottom graph without changing the structure. Thus, you can only guess with 50/50 accuracy which is the new node. Example 3 This graph has symmetry in 2 dimensions and can be mirrored without changing the structure. Meaning you can swap several nodes without changing the structure. Example 4 This last graph is the only one for which you can identify the new node with 100% accuracy.

Thanks Kirk Broadhurst, for pointing this out.

  • 1
    This question is probably better suited for stackoverflow. – Oleksi Apr 12 '12 at 4:30
  • 1
    Based "solely on the graph structure", how would you match the 1 to the 1 rather than to the 5 in the second graph? The only graph here that I could match solely on structure would be the last one. All of the others are ambiguous. – Kirk Broadhurst Apr 12 '12 at 4:45
  • @Oleksi This is a design question, far more suitable for Programmers than Stack Overflow. – yannis Apr 12 '12 at 4:47
  • I'll keep that in mind. – Oleksi Apr 12 '12 at 4:51
  • 1
    Checking that two graphs have the same structure is called the graph isomorphism problem, I don't know how your variant is called but that may help you find something. (If I had to propose another SE site, it would be cs or even cstheory). – AProgrammer Apr 12 '12 at 5:05
9

As others pointed out, a site like cstheory may be more helpful. From what I can understand of your problem this sounds pretty much exactly like the subgraph isomorphism problem:

Given two graphs G and H find a subgraph of H that is isomorphic to G.

What you tried to express with "matching" 0 and 1, and so on, is referred to as isomorphism in a graph-theoretic setting. This is the typical mathematical concept of isomorphisms and general graph isomorphism is an interesting problem, for which it is yet unclear if it is NP-complete.

The good news is that this problem is well-known, well-researched and there exists a recursive algorithm that solves it (the paper is linked from the wp article).

The bad news is that the algorithm is exponential (except for some special cases, which seem to not apply to your problem), and in fact, the very problem itself is NP-complete. Yes, unfortunate as it my seem, for the graph isomorphism problem it is not known whether it is NP-complete, but the sub-graph isomorphism problem definitely is NP-complete.

  • Thanks for the magic google words, it's just what I needed. – Buttons840 Apr 12 '12 at 14:20
-2

Answering for question: "Are there any established algorithms or patterns I might consider?"

There is evolutionary algorithm. Each genome was valued by function which count level of matching these graphs.

This kind of solution is not perfect - but you may match many graphs together. Number of possible survival functions are huge and can be easy created.

e.g. lets calculate matching function like: M(G,H) := SUM( for each pair in vertex G and H which is marked as identical m(g,h) ) - where m(g,h) is metric then lets define survival function like: S(t) := SUM(F(G,H) : for all matched graphs ) then start evolutionary algorithm

protected by gnat May 8 at 16:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.