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

Question

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

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

我从哪里开始？

无向顶点标记多图加权疏节点:2,172边数:3,000

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

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

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 的节点集占图 A 的 75% 或更多，而节点集占图 A 的 95% 或更多，则该算法将返回 TRUE