CODEWITHSUNDEEP
pythonsocial-networkingnetworkx
Randy Olson
Randy Olson

Reputation: 3221

Is there an easy way to prune disconnected networks in a NetworkX graph?

I'm using Python's NetworkX package to calculate a bunch of network statistics for networks of varying size. I'm sweeping an independent parameter that systematically prunes edges, so sometimes a small network will become disconnected from the main network. Is there an easy way to detect and remove those smaller disconnected networks in NetworkX?

Upvotes: 5

Views: 5858

Answers (3)

Rafters
Rafters

Reputation: 144

As the accepted answer is now deprecated here is a better solution for an undirected graph = 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)

For a directed graph, you will need either strongly_connected_components(G) or weakly_connected_components(G) in the place of connected_components(G).

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

Upvotes: 4

Randy Olson
Randy Olson

Reputation: 3221

Sorin is correct. The function is called connected_component_subgraphs in NetworkX.

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

Here's some code that finds the largest network in a NetworkX graph:

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

Upvotes: 7

Sorin
Sorin

Reputation: 11968

The generic algorithm is called connected components. You can find a description here: http://en.wikipedia.org/wiki/Connected_component_(graph_theory). It's fairly easy to implement and linear in the number of edges to run.

Not sure about NetworkX.

Upvotes: 1

Related Questions