Diameters in preferential attachment models
From MaRDI portal
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 au>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 au 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 au>3, distances are of the order log{t}. For auin (2,3), we improve the upper bound to a constant times loglog{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 loglog{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 loglog{t} when auin (2,3), and of order log{t} when au>3.
Recommendations
- Core size and densification in preferential attachment networks
- Distances and large deviations in the spatial preferential attachment model
- A preferential attachment model with random initial degrees
- The diameter of the directed configuration model
- Weighted distances in scale-free preferential attachment models
- Classes of preferential attachment and triangle preferential attachment models with power-law spectra
- On a preferential attachment and generalized Pólya's urn model
Cites work
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 3153525 (Why is no real title available?)
- scientific article; zbMATH DE number 2038750 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 1792101 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- A Phase Transition for the Diameter of the Configuration Model
- A general model of web graphs
- A preferential attachment model with random initial degrees
- Complex graphs and networks
- Connectivity Transitions in Networks with Super-Linear Preferential Attachment
- Convergence properties of the degree distribution of some growing network models
- Coupling Online and Offline Analyses for Random Power Law Graphs
- Coupling Scale-Free and Classical Random Graphs
- Directed scale-free graphs
- Distance in random graphs with infinite mean degrees
- Distances in random graphs with finite mean and infinite variance degrees
- Distances in random graphs with finite variance degrees
- Emergence of Scaling in Random Networks
- Note on the heights of random recursive trees and random m‐ary search trees
- On a conditionally Poissonian graph process
- On random trees
- Random graph dynamics
- Random graphs and complex networks. Volume 1
- Random graphs.
- Random trees and general branching processes
- Robustness and Vulnerability of Scale-Free Random Graphs
- Statistical mechanics of complex networks
- The Average Distance in a Random Graph with Given Expected Degrees
- The Maximum Degree of the Barabási–Albert Random Tree
- The Structure and Function of Complex Networks
- The average distances in random graphs with given expected degrees
- The degree sequence of a scale-free random graph process
- The degree sequences and spectra of scale-free random graphs
- The diameter of a scale-free random graph
- The diameter of sparse random graphs
- The phase transition in inhomogeneous random graphs
- Universality for the distance in finite variance random graphs
Cited in
(33)- MATRIX-MFO tandem workshop: Stochastic reinforcement processes and graphs. Abstracts from the MATRIX-MFO tandem workshop held March 5--10, 2023
- The idemetric property: when most distances are (almost) the same
- When is a scale-free graph ultra-small?
- Subgraphs in preferential attachment models
- A preferential attachment model with random initial degrees
- Distances in scale free networks at criticality
- Not all interventions are equal for the height of the second peak
- The age-dependent random connection model
- Typical distances in a geometric model for complex networks
- Typical distances in ultrasmall random networks
- Justifying the small-world phenomenon via random recursive trees
- Local weak convergence for PageRank
- Chemical distance in geometric random graphs with long edges and scale-free degree distribution
- Diameter in ultra-small scale-free random graphs
- A Phase Transition for the Diameter of the Configuration Model
- Highway preferential attachment models for geographic routing
- First passage percolation on random graphs with finite mean degrees
- Distance evolutions in growing preferential attachment graphs
- Scale-free percolation
- Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
- A Theory of Network Security: Principles of Natural Selection and Combinatorics
- Random networks with sublinear preferential attachment: the giant component
- The diameter of a scale-free random graph
- Diameter of P.A. random graphs with edge-step functions
- It's a small world for random surfers
- Scale-free network clustering in hyperbolic and other random graphs
- On the diameter of hyperbolic random graphs
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Metastability for the contact process on the preferential attachment graph
- Large communities in a scale-free network
- First-Order Model-Checking in Random Graphs and Complex Networks
- On the diameter of hyperbolic random graphs
- Fitting the linear preferential attachment model
This page was built for publication: Diameters in preferential attachment models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q967660)
