一种图相似度分级算法的Python实现

Question

我正在寻找执行以下任务的算法的Python实现：

给定两个有向图，其中可能包含圈及其根， 对两个图的相似性进行评分。

（Python的difflib对两个序列的执行方式）

希望存在这样的实现。否则，我会自己尝试实现一个算法。在这种情况下，最好实现什么算法（关于简单性）。

算法的工作方式对我来说并不重要，尽管它的复杂性是。 另外，一个与不同数据结构一起工作的算法也是可以接受的，只要一个图（如我所描述的）可以用这个DS表示。

我要强调的是，恳求会更好。

编辑：
似乎同构算法是不相关的。有人建议，图形编辑距离更接近于该点，这会将我的搜索范围缩小到一个解决方案，即执行图形编辑距离或将图形缩小为树，然后执行树编辑距离
节点本身由几行汇编代码组成。

Answer 1

我们最终要做的是实现一个在："Heuristics for Chemical Compound Matching"中描述的算法。

我们使用NetworkX来表示图形和查找max团。

编辑：

基本上，创建一个新的图，每个节点（v）表示图a（a）中的一个节点到图B（B）中的一个节点的可能配对。

如果应用程序中的两个节点（a，b）相似或不相似，则从对应于不同对（a，b）的新图中移除节点（v）。 如果两个节点不互相矛盾，就用一条边连接起来。 例如，（a，b）和（a，c）这两个对相互矛盾（见文章中的形式定义）。 然后在新图中找到一个具有最大节点数的团。

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

不管是哪种方式，最终都会生成相似等级：团的大小/总权重除以原始图的属性函数（a和B的大小/权重的最大/最小/平均值）。

一个很好的特点是你可以从你发现的群体中推断出相似性的“来源”——“更强的”配对。

进一步澄清： 这些约束依赖于应用程序。我们使用这种方法来比较函数控制流图对。通常，该方法会找到第一个图中的某些节点与第二个图中的某些节点（子图到子图）的匹配。关联图中的每个节点表示第一个图中的单个节点与第二个图中的单个节点的可能匹配。因为最终选择了一个团（节点的子集），所以一条边意味着两个匹配并不矛盾。要申请不同的应用程序，您应该询问可能配对的条件是什么（或我要创建什么节点），以及选择一个配对如何影响选择另一个配对（或如何将节点与边连接）。

Answer 2

我们最终要做的是实现一个在："Heuristics for Chemical Compound Matching"中描述的算法。

我们使用NetworkX来表示图形和查找max团。

编辑：

基本上，创建一个新的图，每个节点（v）表示图a（a）中的一个节点到图B（B）中的一个节点的可能配对。

如果应用程序中的两个节点（a，b）相似或不相似，则从对应于不同对（a，b）的新图中移除节点（v）。 如果两个节点不互相矛盾，就用一条边连接起来。 例如，（a，b）和（a，c）这两个对相互矛盾（见文章中的形式定义）。 然后在新图中找到一个具有最大节点数的团。

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

不管是哪种方式，最终都会生成相似等级：团的大小/总权重除以原始图的属性函数（a和B的大小/权重的最大/最小/平均值）。

一个很好的特点是，你可以从你发现的群体中推断出相似性的“来源”——“更强的”配对。

进一步澄清： 这些约束依赖于应用程序。我们使用这种方法来比较函数控制流图对。通常，该方法会找到第一个图中的某些节点与第二个图中的某些节点（子图到子图）的匹配。关联图中的每个节点表示第一个图中的单个节点与第二个图中的单个节点的可能匹配。因为最终选择了一个团（节点的子集），所以一条边意味着两个匹配并不矛盾。要申请不同的应用程序，您应该询问可能配对的条件是什么（或我要创建什么节点），以及选择一个配对如何影响选择另一个配对（或如何将节点与边连接）。

Answer 3

这是一个老问题，但我想分享我的方法。 我有一个CVRP（电容车辆路径问题）任务。我的启发式算法产生了几个不同的图，以便找到一个解决方案。 为了不陷入局部最优，我采用了放松和修复程序。

在这一点上，我不得不过滤掉太相似的溶液。 由于大多数启发式方法在局部搜索过程中使用系统的邻域变化来提供解决方案，所以Edit距离（Levenshtein distance）对我来说是完美的。Levenshtein算法的复杂度为O(n*m)，其中n和m是两个字符串的长度。因此，通过图形节点和路由的字符串表示，我能够计算出相似度。可以将edit operations视为neighborhood operations，因此可以将其视为搜索空间距离（而不是解空间距离）。

牺牲一些速度的更好的/通用方法是Needleman-Wunsch算法。Needleman-Wunsch是一种混合相似性度量，它推广了Levenshtein距离并考虑了两个字符串之间的全局对齐。具体来说，它是通过为两个输入字符串之间的每个对齐指定一个分数并选择最佳对齐的分数（即最大分数）来计算的。两个字符串之间的对齐是其字符之间的一组对应关系，允许有间隙。

例如：

import py_stringmatching as sm
nw = sm.NeedlemanWunsch(gap_cost=0.5, sim_func=lambda s1, s2: (0.0 if s1 == s2 else 1.0))
print('\nNeedleman-Wunsch: ', nw.get_raw_score('045601230', '062401530'))

在示例中，可以使用自定义的Levenshtein算法。

Git中存在Levenshtein的快速实现（使用Cython、Numpy等）。
一个不错的库是py_stringmatching，它包含以下相似算法列表：

• 仿射间隙
• 袋距
• 余弦
• 骰子
• 伊迪迪斯
• 广义Jaccard
• 汉明距离
• 雅卡
• 雅罗
• 雅罗温克勒
• 左旋血凝素
• 蒙古埃尔坎
• 女红
• 重叠系数
• 部分比率
• 部分标记排序
• 比率
• 史密斯·沃特曼
• 软TF/IDF
• Soundex公司
• 特遣部队/国际国防军
• 标记排序
• 特沃斯基指数

Answer 4

另一种方法是使用所谓的特征向量相似性。基本上，计算每个图的邻接矩阵的拉普拉斯特征值。对于每个图，找到最小的k，使得k最大特征值之和构成所有特征值之和的至少90%。如果两个图之间的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)