NetworkX 中图形的交集

Question

我有 2 个图，我想获得一个具有相交边的图。例如，如果我们有：

import networkx as nx

graph1 = nx.barabasi_albert_graph(100, 3)
graph2 = nx.watts_strogatz_graph(100, 4, 0.15)
nx.draw_networkx(graph1, with_labels=True)
nx.draw_networkx(graph2, with_labels=True)

如何找到他们的交集？

Answer 1

答案取决于你如何真正定义交点。如果您想要保留两个图中的所有相交边，您可以使用 nx.intersection，如文档中所述，它保留两个图中存在的所有边。假设您有以下图表：

graph1 = nx.barabasi_albert_graph(100, 3)
graph2 = nx.watts_strogatz_graph(100, 4, 0.15)

生成以下图表：

pos = nx.spring_layout(graph1, scale=20, k=3/np.sqrt(graph1.order()))
nx.draw(graph1, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

pos = nx.spring_layout(graph2, scale=20, k=3/np.sqrt(graph2.order()))
nx.draw(graph2, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

我们可以用 nx.intersection 生成两个图的交集。这确实需要两个图中的节点集相同。也不会删除相交节点。为此，您可以使用 nx.isolates 获取孤立节点并将它们从图中删除：

g_int = nx.intersection(graph1, graph2)
g_int.remove_nodes_from(list(nx.isolates(g_int)))

pos = nx.spring_layout(g_int, scale=20, k=3/np.sqrt(g_int.order()))
nx.draw(g_int, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

我们可以很容易地检查这确实是两个图的边的交集：

set_int = set(graph2.edges()).intersection(graph1.edges())
G_set_int = nx.from_edgelist(set_int)
list(nx.connected_components(G_set_int))
# [{1, 2, 3, 4, 6}, {48, 50}, {8, 9, 10, 72}, {76, 78}, {85, 87}, {53, 54}, 
#  {40, 38}, {28, 30}, {20, 21}]

NetworkX 中图形的交集

Intersection of graphs in NetworkX

python

networkx