When is a scale-free graph ultra-small?

In this paper we study typical distances in the configuration model, when the degrees have asymptotically infinite variance. We assume that the empirical degree distribution follows a power law with exponent $\tau \in (2,3)$, up to value $n^{{\beta }_n}$ for some ${\beta }_n\gg (\log n{)}^{-\gamma }$ and $\gamma \in (0,1)$. This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law distributions where the (possibly exponential) truncation happens at $n^{{\beta }_n}$. We show that the graph distance between two uniformly chosen vertices centers around $2 \log \log (n^{\beta_n}) / |\log (\tau-2)| + 1/(\beta_n(3-\tau))$, with tight fluctuations. Thus, the graph is an \emph{ultrasmall world} whenever $1\mathrm{/}{\beta }_n=o(\log \log n)$. We determine the distribution of the fluctuations around this value, in particular we prove that these are non-converging tight random variables that show $\log \log$-periodicity. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order $n^{f_n{\beta }_n}$, where $f_n\in (0,1)$ is a random variable that oscillates with $n$. The two end-segments of any shortest path have length $\log \log (n^{{\beta }_n})\mathrm{/}\mathrm{\mid }\log (\tau -2)\mathrm{\mid }$+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length $1\mathrm{/}({\beta }_n(3-\tau ))$+tight, and it contains only vertices with degree at least of order $n^{(1-f_n){\beta }_n}$, thus all the degrees on this segment are comparable to the maximal degree. Our theorems also apply when instead of truncating the degrees, we start with a configuration model and we remove every vertex with degree at least $n^{{\beta }_n}$, and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.