从NetworkX图中查找连接组件内的子图

Question

我构建了一个NetworkX图，其中包含50000个节点和大约1亿条边。我使用nx.connected_components（G）方法列出了该组中所有连接的组件。这种方法导致我拥有节点集群，这样每个节点都有一条路径可以到达该集群中的每个其他节点。现在我想要的是，在每个连接的组件中，我想要找到子图/子簇，这样每个子图都通过一条边相互连接。NetworkX中是否有我可以直接使用的方法，或任何其他方式来完成此任务？对不起，我对图论很陌生，所以需要一点指导

Answer 1

如果我理解正确，那么对于每个子图，你想要找到所有大小为1的graph cuts，也就是说，你想要找到所有的边，如果去掉这些边，把图分成两个子图。这些边称为bridges，有高效的算法来查找它们。networkx中的实现可以通过networkx.algorithms.bridges.bridges访问

Answer 2

你想要的是minimum spanning three。使用networkx可以这样做：

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (4,5), (4,6), (5,6)])
nx.draw(nx.minimum_spanning_tree(G), with_labels=True)
plt.show()

然而，我有点怀疑networkx是否能够根据to this benchmark在这么多边上执行。我已经在igraph上测试了connected components算法，它对我也很有效（当然，速度要快得多），所以您可能还想寻找基于igraph的解决方案

结果