利用NetworkX实现图之间的相似性度量 [英] Similarity measure between graphs using NetworkX

问题描述

我有两个图表A和B。它们可能是同构的、完全不同的，也可能有一些相似之处(少数节点相同，或少数节点共享相同的边)。

我想查看/检查这些图表有多不同/相似。 Networkx.is_isolomic()是一种方法。然而，这并不能说明更多的是真或假。

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

我的图A和B的节点数不同。并且可能有几百个节点。因此，如果算法不是NP-Hard的，那么算法将是最好的(例如，graph_dit_Distance()函数是NP Hard的)。

推荐答案

我不确定它是否完全符合您的要求，但希望您能从中找到一些有用的东西。让我们以以下图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'))

为了获得相似性度量，考虑到边并集的交集，您可能会提出一些相似性或差异的自定义定义。也许Jaccard distance可能是一个很好的候选者：

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或HGraph，则它们将分别为绿色或蓝色。

我们现在可以分别使用上面的边和节点颜色词典/列表绘制图形。这样可以很好地查看两个图上的相交的和不相交的节点/边：

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)

这篇关于利用NetworkX实现图之间的相似性度量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！