Trying to match nodes between similar graphs

Question

I am looking for an algorithm to match nodes in similar graphs. The number of nodes are not equal, but each graph does represent the same system.

So, I'm looking for similar or fuzzy graph matching or pattern recognition.

Where do I start?

Undirected Vertex-labelled Multigraph Weighted Sparse Nodes: 2,172 Edges: 3,000

Nodes have a number of independent attributes. Edges have one attribute, similar to length. Node and edge attributes are not identical for corresponding nodes and edges between the two graphs.

This problem is described in technical papers as partial isomorphism, graph alignment and maximum common subgraph

Answer 1

Here's a basic algorithm for partial isomorphism between two graphs A and B ..

---

Algorithm

Given:
- graph A
- graph B
- threshold on A, p in [0.0,1.0)
- threshold on B, q in [0.0,1.0)

1. define: list T = { Nodes in graph B }

2. define: c = 0

3. for every Node i in graph A
   {
       for every Node j in list T
       {
           if(i and j are equivlant)
           {
               c = c + 1

               remove j from list T
           }
       }
   }

4. calculate: x = number of nodes in graph A / c

5. calculate: y = number of nodes in graph B / c

6. return (x > p AND y > q)

---

Example

Rule: Node i and Node j are equivalent if they have same degree.

Constant: Threshold on A, p = 0.95 ~ 95%.

Constant: Threshold on B, q = 0.75 ~ 75%.

Output: The algorithm will return TRUE for any graph B that has set of nodes that make of 75% or more of it equivalent to set of nodes that make 95% or more of graph A