Diameters in Preferential Attachment Models

In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider affine PA-models. There is a substantial amount of literature proving that, quite generally, PA-graphs possess power-law degree sequences with a power-law exponent τ >2. We prove that the diameter of the PA-model is bounded above by a constant times log t , where t is the size of the graph. When the power-law exponent τ exceeds 3, then we prove that log t is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for τ >3, distances are of the order log t . For τ ∈(2,3), we improve the upper bound to a constant times log log t , and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order log log t . These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order log log t when τ ∈(2,3), and of order log t when τ >3.