如何使用networkx(Python)计算图形编辑距离？

Question

我正在使用图形编辑距离；根据定义，将原图G1变换成与G2同构的图的最小成本和；

图形编辑操作通常包括：

• 顶点插入将单个新标记的顶点引入到图中。
• 顶点删除从图中删除单个（通常是断开连接的）顶点。
• 顶点替换来更改给定顶点的标签（或颜色）。
• 边插入在一对顶点之间引入新的彩色边。
• 边删除删除一对顶点之间的单条边。
• 边缘替换以更改给定边缘的标签（或颜色）。

现在我想使用networkx的实现 - 我没有任何边标签，G1和G2的节点集是相同的，我不想要与G2同构的图，但我想要G2本身；

这主要是因为G1：1->2->3和G2：3->2->1是同构的，但如果节点代表一些事件，从因果关系的角度来看，它们是非常非常不同的；

因此，在这种情况下，我一直在运行如下测试：

import networkx as nx

G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])


nx.graph_edit_distance(G,G2)

但它返回距离为零，这是有道理的，因为图彼此同构；

所以我尝试设置node_match但仍然没有成功

import networkx as nx

def nmatch(n1, n2):
    return n1==n2 

G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])


nx.graph_edit_distance(G,G2, node_match=nmatch)

如果我们假设删除或添加边/顶点的成本为 1，则编辑距离应为 4，因为我们可以：

• 删除 G 中的两条边，添加 G2 中的 2 条边

在不考虑同构但真正等价的情况下计算编辑距离如何合适？

Answer 1

看来你没有在比较你想要的东西。n1在n2nmatch 中总是{}. 来自文档

(...) 也就是说，该函数将接收 n1 和 n2 的节点属性字典作为输入。

您不是比较节点对象，而是与它们关联的字典（作为您需要的任何数据）

您可以在添加节点时将自定义数据添加到该字典中，例如：

import networkx as nx

def nmatch(n1, n2):
    return n1==n2

G=nx.DiGraph()
G.add_node(1, id=1)
G.add_node(2, id=2)
G.add_node(3, id=3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1, id=1)
G2.add_node(2, id=2)
G2.add_node(3, id=3)
G2.add_edges_from([(3, 2),(2,1)])


nx.graph_edit_distance(G,G2, node_match=nmatch)

返回 2，因为您可以进行 2 次边缘替换。如果您希望结果为 4（2 个插入，2 个删除），您可能会增加替换成本