Memory and runtime limits for NetworkX betweenness centrality on graphs with millions of edges

Direct answer

For a directed NetworkX graph approaching several million edges, pure-Python betweenness_centrality is generally impractical for exact full computation. Runtime is usually the first hard limit because Brandes' algorithm runs in roughly O(V*E) time; with Python constant factors, moving from hundreds of thousands to millions of edges typically shifts wall-clock time from minutes to hours or days on a single core. Memory can also bind, but it is usually the second constraint unless the graph is unusually dense or carries very heavy per-edge attributes.

Likely explanation versus confirmed facts

The algorithmic complexity is well-established: unweighted betweenness centrality uses Brandes' algorithm, and NetworkX implements it in pure Python. The dict-of-dicts storage model adds a large constant factor: each edge is represented by nested dictionaries plus an attribute dictionary. This overhead scales roughly linearly with nodes and edges, but the per-edge cost is substantial. In practice, several million edges commonly occupy multiple gigabytes, so a standard workstation can hit memory pressure before the algorithm finishes. The exact byte count depends on attribute size and Python version, so treat any single number as an estimate.

What does not help

Converting the graph with to_numpy_array builds a dense V × V matrix with O(V^2) memory. For a sparse graph with millions of edges, this usually increases memory and does not accelerate betweenness centrality; it is intended for dense linear-algebra measures. Expect a MemoryError or heavy swapping long before any speedup.

Supported ways to reduce cost without changing graph classes

1. Sampled approximation via k: nx.betweenness_centrality(G, k=50, seed=...) samples k pivot nodes and reduces time to about O(k*E). Scores remain normalized. This is the main documented in-library trade-off, but it is stochastic and seed-dependent; do not use it when exact values are required.
2. Backend dispatching: NetworkX 3.x introduced backend dispatching for many algorithms. If a compiled or GPU backend is installed and implements betweenness centrality, it may run faster without changing your Graph class. Support is backend- and version-specific; confirm in your environment.

Practical verification before committing

Because sys.getsizeof returns only the shallow size of a dict and ignores nested edge and attribute dicts, it will drastically undercount graph memory. Use a deep measurement instead:

import tracemalloc
tracemalloc.start()
# ... build or load G ...
# or: from pympler import asizeof; bytes_used = asizeof.asizeof(G)
bytes_per_edge = asizeof.asizeof(G) / G.number_of_edges()

Then time a sampled run and extrapolate:

import time, networkx as nx
t0 = time.time()
nx.betweenness_centrality(G, k=50, seed=42)
elapsed = time.time() - t0
# estimated full-runtime ≈ elapsed * (G.number_of_nodes() / 50)

Validate the linear-in-k assumption on a smaller subgraph by comparing full and sampled timings. To check backend support, attempt nx.betweenness_centrality(G, k=50, backend="") and catch NetworkXNotImplemented.

One missing diagnostic detail

Is the graph weighted? Weighted betweenness uses Dijkstra with a heap, raising per-source cost to roughly O(E + V log V) and total cost to O(V*(E + V log V)). If weights are present, the runtime wall arrives sooner and the k-sampling path becomes even more important.