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

Question

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

我想查看/查看 这些图表的不同/相似程度 .
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'))

为了获得相似性度量，考虑到边缘联合的交集，您可能会想出一些相似性或差异的自定义定义。也许 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 或 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)