algorithm - 模糊图匹配

Question

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

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

Answer 1

首先，要比较两个图，您应该解决 Subgraph isomorphism problem , 它可以是多项式也可以不是。

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

1. 如果您可以将隶属度定义为概率，则可以先找到假设通常图形 (P{is member}=1) 的“最大相似度”，然后尝试找到一些关系使用 Bayesian networks (如果是非循环的)或以更一般的方式使用 Markov random fields .

2. 您可以使用 Monte Carlo methods 定义模糊图之间的度量.作为一个示例，简单地走两张图，当一步产生一些差异时停止。步数是一个指标。运行 n 次并获得 max, avg, ... 最终算法强烈依赖于你的隶属函数是否有状态，你知道“最大相似度”等等...

前一种方法应该快速可靠，但如果找不到合适的方程式，您将一无所获。后一种方法看起来更可行，但效率要低得多。

无论如何，定义的指标的可用性是主观的(如果您不解释要求，任何指标都可能有效)。