Logarithmic typical distances in preferential attachment models

Abstract

We prove that the typical distances in a preferential attachment model with out-degree $m\ge 2$ and strictly positive fitness parameter are close to ${\log }_{\hat{I}}½n$, where $\hat{I}½$ is the exponential growth parameter of the local limit of the preferential attachment model. The proof relies on a path-counting technique, the first- and second-moment methods, as well as a novel proof of the convergence of the spectral radius of the offspring operator under a certain truncation.

70 pages, 4 figures