Back to Search
Start Over
Growing random graphs with a preferential attachment structure.
- Source :
- ALEA. Latin American Journal of Probability & Mathematical Statistics; 2022, Vol. 19 Issue 1, p259-309, 51p
- Publication Year :
- 2022
-
Abstract
- The aim of this paper is to develop a method for proving almost sure convergence in the Gromov-Hausdorff-Prokhorov topology for a class of models of growing random graphs that generalises Rémy's algorithm for binary trees. We describe the obtained limits using some iterative gluing construction that generalises the famous line-breaking construction of Aldous' Brownian tree, and we characterize some of them using the self-similarity property in law that they satisfy. To do that, we develop a framework in which a metric space is constructed by gluing smaller metric spaces, called blocks, along the structure of a (possibly infinite) discrete tree. Our growing random graphs seen as metric spaces can be understood in this framework, that is, as evolving blocks glued along a growing discrete tree structure. Their scaling limit convergence can then be obtained by separately proving the almost sure convergence of every block and verifying some relative compactness property for the whole structure. For the particular models that we study, the discrete tree structure behind the construction has the distribution of an affine preferential attachment tree or a weighted recursive tree. We strongly rely on results concerning those two models and their connection, obtained in the companion paper Sénizergues (2021). [ABSTRACT FROM AUTHOR]
- Subjects :
- RANDOM graphs
STOCHASTIC convergence
METRIC spaces
ALGORITHMS
GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 19800436
- Volume :
- 19
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- ALEA. Latin American Journal of Probability & Mathematical Statistics
- Publication Type :
- Academic Journal
- Accession number :
- 159201737
- Full Text :
- https://doi.org/10.30757/ALEA.v19-11