Finding Critical Junctions in Transportation Networks with NetworkX Betweenness Centrality

Why Betweenness Matters for Road and Rail Planning

When you look at a city’s road map, the most obvious way to spot a bottleneck is to see which streets carry the most traffic. In graph‑theory terms that traffic is represented by the *shortest paths* that travel through the network. Betweenness centrality quantifies exactly that: the proportion of all shortest paths that pass through a given node. A node with a high betweenness score is a critical connector – if it fails, many routes will be disrupted.

NetworkX’s Implementation and Performance

NetworkX implements Brandes’ algorithm, which runs in O(nm) time for unweighted graphs and in O(nm + n² log n) for weighted graphs. For a typical transportation network of a few thousand edges, the calculation completes in a few seconds on a standard laptop. The function signature is:

betweenness_centrality(G, weight=None, normalized=True)

• G – a networkx.Graph (undirected) or DiGraph (directed).
• weight – name of the edge attribute that stores the cost (e.g., travel time). If None, all edges are treated as weight 1.
• normalized – divides by \((n-1)(n-2)/2\) for undirected graphs or \((n-1)(n-2)\) for directed graphs. Set to False for small graphs to avoid division by zero.

Step‑by‑Step Example: A Mini‑Transit Network

Below is a minimal example that builds a weighted transportation graph, calculates betweenness, and visualises the top nodes.

import networkx as nx
import matplotlib.pyplot as plt

# 1. Build a weighted graph – nodes are stations, edges are routes
G = nx.Graph()
# Add nodes (stations)
G.add_nodes_from(["A", "B", "C", "D", "E", "F"])
# Add weighted edges (travel time in minutes)
edges = [
    ("A", "B", 5),
    ("A", "C", 2),
    ("B", "C", 1),
    ("B", "D", 3),
    ("C", "D", 4),
    ("C", "E", 6),
    ("D", "E", 2),
    ("D", "F", 7),
    ("E", "F", 1),
]
for u, v, w in edges:
    G.add_edge(u, v, weight=w)

# 2. Compute betweenness centrality
bet = nx.betweenness_centrality(G, weight="weight", normalized=True)

# 3. Sort nodes by centrality
sorted_bet = sorted(bet.items(), key=lambda x: x[1], reverse=True)
print("Top nodes by betweenness:")
for node, score in sorted_bet[:3]:
    print(f"{node}: {score:.4f}")

# 4. Visualise – highlight top 3 nodes
pos = nx.spring_layout(G, seed=42)
node_colors = ["red" if node in dict(sorted_bet[:3]) else "skyblue" for node in G.nodes()]

nx.draw(G, pos, with_labels=True, node_color=node_colors, node_size=800, edge_color="gray")
# Draw edge weights
edge_labels = {(u, v): d["weight"] for u, v, d in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("Betweenness Centrality – Highlighted Nodes")
plt.show()

Running this script will produce a plot where the three most critical stations (e.g., B, D, and E) are colored red. The printed scores confirm that the algorithm returned floating‑point values between 0 and 1.

Trade‑offs and Caveats

• Complexity vs. Size: For graphs with tens of thousands of edges, the full algorithm can consume several gigabytes of RAM because it stores all shortest‑path counts. NetworkX offers betweenness_centrality_subset to compute centrality for a subset of nodes or an approximate method that samples pairs of nodes.
• Equal‑Length Paths: In dense transportation grids, many different routes can have identical length. The algorithm will split the centrality contribution evenly among them, potentially diluting the signal for truly critical nodes.
• Weight Attribute Consistency: All edges must carry a numeric weight when you pass weight="weight". Missing or non‑numeric values raise a NetworkXError and abort the calculation.
• Normalization in Small or Directed Graphs: The default normalization divides by a factor that becomes zero when n < 3 or for directed graphs with very few nodes. Set normalized=False to avoid division by zero.

Actionable Takeaway

Use betweenness centrality as the first pass to flag potential bottlenecks in a transportation network. After identifying high‑centrality nodes:

• Validate with real traffic data or simulation to confirm that these nodes actually experience heavy load.
• Prioritise upgrades (e.g., adding lanes, new routes, or redundancy) on the top 10–15% of nodes by centrality.
• Monitor the impact of interventions by re‑running the calculation on the updated graph.

Because NetworkX returns a plain dictionary, you can feed the scores directly into a GIS system, a machine‑learning pipeline, or a custom dashboard. The key is to treat betweenness as a heuristic that highlights where the network is most vulnerable, not as an absolute measure of risk.