python - 考虑权重的networkx is_isomorphic

Question

import networkx as nx
import numpy as np

def is_isomorphic(graph1, graph2):
    G1 = nx.from_numpy_matrix(graph1)
    G2 = nx.from_numpy_matrix(graph2)
    isomorphic = nx.is_isomorphic(G1,G2)
    print("isomorphic? \t", str(isomorphic))
    return isomorphic


graph1 = np.array([[1, 0.5, 1.5],
                   [0, 1,   0],
                   [0, 0,   2]])

graph2 = np.array([[1,  0, 1.5],
                   [0,  1, 1.5],
                   [0,  0, 2]])

print(is_isomorphic(graph1,graph2))

假设我有两个图:graph1，其中节点 1 与节点 1 和 2 绑定(bind)；graph2，其中节点 2 与两个节点 1 绑定(bind)。因此，如果我们将这些图视为分子，则这两个图不是同构的。现在，当我调用 is_isomorphic() 时，会产生 True 值，这意味着两个图是同构的。

如何确保考虑到权重？

谢谢!

Answer 1

您可以使用iso.categorical_edge_match定义一个比较函数，以便在检查两个网络是否同构时，考虑边缘权重属性:

G1 = nx.from_numpy_matrix(graph1)
G2 = nx.from_numpy_matrix(graph2)

请注意，权重基本上只是边缘属性:

G1.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 1, {'weight': 0.5})...
G2.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 2, {'weight': 1.5})...

因此，我们要定义一个比较函数，当 iso.categorical_edge_match 收到来自 G1 和 G2 的两条边时，对这些属性进行比较:

import networkx.algorithms.isomorphism as iso
em = iso.categorical_edge_match('weight', 'weight')

现在，当使用nx.is_isomorphic时，将edge_match设置为上面使用iso.categorical_edge_match定义的比较函数em ，以便调用它来比较每条边以检查它们的权重是否相等:

nx.is_isomorphic(G1, G2, edge_match=em)
# False

由于edge_match需要一个可调用的，并且我们只想比较一个属性，在这种情况下，我们还可以定义我们自己的简单比较函数，以便边缘属性还考虑:

nx.is_isomorphic(G1, G2, edge_match=lambda x,y: x['weight']==y['weight'])
# False