Weighted distances in scale-free preferential attachment models
arXiv:1907.01907 · doi:10.1002/rsa.20947
Abstract
We study three preferential attachment models where the parameters are such that the asymptotic degree distribution has infinite variance. Every edge is equipped with a non-negative i.i.d. weight. We study the weighted distance between two vertices chosen uniformly at random, the typical weighted distance, and the number of edges on this path, the typical hopcount. We prove that there are precisely two universality classes of weight distributions, called the explosive and conservative class. In the explosive class, we show that the typical weighted distance converges in distribution to the sum of two i.i.d. finite random variables. In the conservative class, we prove that the typical weighted distance tends to infinity, and we give an explicit expression for the main growth term, as well as for the hopcount. Under a mild assumption on the weight distribution the fluctuations around the main term are tight.
arXiv commentRevised version, results are unchanged. 30 pages, 1 figure. To appear in Random Structures and Algorithms
References in corpus (17)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- The diameter of the world wide web
- Diameters in preferential attachment models
- Distances in random graphs with finite variance degrees
- Spatial preferential attachment networks: Power laws and clustering coefficients
- Asymptotic behavior and distributional limits of preferential attachment graphs
- 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
- The age-dependent random connection model
- On explosions in heavy-tailed branching random walks
- The front of the epidemic spread and first passage percolation
- Subgraphs in preferential attachment models
- Weighted distances in scale-free configuration models
- Local neighbourhoods for first passage percolation on the configuration model