Multigraph limit of the dense configuration model and the preferential attachment graph

DOI10.1007/S10474-012-0217-4MaRDI QIDQ452852zbMATHOpenAlexFDO

Authors B. Ráth, L. Szakács

Publication date 18 September 2012

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

multigraphpreferential attachmentconfiguration modeldense graph limit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: The configuration model is the most natural model to generate a random multigraph with a given degree sequence. We use the notion of dense graph limits to characterize the special form of limit objects of convergent sequences of configuration models. We apply these results to calculate the limit object corresponding to the dense preferential attachment graph and the edge reconnecting model. Our main tools in doing so are (1) the relation between the theory of graph limits and that of partially exchangeable random arrays (2) an explicit construction of our random graphs that uses urn models.

Recommendations

• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Multigraph limits and exchangeability
• Asymptotic behavior and distributional limits of preferential attachment graphs
• On the dense preferential attachment graph models and their graphon induced counterpart

Cites work

• scientific article; zbMATH DE number 3719745 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• Graph limits and exchangeable random graphs
• Limits of dense graph sequences
• Limits of randomly grown graph sequences
• Moments of two-variable functions and the uniqueness of graph limits
• Multigraph limits and exchangeability
• Probability with Martingales
• Random graphons and a weak positivstellensatz for graphs
• Random graphs with a given degree sequence
• Representations for partially exchangeable arrays of random variables

Cited in

(11)

• Uniqueness of Banach space valued graphons
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
• Multigraph limits and exchangeability
• Preferential attachment processes approaching the Rado multigraph
• Higher-order fluctuations in dense random graph models
• Positivity of the virial coefficients in lattice dimer models and upper bounds on the number of matchings on graphs
• Large deviations for the degree structure in preferential attachment schemes
• On the dense preferential attachment graph models and their graphon induced counterpart
• Preferential attachment without vertex growth: emergence of the giant component
• Limits of sparse configuration models and beyond: graphexes and multigraphexes

This page was built for publication: Multigraph limit of the dense configuration model and the preferential attachment graph

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