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