Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Student Program 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Wednesday, August 05, 2009
4:00 PM - 5:00 PM
CNLS Conference Room (TA-3, Bldg 1690)


Approximate shortest path and distance queries in power-law graphs

Christian Sommer
CCS-3 and Tokyo University

Distance oracles have been investigated both for general graphs as well as for various graph classes. Many practical networks seem to obey a power law, and, fortunately, general schemes perform quite well for power-law graphs too. We adapt the approximate distance oracle by Thorup and Zwick (J. ACM 2005) to optimize it for unweighted, undirected power law graphs.

We provide a rigorous probabilistic analysis of the average-case performance of our deterministic algorithm based on the theory of random power law graphs with a fixed expected degree sequence by Aiello, Chung, and Lu.

Let $\gamma>\frac{\tau-2}{2\tau-3}$, where $\tau\in(2,3)$ is the power law exponent. We prove that for stretch 3, instead of an oracle of size~$O(n^{3/2})$, expected space~$O(n^{1+\gamma})$ is sufficient and that the oracle can be constructed in expected time~$O(n^{1+\gamma}\log n)$. Our distance oracle is the first one optimized for power-law graphs with a theoretical analysis. The results can be extended to obtain a compact routing scheme. Joint work with Wei Chen, Shanghua Teng, and Yajun Wang