Python实现图相似性分级算法

Question

我正在寻找一个算法的Python实现,它执行以下任务:

给定两个有向图,可能包含周期及其根,对两个图的相似性产生分数.

(Python difflib可以为两个序列执行的方式)

希望这样的实现存在.否则,我会尝试自己实现一个算法.在这种情况下,什么是优选的算法(关于简单性).

算法的工作方式对我来说并不重要,尽管它的复杂性是.此外,只要可以用该DS表示诸如我所描述的图形,也可以使用与不同数据结构一起工作的算法.

我要强调的是,一个实现会更好.

编辑:
似乎同构algortihm是不相关的.有人建议图形编辑距离更接近点,这会将我的搜索范围缩小到一个解决方案,该解决方案执行图形编辑距离或将图形缩小为树,然后执行树编辑距离.
它们的节点由每行的几行汇编代码组成.

Answer 1

另一种方法是使用所谓的Eigenvector Similarity.基本上,您计算每个图的邻接矩阵的拉普拉斯特征值.对于每个图,找到最小的k,使得k个最大特征值的总和构成所有特征值之和的至少90%.如果两个图之间的k值不同,则使用较小的值.然后,相似性度量是图之间的最大k个特征值之间的平方差的总和.这将产生范围[0,∞)中的相似性度量,其中更接近零的值更相似.

例如,如果使用networkx:

def select_k(spectrum, minimum_energy = 0.9):
    running_total = 0.0
    total = sum(spectrum)
    if total == 0.0:
        return len(spectrum)
    for i in range(len(spectrum)):
        running_total += spectrum[i]
        if running_total / total >= minimum_energy:
            return i + 1
    return len(spectrum)

laplacian1 = nx.spectrum.laplacian_spectrum(graph1)
laplacian2 = nx.spectrum.laplacian_spectrum(graph2)

k1 = select_k(laplacian1)
k2 = select_k(laplacian2)
k = min(k1, k2)

similarity = sum((laplacian1[:k] - laplacian2[:k])**2)

Answer 2

我们最终要做的是实现“化学化合物匹配的启发式”中描述的算法。

我们使用 NetworkX 来表示图并查找最大派系。

编辑：

基本上，您创建一个新图，每个节点 (v) 代表图 A (a) 中的节点与图 B (b) 中的节点的可能配对。

如果在您的应用程序中，两个节点 (a,b) 相似或不相似，则从新图中删除对应于不同配对 (a,b) 的节点 (v)。如果两个节点彼此不矛盾，则可以用边连接它们。例如，配对 (a,b) 和 (a,c) 相互矛盾（请参阅文章了解正式定义）。然后，您会在新图中找到一个具有最大节点数的派系。

如果在您的应用程序中，两个节点的相似性不是二元的，则您可以为新节点赋予一定范围内的权重（例如（0,1））。您可以启发式地删除相似度低于预定义阈值的新节点。然后，您在新图中找到一个具有最大权重（节点分配的权重之和）的团。

无论哪种方式，您最终都会生成相似度：团的大小/总权重除以原始图的属性函数（A 和 B 的大小/权重的最大/最小/平均值）。

一个很好的功能是，您可以从您发现的派系中推断出相似性的“来源” - “更强”的配对。

进一步说明： 这些约束取决于应用程序。我们使用该方法来比较函数控制流图对。通常，该方法找到第一个图中的某些节点与第二个图中的某些节点（子图到子图）的匹配。关联图中的每个节点象征着第一图中的单个节点与第二图中的单个节点的可能匹配。由于最终会选择一个派系（节点的子集），因此边缘意味着两个匹配不会相互矛盾。要申请不同的应用程序，您应该询问可能的配对的标准是什么（或者我要创建哪些节点），以及选择一个配对如何影响另一个配对的选择（或者如何将节点与边连接）。