Growing random graphs with a preferential attachment structure
From MaRDI portal
Abstract: 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'emy'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.
Recommendations
- Scaling limits and influence of the seed graph in preferential attachment trees
- Growth of preferential attachment random graphs via continuous-time branching processes
- Scaling limits for some random trees constructed inhomogeneously
- Scaling limits of k-ary growing trees
- Limits of randomly grown graph sequences
Cites work
- A course in metric geometry
- A line-breaking construction of the stable trees
- A new family of Markov branching trees: the alpha-gamma model
- A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
- Branching processes in Lévy processes: The exploration process
- Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
- Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
- Extensions of Measures and the Von Neumann Selection Theorem
- Geometry of weighted recursive and affine preferential attachment trees
- scientific article; zbMATH DE number 6683511 (Why is no real title available?)
- scientific article; zbMATH DE number 739280 (Why is no real title available?)
- scientific article; zbMATH DE number 1859371 (Why is no real title available?)
- Limit theorems for triangular urn schemes
- On the exponential functional of Markov Additive Processes, and applications to multi-type self-similar fragmentation processes and trees
- On the geometry of Urysohn's universal metric space
- Probabilistic and fractal aspects of Lévy trees
- Random gluing of metric spaces
- Random real trees
- Random recursive trees and preferential attachment trees are random split trees
- Random stable looptrees
- Rayleigh processes, real trees, and root growth with re-grafting
- Scaling limits and influence of the seed graph in preferential attachment trees
- Scaling limits for some random trees constructed inhomogeneously
- Scaling limits of k-ary growing trees
- Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
- Scaling limits of multi-type Markov branching trees
- Scaling limits of random trees and random graphs
- Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
- Separability and completeness for the Wasserstein distance
- Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
- The continuum random tree. I
- The distribution of the maximum Brownian excursion
- The genealogy of self-similar fragmentations with negative index as a continuum random tree
- The stable trees are nested
- The vertex-cut-tree of Galton-Watson trees converging to a stable tree
- Urysohn universal space, its development and Hausdorff's approach
Cited in
(13)- Preferential attachment in randomly grown networks
- On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
- Sublinear but never superlinear preferential attachment by local network growth
- Entropy and Hausdorff dimension in random growing trees
- Scaling limits and influence of the seed graph in preferential attachment trees
- scientific article; zbMATH DE number 6311840 (Why is no real title available?)
- Community Recovery in a Preferential Attachment Graph
- Stable graphs: distributions and line-breaking construction
- A binary embedding of the stable line-breaking construction
- Decorated stable trees
- Depths in random recursive metric spaces
- The scaling limit of the root component in the wired minimal spanning forest of the Poisson weighted infinite tree
- Growth of preferential attachment random graphs via continuous-time branching processes
This page was built for publication: Growing random graphs with a preferential attachment structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026477)
