Typical distances in ultrasmall random networks

Abstract

We show that in preferential attachment models with power-law exponent $\tau \in (2,3)$ the distance between randomly chosen vertices in the giant component is asymptotically equal to $(4+o(1))\frac{\log \log N}{-\log (\tau -2)}$, where $N$ denotes the number of nodes. This is twice the value obtained for several types of configuration models with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.

16 pages