使用NetworkX计算图之间的相似度指标

Question

使用NetworkX计算图之间的相似度指标

pythonnetworkinggraphnetworkxgraph-theory

5

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

我想查看/检查这些图形是如何不同/相似的。networkx.is_isomorphic() 是一种方式。但是，这只会返回 true 或 false 而已。

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

我的图形 A 和 B 没有相同数量的节点。并且可能有 几百个节点。因此，算法最好不要是 NP-Hard（像 graph_edit_distance() 函数那样是 NP Hard）。

- iromba

在您的上下文中，“similar”是什么意思？ - Joel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- yatu · Accepted Answer

不确定它是否完全符合您的要求，但希望您能发现其中一些有用的内容。让我们以以下图形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距离是一个不错的选择。

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，并具有绿色或蓝色。

现在，我们可以使用上述颜色字典/列表来绘制图形。这应该是一个很好的方法来查看两个图中的交叉和不相交节点/边缘：

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)