Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics

DOI10.1002/RSA.20422MaRDI QIDQ3168499zbMATH OpenOpenAlexFDO

Authors Balázs Ráth

Publication date 31 October 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

dense graph limitsmultigraphspreferential attachment

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the notion of convergence of dense graph sequences, defined by Lovasz and Szegedy in arXiv:math/0408173. We investigate how the limit object evolves under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limit object from its initial state up to the stationary state, which is described in the companion paper arXiv:1106.2058. In our proofs we use the theory of exchangeable arrays, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits subaging.

Recommendations

• Multigraph limit of the dense configuration model and the preferential attachment graph
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• Preferential attachment processes approaching the Rado multigraph
• Asymptotic degree distribution in preferential attachment graph models with multiple type edges
• On a random graph evolving by degrees

Cites work

• A note on weak convergence of random step processes
• A two-time-scale phenomenon in a fragmentation-coagulation process
• Graph limits and exchangeable random graphs
• scientific article; zbMATH DE number 3522951 (Why is no real title available?)
• Interest rate models: an introduction
• 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

Cited in

(11)

• Mean-field and graph limits for collective dynamics models with time-varying weights
• Higher-order fluctuations in dense random graph models
• A time-invariant random graph with splitting events
• Preferential attachment without vertex growth: emergence of the giant component
• Graphon-valued stochastic processes from population genetics
• Limit of a nonpreferential attachment multitype network model
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• Diffusion approximation of critical controlled multi-type branching processes
• Graphon-valued processes with vertex-level fluctuations

This page was built for publication: Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics

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