HierX: Fast Multi-Scale Distance-Decay Interaction on Million-Node Networks
Abstract
Many models across the sciences require global distance-decay interactions on large sparse networks. Gravity models, accessibility measures, spatial economic models, and network influence processes all evaluate distance-weighted potential fields: each location accumulates contributions from every other location, weighted by a decaying function of the shortest-path travel cost between them. Computed directly, such aggregate fields require the dense matrix of all pairwise network costs, which scales quadratically in time and memory. Common approximations either discard long-range contributions or fail when interaction is governed by network distances rather than geometric proximity. We introduce HierX, a hierarchical sparse-plus-correction operator for distance-decay potential fields on networks. HierX constructs multi-scale representative layers with explicit correction terms ensuring each location pair contributes exactly once at the finest available resolution. Under bounded-growth assumptions common in spatially embedded networks, applying HierX scales as O(n log n). Systematic benchmarks confirm quasi-linear scaling to 100,000 nodes. In head-to-head comparison with distance cutoff truncation and Nystrom low-rank approximation on 25,000-zone networks, HierX achieves 5-9% RMSE at a fraction of the computational work; Nystrom degrades severely on steep decay kernels. Case studies compute population-weighted accessibility on the 2.58-million-node Great Britain driving network and the 1.77-million-node London pedestrian network: a one-time hierarchy construction (~1 hour) yields a compact reusable operator that then evaluates each national-scale accessibility field in under one second (~700 ms for Great Britain, ~150 ms for London). Open-source code and worked examples are provided.
Versions
Related
- Exponential speedup of polarization stabilization for long distance DWDM quantum networks
- High-precision fault inception time detection in active distribution networks using Euclidean distance and Gaussian filtering
- Transverse Numerical Approach Combining Fluid-Structure Interaction and Model Reduction Methods of a Modular Thermal Energy Storage System to Improve the Energy Efficiency of District Heating Networks
- Incorporating deep neural networks into lepton-nucleus interaction modeling
- Freezing-Induced Interaction Engineering in Fixed-Frequency Transmon Networks
BibTeX
@misc{hellervik2026hierx,
title = {{HierX: Fast Multi-Scale Distance-Decay Interaction on Million-Node Networks}},
author = {Alexander Hellervik and Joakim Bohlin and Claes Andersson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08676},
eprint = {2609.08676},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08676},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - HierX: Fast Multi-Scale Distance-Decay Interaction on Million-Node Networks
AU - Alexander Hellervik
AU - Joakim Bohlin
AU - Claes Andersson
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08676
UR - https://arxiv.org/abs/2609.08676
AB - Many models across the sciences require global distance-decay interactions on large sparse networks. Gravity models, accessibility measures, spatial economic models, and network influence processes all evaluate distance-weighted potential fields: each location accumulates contributions from every other location, weighted by a decaying function of the shortest-path travel cost between them. Computed directly, such aggregate fields require the dense matrix of all pairwise network costs, which scales quadratically in time and memory. Common approximations either discard long-range contributions or fail when interaction is governed by network distances rather than geometric proximity. We introduce HierX, a hierarchical sparse-plus-correction operator for distance-decay potential fields on networks. HierX constructs multi-scale representative layers with explicit correction terms ensuring each location pair contributes exactly once at the finest available resolution. Under bounded-growth assumptions common in spatially embedded networks, applying HierX scales as O(n log n). Systematic benchmarks confirm quasi-linear scaling to 100,000 nodes. In head-to-head comparison with distance cutoff truncation and Nystrom low-rank approximation on 25,000-zone networks, HierX achieves 5-9% RMSE at a fraction of the computational work; Nystrom degrades severely on steep decay kernels. Case studies compute population-weighted accessibility on the 2.58-million-node Great Britain driving network and the 1.77-million-node London pedestrian network: a one-time hierarchy construction (~1 hour) yields a compact reusable operator that then evaluates each national-scale accessibility field in under one second (~700 ms for Great Britain, ~150 ms for London). Open-source code and worked examples are provided.
ER -