有没有一种简单的方法在NetworkX图中修剪断开的网络？

Question

我正在使用Python的NetworkX包来计算各种大小的网络的许多网络统计量。我正在扫描一个独立参数，系统地修剪边缘，所以有时一个小网络会与主网络断开连接。在NetworkX中，有没有一种简单的方法来检测和删除这些较小的离散网络？

- Randy Olson

Answer 1

Sorin是正确的。在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

- Randy Olson

Answer 2

由于现在接受的答案已经过时了，这里提供了一个更好的解决方案，针对一个无向图 = 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

- Rafters

Answer 3

这里介绍的通用算法称为连通组件。您可以在此处找到描述: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)。它很容易实现，并且在运行边数方面是线性的。 不确定NetworkX是否支持该算法。

- Sorin

---

我在NetworkX中找到了函数connected_component_subgraphs。干杯！ - Randy Olson

现代版本中的 nx.connected_components。 - bugmenot123