algorithm - 尝试匹配相似图之间的节点

Question

我正在寻找一种算法来匹配相似图中的节点。节点的数量不相等，但每个图确实代表同一个系统。

所以，我正在寻找相似或模糊的图形匹配或模式识别。

我从哪说起呢？

无向顶点标记的多图加权稀疏节点：2,172 边：3,000

节点有许多独立的属性。边有一个属性，类似于长度。两个图之间对应的节点和边的节点和边属性不相同。

这个问题在技术论文中被描述为部分同构、图对齐和最大公共子图

Answer 1

这是两个图 A 和 B 之间部分同构的基本算法..

---

算法

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)

---

例子

规则：如果节点 i 和节点 j 具有相同的度数，则它们是等价的。

常数： A 上的阈值，p = 0.95 ~ 95%。

常数： B 上的阈值，q = 0.75 ~ 75%。

输出：对于任何图 B 的算法将返回 TRUE，该图 B 的节点集占图 A 的 75% 或更多，相当于图 A 的 95% 或更多的节点集