模糊图匹配

Question

我有一个模糊图G=(V, E)，其中V是顶点集，E是边集。每个顶点都是一个模糊顶点，这意味着它具有一个与其相关联的隶属函数的属性(以某种方式存储在顶点中)。每一条边都是模糊边，这意味着它有一个与其相关联的隶属函数的属性(以某种方式存储在边缘中)。通过这样做，G是一个关于边和顶点的模糊图。

给定G和G2，另一个边和/或顶点数不同(或相等)的模糊图，我需要用一种模糊的方式来比较这两个图。我想检查G2是子图还是G (反之亦然)。有什么算法可以解决这个问题吗？

Answer 1

首先，为了比较两个图，您应该解决子图同构问题，它可以是多项式，也可以不是多项式。

但是你没有图，你有模糊图。我不知道是否存在显式算法，但我会尝试两种方法：

1. 如果可以将隶属度定义为概率，那么首先可以找到“最大相似度”假设通常的图形(P{is member}=1)，然后尝试使用贝叶斯网络 (如果无循环的话)或使用马尔可夫随机场的更一般的方式找到一些关系。
2. 您可以使用蒙特卡罗方法在模糊图之间定义度量。作为一个示例，只需遍历这两个图并在一步产生一些差异时停止。步骤的数量是一个度量。运行n时代，得到max，avg，.如果你的隶属函数有状态，你知道“最大相似度”，那么最后的算法就会有很强的依赖性。

前一种方法应该是快速和可靠的，但是如果你找不到足够的方程，你就什么也没有了。后一种方法看起来更可行，但效率要低得多。

无论如何，定义的度量的可用性是次要的(如果您不解释需求，任何度量都可能是有效的)。