Lab Home | Phone | Search
 Current Affiliates Visitors Students
 Colloquia Colloquia Archive Seminars Postdoc Seminars Archive Quantum Lunch CMS Colloquia Q-Mat Seminars Q-Mat Seminars Archive Archive

 Description Past Visitors

Wednesday, August 05, 2009
4:00 PM - 5:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Seminar

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