When Edge Importance Disagrees: Resistance-Ranked versus Betweenness Pruning on Urban Road Networks

Abstract

Sparsifying large road-network graphs by removing a fraction of their edges is a common way to reduce storage and accelerate spatial queries, but the choice of which edges to remove can quietly degrade the network that remains. We compare three edge-importance criteria, uniform random removal, low edge-betweenness removal, and low-effective-resistance removal, on 27 urban road networks drawn from OpenStreetMap. At edge-removal ratios from five to thirty percent we evaluate each criterion along three complementary axes: length-weighted routing utility, the retention of normalized algebraic connectivity on the largest connected component, and the fraction of an arterial backbone, taken from OpenStreetMap road classes, that each criterion destroys. The criteria disagree, and the three axes disagree about effective resistance itself. Deleting the edges with the lowest exact effective resistance preserves routing better than random deletion at every ratio, yet removes the arterial backbone faster than random deletion from five percent onward and holds an early connectivity advantage that fades to statistical parity by twenty-five percent. Betweenness removal is consistently the best of the three on all three axes, at every removal ratio. Deterministic deletion of low-resistance edges, which is distinct from the randomized, reweighted spectral sparsifier, is therefore not a safe proxy for routing importance when compressing real road networks, and a routing-oriented criterion is the more dependable choice.