When is a scale-free graph ultra-small?

Abstract

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/{\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})/|\log (\tau -2)|$+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length $1/({\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.

36 pages, 1 figure

References in corpus (2)

• Power-law distributions in empirical data
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models

Cited by in corpus (4)

• Linking the mixing times of random walks on static and dynamic random graphs
• Learning the mechanisms of network growth
• Degree-penalized contact processes
• First passage percolation on Erdős-Rényi graphs with general weights