Abstract
This paper bridges the gap between the empirical success of "pruned labeling" algorithms and theoretical graph theory. We introduce ApproximatePruning, a hybrid distance sketch algorithm that combines global landmarks with local search. By leveraging high-degree nodes as hubs and local balls for short-range connectivity, the algorithm achieves near-optimal space complexity on random power-law graphs. Experimental results on real-world networks demonstrate 2-15x faster preprocessing and significant storage savings compared to state-of-the-art methods, while maintaining high accuracy with relative average stretch under 1%.
Introduction
In the era of massive social and information networks, computing shortest paths between nodes must occur in milliseconds. Standard algorithms like BFS or Dijkstra are too slow for real-time queries. Landmark-based labeling, which precomputes distances to a small set of landmarks, is a common solution but often faces a "Space-Accuracy-Time" trilemma. Exact methods require excessive storage, while theoretically grounded approximate methods often perform poorly in practice. This research provides a rigorous theoretical foundation for why pruning-based heuristics work exceptionally well on real-world graphs with power-law degree distributions.
Methods: The ApproximatePruning Algorithm
The proposed ApproximatePruning algorithm is a strategic evolution of the Pruned Labeling algorithm. It operates in two main phases:
- Global Pruning: The algorithm selects a small set of high-degree "global landmarks" and performs a full BFS from these nodes. A pruning step ensures that if a path is already covered by a previously processed landmark, that branch of the BFS is terminated.
- Local Ball Growing: For the remaining nodes, the algorithm grows a "local ball" only up to a specific radius $l$, rather than a full BFS.
This hybrid approach utilizes high-degree nodes as efficient "hubs" for long distances while relying on local balls for short-range connectivity, avoiding the massive overhead of exhaustive searches from every node. The theoretical analysis uses the Chung-Lu model to mimic real-world power-law distributions, proving that for certain power-law exponents, the algorithm reaches fundamental lower bounds of storage.
Experimental Evaluation
The algorithm was evaluated on six diverse real-world datasets from the SNAP collection, including social networks (Twitter, Youtube), web graphs (Stanford, Google, BerkStan), and collaboration networks (DBLP).
As shown in the space comparisons, ApproximatePruning reduced landmark storage by 1.5x to 2.5x compared to state-of-the-art Pruned Labeling. Furthermore, the hybrid approach proved significantly lighter in terms of computational overhead during the setup phase.
Despite being an approximate method, the relative average stretch remained below 1% across all datasets. In many instances, the median additive stretch was zero, indicating exact distance retrieval for the majority of queries. It consistently outperformed classical benchmarks like the Thorup-Zwick 3-approximate oracle in both space and accuracy.
Conclusion
This work demonstrates that pruning is not just a heuristic but a theoretically sound method for reaching fundamental storage lower bounds in power-law graphs. While highly effective for small-world networks, future research will focus on extending these proofs to preferential attachment models, adapting sketches for dynamic graphs, and evaluating performance on high-diameter transportation networks where hub-based logic may differ.
Summary updated