是否有一种简单的方法可以修剪NetworkX图中断开连接的网络？

Question

我正在使用Python的NetworkX软件包为不同大小的网络计算一堆网络统计信息。我正在扫描一个系统地修剪边缘的独立参数，因此有时一个小网络将与主网络断开连接。是否有一种简单的方法来检测和删除NetworkX中那些较小的断开连接的网络？

Answer 1

索林是正确的。该功能在NetworkX中称为connected_component_subgraphs。

文档：http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.connected.connected_component_subgraphs.html#networkx.algorithms.components.connected.connected_component_subgraphs

以下是一些代码，可以找到NetworkX图中最大的网络：

cur_graph = # whatever graph you're working with

if not nx.is_connected(cur_graph):
    # get a list of unconnected networks
    sub_graphs = nx.connected_component_subgraphs(cur_graph)

    main_graph = sub_graphs[0]

    # find the largest network in that list
    for sg in sub_graphs:
        if len(sg.nodes()) > len(main_graph.nodes()):
            main_graph = sg

    cur_graph = main_graph

Answer 2

通用算法称为连接组件。你可以在这里找到一个描述：http://en.wikipedia.org/wiki/Connected_component_(graph_theory)。它的实现相当容易，并且要运行的边数是线性的。

关于NetworkX不确定。

Answer 3

由于现在已弃用的答案已被弃用，因此对于无向图= G，这是一个更好的解决方案：

# Generate connected components and select the largest:
largest_component = max(nx.connected_components(G), key=len)

# Create a subgraph of G consisting only of this component:
G2 = G.subgraph(largest_component)

对于有向图，您将需要strongly_connected_components(G)或weakly_connected_components(G)代替connected_components(G)。

https://networkx.github.io/documentation/stable/reference/algorithms/component.html