A preferential attachment process approaching the Rado graph

DOI10.1017/S0013091519000336MaRDI QIDQ4961139zbMATH OpenFDO

Authors Richard Elwes

Publication date 22 April 2020

Published in Proceedings of the Edinburgh Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Rényi graphpreferential attachmentRado graphscale-free network

Mathematics Subject Classification ID

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

Abstract: We consider a simple Preferential Attachment graph process, which begins with a finite graph, and in which a new $(t+1)$st vertex is added at each subsequent time step $t$, and connected to each previous vertex $uleqt$ with probability $frac{d}_u(t)t$ where $d_u(t)$ is the degree of $u$ at time $t$. We analyse the graph obtained as the infinite limit of this process, and show that so long as the initial finite graph is neither edgeless nor complete, with probability 1 the outcome will be a copy of the Rado graph augmented with a finite number of either isolated or universal vertices.

Recommendations

• Preferential attachment processes approaching the Rado multigraph
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Preferential attachment without vertex growth: emergence of the giant component
• A preferential attachment model with random initial degrees
• Growth of preferential attachment random graphs via continuous-time branching processes

Cites work

• Bernard Friedman's Urn
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Emergence of Scaling in Random Networks
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Preferential attachment processes approaching the Rado multigraph
• Random graphs.
• Random networks with sublinear preferential attachment: degree evolutions
• Random networks with sublinear preferential attachment: the giant component
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The random graph

Cited in

(6)

• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Preferential attachment processes approaching the Rado multigraph
• Growth of common friends in a preferential attachment model
• On the dense preferential attachment graph models and their graphon induced counterpart
• A random walk on the Rado graph

This page was built for publication: A preferential attachment process approaching the Rado graph

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