Paper detail

Growing random graphs with a preferential attachment structure

The aim of this paper is to develop a method for proving almost sure convergence in Gromov-Hausodorff-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. In order to do that, we develop a framework in which a metric space is constructed by gluing smaller metric spaces, called \emph{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 of random trees and their connection, obtained in a companion paper.