Distance Labelings on Random Power Law Graphs.

Huacheng Yu, Hongyang ZhangarXiv 2017 · arXiv

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:

  1. Degree-Based Ordering: Nodes are processed in decreasing order of degree. High-degree "hubs" are prioritized as they effectively cover long-range paths.
  2. 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.
  3. 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.

Theoretical bounds for landmark requirements as a function of the power law exponent beta.

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).

Comparison of space, preprocessing time, and query time between ApproximatePruning and PrunedLabeling across six real-world datasets.

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

Abstract

A {\it Distance Labeling} scheme is a data structure that can answer shortest path queries on a graph. Experiment results from several recent studies (Akiba et al.'13, Delling et al.'14) found very efficient and very accurate labeling schemes, which scale to social and information networks with tens of millions of vertices and edges. Such a finding is not expected in the worst case, since even for graphs with maximum degree $3$, it is known that any distance labeling requires $\Omega{(n^{3/2})}$ space (Gavoille et al.'03). On the other hand, social and information networks have a heavy-tailed degree distribution and small average distance, which are not captured in the worst case. In this paper, we fill in the gap between empirical and worst case results. We consider distance labeling schemes on random graph models with a power law degree distribution. For such graphs, we show that simple breadth-first-search based algorithm can find near optimal labeling schemes. The intuition behind our proof reveals that the distances between different pairs of vertices are almost independent, even for polynomially many pairs.
BibTeX
@misc{yu2017distance,
  author = {Huacheng Yu and Hongyang Zhang},
  title = {{Distance Labelings on Random Power Law Graphs.}},
  year = {2017},
  eprint = {1712.08709},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.08709},
}

Loading related content...

Figure