使用 NetworkX 的图之间的相似性度量

Question

我有两个图 A和B。它们可能是同构的，完全不同的，或者有一些相似之处（很少有节点是相同的，或者很少有节点共享相同的边）。

我想看看/检查这些图表有多么不同/相似。networkx.is_isomorphic() 是一种方式。然而，这并不仅仅说明真假。

例如，difference(A,B) 函数返回一个新图，该图包含 A 中存在但 B 中不存在的边；但它需要具有相同数量的节点。

我的图 A 和 B的节点数不同。并且可能有几百个节点。因此，如果不是 NP-Hard，算法将是最好的（就像 NP 难的 graph_edit_distance() 函数）。

Answer 1

不确定这是否正是您正在寻找的内容，但希望您会发现其中一些有用。让我们以下面的图表G为例H：

l1 = [['A','C'], ['A', 'D'], ['I','F'], ['K', 'E'], ['D', 'A'], ['A', 'B'], ['C', 'D']]
l2 = [['A','B'], ['Q', 'D'], ['J','F'], ['A', 'E'], ['D', 'F'], ['X','A']]

G = nx.from_edgelist(l1)
H = nx.from_edgelist(l2)

G.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B'))
H.nodes()
# NodeView(('A', 'B', 'Q', 'D', 'J', 'F', 'E', 'X'))

为了获得相似性度量，您可能会考虑到边并集的交集，提出一些相似性或差异的自定义定义。也许杰卡德距离是一个不错的选择：

def jaccard_similarity(g, h):
    i = set(g).intersection(h)
    return round(len(i) / (len(g) + len(h) - len(i)),3)

jaccard_similarity(G.edges(), H.edges())
# 0.091

这里可能也有用的是提出一个可视化，让人们了解两个图的相似和不同程度。我们可以从使用 开始compose，这将为我们提供节点集和边集的简单并集：

GH = nx.compose(G,H)
GH.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B', 'Q', 'J', 'X'))

并迭代组合图的边和节点，并根据它们属于哪个图（也同时包括两者）为它们分配颜色。这也可以扩展到添加一些属性来指示它也属于哪个图：

# set edge colors
edge_colors = dict()
for edge in GH.edges():
    if G.has_edge(*edge):
        if H.has_edge(*edge):
            edge_colors[edge] = 'magenta'
            continue
        edge_colors[edge] = 'lightgreen'
    elif H.has_edge(*edge):
        edge_colors[edge] = 'lightblue'

# set node colors
G_nodes = set(G.nodes())
H_nodes = set(H.nodes())
node_colors = []
for node in GH.nodes():
    if node in G_nodes:
        if node in H_nodes:
            node_colors.append('magenta')
            continue
        node_colors.append('lightgreen')
    if node in H_nodes:
        node_colors.append('lightblue')

所以这里相交的节点和边将具有洋红色。否则，如果它们分别属于G或H ，则它们将是绿色或蓝色。 Graph

我们现在可以分别使用上面的边和节点颜色的字典/列表来绘制图形。这应该提供一个很好的方法来查看两个图上相交和不相交的节点/边：

pos = nx.spring_layout(GH, scale=20)
nx.draw(GH, pos, 
        nodelist=GH.nodes(),
        node_color=node_colors,
        edgelist=edge_colors.keys(), 
        edge_color=edge_colors.values(),
        node_size=800,
        width=8,alpha=0.5,
        with_labels=True)