Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Affiliates 
 Visitors 
 Students 
 Research 
 ICAM-LANL 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Colloquia 
 Colloquia Archive 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Colloquia 
 
 Jobs 
 Students 
 Summer Research 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
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