Algorithm cost and scaling strategies

Many NetworkX analyses work on 10,000 nodes and never finish on 10 million; experts choose the right tool before starting.

Know the cost before you run something:

Linear, O(n + m): BFS, DFS, components, degree, topological sort, PageRank per iteration. Fine up to millions of edges, if slowly in pure Python.
O(m + n log n) per source: Dijkstra. All-pairs shortest paths multiplies that by n.
O(nm): exact betweenness and closeness. Hours or days on million-edge graphs.
Exponential: simple cycles, all simple paths, cliques, isomorphism and exact colouring on hard instances.

Strategies, in order:

Reduce the graph: take the largest component, remove low-degree nodes or edges under a weight threshold, or analyse a k-core (nx.k_core).
Sample and approximate: betweenness_centrality(G, k=500, seed=1), the nx.approximation module (clique, diameter, treewidth, max independent set), and early cutoffs such as cutoff= on path functions.
Use a backend: dispatch to nx-cugraph (GPU) or nx-parallel with the same code (next lesson).
Switch tools: igraph and graph-tool (C/C++ cores), rustworkx (Rust), GraphFrames on Spark, or a graph database such as Neo4j for interactive queries on huge, changing graphs.

Measure with time.perf_counter() on growing subgraphs and extrapolate before launching a full run. A doubling of n turning 1 minute into 4 is quadratic behaviour.

Example

import time
import networkx as nx

def timed(f, *a, **kw):
    t = time.perf_counter()
    out = f(*a, **kw)
    return out, time.perf_counter() - t

G = nx.barabasi_albert_graph(2_000, 3, seed=7)

exact, t_exact = timed(nx.betweenness_centrality, G)
approx, t_approx = timed(nx.betweenness_centrality, G, k=200, seed=7)

top = lambda s: set(sorted(s, key=s.get, reverse=True)[:10])
print(len(top(exact) & top(approx)) >= 7)   # True: top-10 mostly agree
print(t_exact > 3 * t_approx)               # True: sampling is much faster

core = nx.k_core(G, k=4)                    # shrink before heavy analysis
print(core.number_of_nodes() < G.number_of_nodes())   # True
print(nx.approximation.diameter(G) <= 8)    # True: 2-sweep lower bound, fast

Remember

Know the complexity class before running an algorithm on a big graph
Reduce, sample or approximate first; k= for betweenness
Switch to backends, compiled libraries or graph databases at scale

Watch out for

Starting all_simple_paths or exact betweenness on a large graph without estimating run time.

Check yourself

Exact betweenness takes 10 minutes on 50,000 nodes. Roughly how long on a similar 100,000-node graph with twice the edges?

Official docs: networkx.org/documentation/stable/reference/algorithms/approximation.html

Example

Remember

Watch out for

Check yourself

Builds on

Unlocks