Diameters in preferential attachment models

Abstract

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 τ\in (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 τ\in (2,3), and of order \log{t} when τ>3.

References in corpus (5)

• The phase transition in inhomogeneous random graphs
• Distances in random graphs with finite variance degrees
• A preferential attachment model with random initial degrees
• Distances in random graphs with finite mean and infinite variance degrees
• Random graphs with arbitrary i.i.d. degrees

Cited by in corpus (28)

• The anatomy of Reddit: An overview of academic research
• Random networks with sublinear preferential attachment: The giant component
• First passage percolation on random graphs with finite mean degrees
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• A generative graph model for electrical infrastructure networks
• The age-dependent random connection model
• Not all interventions are equal for the height of the second peak
• Subgraphs in preferential attachment models
• Scale-free network clustering in hyperbolic and other random graphs
• Large Communities in a scale-free network
• On the diameter of hyperbolic random graphs
• Weighted distances in scale-free preferential attachment models
• How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
• On the robustness of power-law random graphs in the finite mean, infinite variance region
• Modeling the Small-World Phenomenon with Road Networks
• Diameter of P.A. random graphs with edge-step functions
• A geometric preferential attachment model with fitness
• Distance evolutions in growing preferential attachment graphs
• Critical Percolation on Random Networks with Prescribed Degrees
• The idemetric property: when most distances are (almost) the same
• Highway Preferential Attachment Models for Geographic Routing
• Likelihood-based Inference for Random Networks with Changepoints
• Cumulative structure and path length in networks of knowledge
• Multiscale genesis of a tiny giant for percolation on scale-free random graphs
• High degree vertices in the Power of Choice model combined with Preferential Attachment
• It's a Small World for Random Surfers
• Asynchronous Majority Dynamics in Preferential Attachment Trees
• Chemical distance in geometric random graphs with long edges and scale-free degree distribution