Graph Utilities

driada.network.graph_utils.get_giant_cc_from_graph(G)[source]

Extract the giant (largest) connected component from a graph.

For directed graphs, returns the largest weakly connected component. For undirected graphs, returns the largest connected component. The graph type is preserved (DiGraph remains DiGraph, Graph remains Graph).

Parameters:: G (networkx.Graph or networkx.DiGraph) – Input graph from which to extract the giant component.
Returns:: Subgraph containing only the nodes in the giant connected component. The returned graph type matches the input graph type.
Return type:: networkx.Graph or networkx.DiGraph
Raises:: IndexError – If the graph has no nodes or no connected components.

See also

get_giant_scc_from_graph: Extract giant strongly connected component.
networkx.algorithms.components.connected_components: Find all connected components.
networkx.algorithms.components.weakly_connected_components: Find weakly connected components.

Examples

>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> gcc = get_giant_cc_from_graph(G)
>>> len(gcc) == len(G)  # Karate club is fully connected
True

driada.network.graph_utils.get_giant_scc_from_graph(G)[source]

Extract the giant (largest) strongly connected component from a directed graph.

A strongly connected component is a maximal subgraph where every node can reach every other node via directed paths.

Parameters:

G (networkx.DiGraph) – Directed graph from which to extract the giant strongly connected component.

Returns:

Subgraph containing only the nodes in the giant strongly connected component.

Return type:

networkx.DiGraph

Raises:

ValueError – If the input graph is undirected, as strongly connected components are only meaningful for directed graphs.
IndexError – If the graph has no nodes or no strongly connected components.

See also

get_giant_cc_from_graph: Extract giant connected component.
networkx.algorithms.components.strongly_connected_components: Find all strongly connected components.

Examples

>>> import networkx as nx
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (4, 5)])
>>> scc = get_giant_scc_from_graph(G)
>>> sorted(scc.nodes())
[1, 2, 3]

driada.network.graph_utils.remove_selfloops_from_graph(graph)[source]

Remove all self-loop edges from a graph.

Self-loops are edges that connect a node to itself. The graph type is preserved.

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph from which to remove self-loops.
Returns:: A deep copy of the input graph with all self-loops removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_isolates_and_selfloops_from_graph: Remove both isolates and self-loops.
networkx.classes.function.selfloop_edges: Find all self-loop edges in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 2), (2, 2), (2, 3)])  # (2, 2) is a self-loop
>>> G_clean = remove_selfloops_from_graph(G)
>>> G_clean.number_of_edges()
2

driada.network.graph_utils.remove_isolates_and_selfloops_from_graph(graph)[source]

Remove all isolated nodes and self-loop edges from a graph.

Isolated nodes are nodes with no edges connecting them to other nodes. Self-loops are edges that connect a node to itself. The graph type is preserved.

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph to clean.
Returns:: A deep copy of the input graph with isolated nodes and self-loops removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_selfloops_from_graph: Remove only self-loops.
remove_isolates_from_graph: Remove only isolated nodes.
networkx.algorithms.isolate.isolates: Find isolated nodes in a graph.
networkx.classes.function.selfloop_edges: Find self-loop edges in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 1), (2, 3)])  # Node 1 has only a self-loop
>>> G.add_node(4)  # Add isolated node
>>> G_clean = remove_isolates_and_selfloops_from_graph(G)
>>> sorted(G_clean.nodes())
[2, 3]

driada.network.graph_utils.remove_isolates_from_graph(graph)[source]

Remove all isolated nodes from a graph.

Isolated nodes are nodes with degree 0 (no edges connecting them).

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph from which to remove isolated nodes.
Returns:: A deep copy of the input graph with all isolated nodes removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_isolates_and_selfloops_from_graph: Remove both isolates and self-loops.
networkx.algorithms.isolate.isolates: Find isolated nodes in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 2), (2, 3)])
>>> G.add_node(4)  # Add isolated node
>>> G_clean = remove_isolates_from_graph(G)
>>> sorted(G_clean.nodes())
[1, 2, 3]

driada.network.graph_utils.small_world_index(G, nrand=10, null_model='erdos-renyi')[source]

Calculate the small-world index of a graph.

The small-world index quantifies how much a network exhibits small-world properties compared to random networks. It is defined as: SW = (C/C_rand) / (L/L_rand) where C is clustering coefficient and L is average shortest path length.

Parameters:

G (networkx.Graph) – Input graph (must be connected).
nrand (int, optional) – Number of random graphs to generate for comparison. Default is 10.
null_model ({'erdos-renyi', 'maslov-sneppen'}, optional) – Type of random graph model to use for comparison. Currently only ‘erdos-renyi’ is implemented. Default is ‘erdos-renyi’.

Returns:

Small-world index. Values > 1 indicate small-world properties. Typical small-world networks have SW >> 1.

Return type:

float

Raises:

NotImplementedError – If ‘maslov-sneppen’ null model is requested (not implemented).
networkx.NetworkXError – If the input graph is not connected.

See also

networkx.algorithms.cluster.average_clustering: Compute average clustering coefficient.
networkx.algorithms.shortest_paths.generic.average_shortest_path_length: Compute average shortest path length.
networkx.generators.random_graphs.watts_strogatz_graph: Generate small-world graphs.

Notes

The function only considers connected random graphs for comparison. Small-world networks have high clustering and short path lengths.

Examples

>>> import networkx as nx
>>> G = nx.watts_strogatz_graph(100, 6, 0.3)  # Small-world network
>>> sw = small_world_index(G, nrand=5)
>>> sw > 1  # Should be True for small-world networks
True

Functions for graph manipulation and analysis.

Component Extraction

driada.network.graph_utils.get_giant_cc_from_graph(G)[source]

Extract the giant (largest) connected component from a graph.

For directed graphs, returns the largest weakly connected component. For undirected graphs, returns the largest connected component. The graph type is preserved (DiGraph remains DiGraph, Graph remains Graph).

Parameters:: G (networkx.Graph or networkx.DiGraph) – Input graph from which to extract the giant component.
Returns:: Subgraph containing only the nodes in the giant connected component. The returned graph type matches the input graph type.
Return type:: networkx.Graph or networkx.DiGraph
Raises:: IndexError – If the graph has no nodes or no connected components.

See also

get_giant_scc_from_graph: Extract giant strongly connected component.
networkx.algorithms.components.connected_components: Find all connected components.
networkx.algorithms.components.weakly_connected_components: Find weakly connected components.

Examples

>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> gcc = get_giant_cc_from_graph(G)
>>> len(gcc) == len(G)  # Karate club is fully connected
True

driada.network.graph_utils.get_giant_scc_from_graph(G)[source]

Extract the giant (largest) strongly connected component from a directed graph.

A strongly connected component is a maximal subgraph where every node can reach every other node via directed paths.

Parameters:

G (networkx.DiGraph) – Directed graph from which to extract the giant strongly connected component.

Returns:

Subgraph containing only the nodes in the giant strongly connected component.

Return type:

networkx.DiGraph

Raises:

ValueError – If the input graph is undirected, as strongly connected components are only meaningful for directed graphs.
IndexError – If the graph has no nodes or no strongly connected components.

See also

get_giant_cc_from_graph: Extract giant connected component.
networkx.algorithms.components.strongly_connected_components: Find all strongly connected components.

Examples

>>> import networkx as nx
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (4, 5)])
>>> scc = get_giant_scc_from_graph(G)
>>> sorted(scc.nodes())
[1, 2, 3]

Graph Cleaning

driada.network.graph_utils.remove_selfloops_from_graph(graph)[source]

Remove all self-loop edges from a graph.

Self-loops are edges that connect a node to itself. The graph type is preserved.

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph from which to remove self-loops.
Returns:: A deep copy of the input graph with all self-loops removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_isolates_and_selfloops_from_graph: Remove both isolates and self-loops.
networkx.classes.function.selfloop_edges: Find all self-loop edges in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 2), (2, 2), (2, 3)])  # (2, 2) is a self-loop
>>> G_clean = remove_selfloops_from_graph(G)
>>> G_clean.number_of_edges()
2

driada.network.graph_utils.remove_isolates_from_graph(graph)[source]

Remove all isolated nodes from a graph.

Isolated nodes are nodes with degree 0 (no edges connecting them).

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph from which to remove isolated nodes.
Returns:: A deep copy of the input graph with all isolated nodes removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_isolates_and_selfloops_from_graph: Remove both isolates and self-loops.
networkx.algorithms.isolate.isolates: Find isolated nodes in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 2), (2, 3)])
>>> G.add_node(4)  # Add isolated node
>>> G_clean = remove_isolates_from_graph(G)
>>> sorted(G_clean.nodes())
[1, 2, 3]

driada.network.graph_utils.remove_isolates_and_selfloops_from_graph(graph)[source]

Remove all isolated nodes and self-loop edges from a graph.

Isolated nodes are nodes with no edges connecting them to other nodes. Self-loops are edges that connect a node to itself. The graph type is preserved.

Parameters:: graph (networkx.Graph or networkx.DiGraph) – Input graph to clean.
Returns:: A deep copy of the input graph with isolated nodes and self-loops removed. The graph type matches the input.
Return type:: networkx.Graph or networkx.DiGraph

See also

remove_selfloops_from_graph: Remove only self-loops.
remove_isolates_from_graph: Remove only isolated nodes.
networkx.algorithms.isolate.isolates: Find isolated nodes in a graph.
networkx.classes.function.selfloop_edges: Find self-loop edges in a graph.

Examples

>>> import networkx as nx
>>> G = nx.Graph([(1, 1), (2, 3)])  # Node 1 has only a self-loop
>>> G.add_node(4)  # Add isolated node
>>> G_clean = remove_isolates_and_selfloops_from_graph(G)
>>> sorted(G_clean.nodes())
[2, 3]

Network Metrics

driada.network.graph_utils.small_world_index(G, nrand=10, null_model='erdos-renyi')[source]

Calculate the small-world index of a graph.

The small-world index quantifies how much a network exhibits small-world properties compared to random networks. It is defined as: SW = (C/C_rand) / (L/L_rand) where C is clustering coefficient and L is average shortest path length.

Parameters:

G (networkx.Graph) – Input graph (must be connected).
nrand (int, optional) – Number of random graphs to generate for comparison. Default is 10.
null_model ({'erdos-renyi', 'maslov-sneppen'}, optional) – Type of random graph model to use for comparison. Currently only ‘erdos-renyi’ is implemented. Default is ‘erdos-renyi’.

Returns:

Small-world index. Values > 1 indicate small-world properties. Typical small-world networks have SW >> 1.

Return type:

float

Raises:

NotImplementedError – If ‘maslov-sneppen’ null model is requested (not implemented).
networkx.NetworkXError – If the input graph is not connected.

See also

networkx.algorithms.cluster.average_clustering: Compute average clustering coefficient.
networkx.algorithms.shortest_paths.generic.average_shortest_path_length: Compute average shortest path length.
networkx.generators.random_graphs.watts_strogatz_graph: Generate small-world graphs.

Notes

The function only considers connected random graphs for comparison. Small-world networks have high clustering and short path lengths.

Examples

>>> import networkx as nx
>>> G = nx.watts_strogatz_graph(100, 6, 0.3)  # Small-world network
>>> sw = small_world_index(G, nrand=5)
>>> sw > 1  # Should be True for small-world networks
True