从 NetworkX 图中查找连通分量内的子图
Find Subgraphs inside a Connected Component from a NetworkX Graph
我构建了一个包含 50000 个节点和大约 1 亿条边的 NetworkX 图。我使用 nx.connected_components(G) 方法列出了该组的所有连接组件。这种方法导致我拥有节点集群，这样每个节点都有一条路径可以到达该集群中的每个其他节点。现在我想要的是，在每个连接的组件中，我想找到 subgraphs/sub-clusters 这样每个子图都通过一条边相互连接。 NetworkX 中是否有我可以直接使用的方法或可以通过任何其他方式完成此操作的方法？抱歉，我对图论很陌生，所以需要一些指导。
你要的叫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 的解决方案。
结果
如果我没理解错的话，对于每个子图，你都想找到所有 graph cuts of size 1, i.e. you want to find all edges, that if taken away partition the graph into two subgraphs. These edges are called bridges 并且有高效的算法可以找到它们。 networkx 中的实现可通过 networkx.algorithms.bridges.bridges 访问。
我构建了一个包含 50000 个节点和大约 1 亿条边的 NetworkX 图。我使用 nx.connected_components(G) 方法列出了该组的所有连接组件。这种方法导致我拥有节点集群，这样每个节点都有一条路径可以到达该集群中的每个其他节点。现在我想要的是，在每个连接的组件中，我想找到 subgraphs/sub-clusters 这样每个子图都通过一条边相互连接。 NetworkX 中是否有我可以直接使用的方法或可以通过任何其他方式完成此操作的方法？抱歉，我对图论很陌生，所以需要一些指导。
你要的叫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 的解决方案。
结果
如果我没理解错的话，对于每个子图，你都想找到所有 graph cuts of size 1, i.e. you want to find all edges, that if taken away partition the graph into two subgraphs. These edges are called bridges 并且有高效的算法可以找到它们。 networkx 中的实现可通过 networkx.algorithms.bridges.bridges 访问。