Preferential attachment processes approaching the Rado multigraph

DOI10.26493/2590-9770.1297.F97zbMATH Open1498.05239arXiv1502.05618OpenAlexW3185480625MaRDI QIDQ5045256FDOQ5045256

Authors: Richard Elwes 

Publication date: 4 November 2022

Published in: The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

Abstract: We consider a preferential attachment process in which a multigraph is built one node at a time. The number of edges added at stage $t$, emanating from the new node, is given by some prescribed function $f(t)$, generalising a model considered by Kleinberg and Kleinberg in 2005 where $f$ was presumed constant. We show that if $f(t)$ is asymptotically bounded above and below by linear functions in $t$, then with probability $1$ the infinite limit of the process will be isomorphic to the emph{Rado multigraph}. This structure is the natural multigraph analogue of the Rado graph, which we introduce here.

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

Recommendations

• A preferential attachment process approaching the Rado graph
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Growth of preferential attachment random graphs via continuous-time branching processes
• Asymptotic degree distribution in preferential attachment graph models with multiple type edges

zbMATH Keywords

random graphsmultigraphspreferential attachmentRado graph

Mathematics Subject Classification ID

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

Cites Work

• Large networks and graph limits
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Probability with Martingales
• Title not available (Why is that?)
• The strange logic of random graphs
• Random graphs.
• The random graph
• Functions of a Complex Variable: Theory and Technique
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Infinite Limits and Adjacency Properties of a Generalized Copying Model
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• A preferential attachment process approaching the Rado graph
• Evolving Shelah‐Spencer graphs

Cited In (4)

• A preferential attachment process approaching the Rado graph
• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
• Evolving Shelah‐Spencer graphs
• On the dense preferential attachment graph models and their graphon induced counterpart

This page was built for publication: Preferential attachment processes approaching the Rado multigraph

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