Abstract
A Distance Labeling scheme is a data structure that can answer shortest path queries on a graph. Recent empirical studies have found highly efficient and accurate labeling schemes that scale to networks with tens of millions of vertices, a result not expected in the worst case where space requirements are $\Omega(n^{3/2})$. This paper bridges the gap between empirical success and worst-case theory by analyzing distance labeling schemes on random graph models with power-law degree distributions. We demonstrate that a simple breadth-first-search based algorithm can find near-optimal labeling schemes, revealing that distances between vertex pairs are almost independent in these models.
Introduction: The Gap Between Theory and Practice
Finding the shortest path between nodes in massive graphs, such as social networks or the web, is a fundamental computational challenge. Standard algorithms like Breadth-First Search (BFS) are too slow for real-time queries on graphs with millions of vertices. To address this, researchers utilize distance sketches (or landmark-based labelings), where each node stores distances to a small set of "landmark" nodes. A query for the distance between nodes $u$ and $v$ is then answered by finding a common landmark $z$ that minimizes $dist(u, z) + dist(z, v)$.
Historically, a significant gap has existed between theory and practice. Worst-case analysis suggests that exact distance labeling for general graphs requires prohibitive space. However, empirical algorithms like "Pruned Landmark Labeling" perform exceptionally well on real-world social networks. This research explains this discrepancy by analyzing these sketches on random power-law graphs, which better reflect the structure of real-world networks.
The ApproximatePruning Algorithm
The authors introduce ApproximatePruning, a hybrid preprocessing algorithm that optimizes landmark selection through three key strategies:
- Degree-Based Ordering: Nodes are processed in decreasing order of degree. High-degree "hubs" are prioritized as they effectively cover long-range paths.
- Global Pruned BFS: For high-degree landmarks, a full BFS is performed with pruning. If a previously processed landmark already explains the shortest path to a node, the current search branch is terminated.
- Local Ball Growing: For the majority of lower-degree nodes, the algorithm restricts searches to a "local ball" of radius $l$, capturing essential local landmarks without the overhead of a global traversal.
Theoretical Analysis and Optimality
The study provides rigorous bounds using the Chung-Lu model for random graphs with a power-law exponent $\beta$. A key insight is the "Power of Hubs": in these networks, a tiny fraction of nodes covers the vast majority of shortest paths.
As shown in Figure 1, the required number of landmarks varies significantly with the exponent $\beta$. For $\beta > 3$, nodes only need $\tilde{O}(\sqrt{n})$ landmarks for exact distances. In the $2 < \beta < 3$ regime, the authors establish a spectrum of bounds based on the allowed "stretch" (error), demonstrating that their space complexity is near-optimal for these models.
Experimental Evaluation
The algorithm was tested on six large-scale networks from the SNAP collection, including social networks (Twitter, Youtube), web graphs (Stanford, Google, BerkStan), and collaboration networks (DBLP).
Key Results
- Efficiency and Speed: As illustrated in Figure 4, ApproximatePruning consistently outperforms the standard Pruned Labeling algorithm. It achieves a 1.5–2.5x reduction in stored landmarks and a 2–15x speedup in preprocessing time. For instance, preprocessing the Google web graph was reduced from 100 minutes to under 10 minutes.
- Accuracy: Despite its approximate nature, the relative average stretch was less than 1% across all datasets, often returning exact distances.
- Benchmarking: The method significantly outperformed theoretical benchmarks like Thorup-Zwick 3-approximation and Das Sarma et al. sketches in both space efficiency and accuracy.
Conclusion and Future Directions
This work provides the first strong theoretical guarantees for landmark-based distance sketches on random power-law graphs. While the analysis currently focuses on the Chung-Lu model, future work aims to extend these results to Preferential Attachment models and directed graphs. Additionally, the authors suggest exploring transportation networks, which present different structural challenges like higher diameters and lower degree variance.
Summary updated