Stable graphs: distributions and line-breaking construction

DOI10.5802/AHL.138MaRDI QIDQ6159721zbMATH OpenFDO

Authors Christina Goldschmidt, Bénédicte Haas, Delphin Sénizergues

Publication date 20 June 2023

Published in Annales Henri Lebesgue (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.06940

zbMATH Keywords

configuration modelrandom graphs with given degree sequencescaling limitstable treesurn models

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For $alphain(1,2]$, the $alpha$-stable graph arises as the universal scaling limit of critical random graphs with i.i.d. degrees having a given $alpha$-dependent power-law tail behavior. It consists of a sequence of compact measured metric spaces (the limiting connected components), each of which is tree-like, in the sense that it consists of an $mathbbR$-tree with finitely many vertex-identifications (which create cycles). Indeed, given their masses and numbers of vertex-identifications, these components are independent and may be constructed from a spanning $mathbbR$-tree, which is a biased version of the $alpha$-stable tree, with a certain number of leaves glued along their paths to the root. In this paper we investigate the geometric properties of such a component with given mass and number of vertex-identifications. We (1) obtain the distribution of its kernel and more generally of its discrete finite-dimensional marginals; we will observe that these distributions are related to the distributions of some configuration models (2) determine the distribution of the $alpha$-stable graph as a collection of $alpha$-stable trees glued onto its kernel and (3) present a line-breaking construction, in the same spirit as Aldous' line-breaking construction of the Brownian continuum random tree.

Recommendations

• ON STABLE GRAPHS
• scientific article; zbMATH DE number 4063144
• Stability of graphs
• A note on stability of graphs
• Stable properties of graphs
• scientific article; zbMATH DE number 3961652
• On the structure of -stable graphs
• scientific article; zbMATH DE number 4075101
• On strongly stable graphs and some consequences for partitionable graphs
• On cohesion stable graphs

Cites work

• A course in metric geometry
• A critical point for random graphs with a given degree sequence
• A limit theorem for the contour process of conditioned Galton-Watson trees
• A line-breaking construction of the stable trees
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Branching processes in Lévy processes: The exploration process
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Contact processes on random graphs with power law degree distributions have critical value 0
• Continuum limit of critical inhomogeneous random graphs
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Critical behavior in inhomogeneous random graphs
• Critical percolation on random regular graphs
• Critical random graphs: limiting constructions and distributional properties
• Critical window for the configuration model: finite third moment degrees
• Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.
• Geometry of the minimal spanning tree of a random 3-regular graph
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Geometry of weighted recursive and affine preferential attachment trees
• Growing random graphs with a preferential attachment structure
• Heavy-tailed configuration models at criticality
• scientific article; zbMATH DE number 6683511 (Why is no real title available?)
• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• scientific article; zbMATH DE number 6850349 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• Limit theorems for triangular urn schemes
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
• Normalized excursion, meander and bridge for stable Lévy processes
• Novel scaling limits for critical inhomogeneous random graphs
• On the re-rooting invariance property of Lévy trees
• Probabilistic and fractal aspects of Lévy trees
• Random gluing of metric spaces
• Random graphs and complex networks. Volume 1
• Random stable looptrees
• Random trees constructed by aggregation
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• Scaling limits for some random trees constructed inhomogeneously
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
• Some problems in the enumeration of labelled graphs
• Spinal partitions and invariance under re-rooting of continuum random trees
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Tessellations of random maps of arbitrary genus
• The asymptotic number of labeled graphs with given degree sequences
• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• The birth of the giant component
• The component sizes of a critical random graph with given degree sequence
• The continuum limit of critical random graphs
• The continuum random tree. I
• The entrance boundary of the multiplicative coalescent
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• The phase transition in the configuration model
• The scaling limit of the minimum spanning tree of the complete graph
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• The stable trees are nested
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree
• Universality for critical heavy-tailed network models: metric structure of maximal components

Cited in

(10)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Universality for critical heavy-tailed network models: metric structure of maximal components
• A line-breaking construction of the stable trees
• A binary embedding of the stable line-breaking construction
• Stable Poisson graphs in one dimension
• Random walks on decorated Galton-Watson trees
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• Epidemics on critical random graphs with heavy-tailed degree distribution
• Scaling limits and universality: critical percolation on weighted graphs converging to an L^3 graphon
• The scaling limit of the root component in the wired minimal spanning forest of the Poisson weighted infinite tree

This page was built for publication: Stable graphs: distributions and line-breaking construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159721)