A Compact Routing Scheme and Approximate Distance Oracle for Power-Law Graphs

Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang
ACM Transactions on Algorithms, Volume 9, Issue 1 (pp. 4:1-26), 2012

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick (SPAA 2001) to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu (STOC 2000). Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme.

Let \(n\) denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch-5 handshaking step (similar to DNS lookup in TCP/IP), routes messages along stretch-3 paths. We prove that, instead of routing tables with \(\widetilde{O}(n^{1/2})\) bits (suppressing factors logarithmic in \(n\)) as in the general scheme by Thorup and Zwick, expected sizes of \(\widetilde{O}(n^\gamma)\) bits are sufficient, and that all the routing tables can be constructed at once in expected time \(\widetilde{O}(n^{1+\gamma})\), with \(\gamma = \frac{\tau - 2}{2 \tau - 3} + \epsilon \), where \(\tau\) is the power-law exponent (between 2 and 3) and \(\epsilon \gt 0\) (which implies \(\epsilon \lt \gamma \lt 1/3 + \epsilon\)). Both bounds also hold with probability at least \(1-1/n\) (independent of \(\epsilon\)). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step. The scheme uses addresses and message headers with \(O(\log n \log \log n)\) bits, with probability at least \(1-o(1)\). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs.

With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick (STOC 2001, J.ACM 2004) for stretch 3 and we obtain a new upper bound of expected \(\widetilde{O}(n^{1+\gamma})\) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5-approximate distance queries in time \(\widetilde{O}(n^{1/4 + \epsilon})\) (similar to \(\gamma\), the exponent actually depends on \(\tau\) and lies between \(\epsilon\) and \(1/4 + \epsilon\)).

@article{CSTW12,
 author  = {Wei Chen 
            and Christian Sommer 
            and Shang-Hua Teng 
            and Yajun Wang},
 title   = {A Compact Routing Scheme
            and Approximate Distance Oracle 
            for Power-Law Graphs},
 journal = {ACM Transactions on Algorithms},
 year    = {2012},
 volume  = {9},
 number  = {1},
 pages   = {4:1--26},
 url     = {http://dx.doi.org/10.1145/2390176.2390180},
 doi     = {10.1145/2390176.2390180},
 note    = {Announced at DISC 2009}
}

Official version
Local version (411.7 KB)

Informal outline: Compact routing schemes and distance oracles have been investigated both for general graphs as well as for various graph classes. Many real-world networks seem to have degree sequences that obey a power law, and, fortunately, general schemes perform quite well for these so-called power-law graphs too. In this work, we prove why, using a rigorous average case analysis for random power-law graphs.

Home → Publications → A Compact Routing Scheme and Approximate Distance Oracle for Power-Law Graphs