Trying to match nodes between similar graphs

Question

I am looking for an algorithm for matching nodes in similar graphs. The number of nodes is not equal, but each graph represents the same system.

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

Where to begin?

undirected Vertex-labeled multigraph weighted rare Knots: 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 the corresponding nodes and edges between two graphs.

This problem is described in technical documents as partial isomorphism, graph alignment and maximal common subgraph

Answer 1

Here the 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 the same degree.

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

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

Result: . The algorithm will return TRUE for any graph B that has many nodes that make up 75% or more of it, equivalent to many nodes that make up 95% or more of graph A