Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-07T04:35:52.119Z Has data issue: false hasContentIssue false
  • English
  • Français

A preferential attachment process approaching the Rado graph

Part of: Graph theory

Published online by Cambridge University Press:  27 February 2020

Richard Elwes
Richard Elwes*
Affiliation:
School of Mathematics, University of Leeds, UK (r.h.elwes@leeds.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 that is connected to each previous vertex u ≤ t with probability du(t)/t, where du(t) is the degree of u at time t. We analyse the graph obtained as the infinite limit of this process, and we show that, as 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.

Keywords

preferential attachmentRado graphscale-free networkErdős–Rényi graph

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C63: Infinite graphs
Type
Research Article
Information
Proceedings of the Edinburgh Mathematical Society , Volume 63 , Issue 2 , May 2020 , pp. 443 - 455
Copyright
Copyright © The Author(s), 2020. Published by Cambridge University Press

References

1.Barabási, A.-L. and Albert, R., Emergence of scaling in random networks, Science 286(5439) (1999), 509–512.CrossRefGoogle ScholarPubMed
2.Bollobás, B., Random graphs, 2nd edn, Cambridge Studies in Advanced Mathematics (Cambridge University Press, 2001).CrossRefGoogle Scholar
3.Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G., The degree sequence of a scalefree random graph process, Random Struct. Algorithms 18(3) (2001), 279–290.CrossRefGoogle Scholar
4.Bollobás, B. and Riordan, O., The diameter of a scale-free random graph, Combinatorica 24(1) (2004), 5–34.CrossRefGoogle Scholar
5.Cameron, P., The random graph, in The mathematics of Paul Erdős II (ed. Graham, R. L., Nešetřil, J. and Butler, S.), pp. 333–351 (Springer, Berlin–Heidelberg, 1997).Google Scholar
6.Dereich, S. and Mörters, P., Random networks with sublinear preferential attachment degree evolutions, Electron. J. Probab. 43(14) (2009), 1222–1267.CrossRefGoogle Scholar
7.Dereich, S. and Mörters, P., Random networks with sublinear preferential attachment: the giant component, Ann. Probab. 41(1) (2013), 329–384.CrossRefGoogle Scholar
8.Elwes, R., Preferential attachment processes approaching the rado multigraph, preprint (arXiv:1502.05618, 2015).Google Scholar
9.Freedman, D., Bernard Friedman's urn, Ann. Math. Stat. 36(3) (1965), 956–970.CrossRefGoogle Scholar
10.Kleinberg, R. and Kleinberg, J., Isomorphism and embedding problems for infinite limits of scale-free graphs. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 277–286 (Society for Industrial and Applied Mathematics, 2005).Google Scholar
11.Oliveira, R. and Spencer, J., Connectivity transitions in networks with super-linear preferential attachment, Internet Math. 2(2) (2005), 121–163.CrossRefGoogle Scholar