We are interested in the asymptotics of random trees built by linear preferential attachment, also known in the literature as Barabási–Albert trees or plane-oriented recursive trees. We first prove a conjecture of Bubeck, Mossel & Rácz [9] concerning the influence of the seed graph on the asymptotic behavior of such trees. Separately we study the geometric structure of nodes of large degrees in a plane version of Barabási–Albert trees via their associated looptrees. As the number of nodes grows, we show that these looptrees, appropriately rescaled, converge in the Gromov–Hausdorff sense towards a random compact metric space which we call the Brownian looptree. The latter is constructed as a quotient space of Aldous’ Brownian Continuum Random Tree and is shown to have almost sure Hausdorff dimension .
Nous nous intéressons au comportement asymptotique d’arbres aléatoires construits par attachement préférentiel linéaire, qui sont aussi connus dans la littérature sous le nom d’arbres de Barabási-Albert ou encore arbres plans récursifs. Nous validons une conjecture de Bubeck, Mossel & Rácz relative à l’influence de l’arbre initial sur le comportement asymptotique de ces arbres. Séparément, nous étudions la structure géométrique des sommets de grand degré dans la version planaire des arbres de Barabási-Albert en considérant leurs « arbres à boucles ». Lorsque le nombre de sommets croît, nous prouvons que ces arbres à boucles, convenablement mis à l’échelle, convergent au sens de Gromov-Hausdorff vers un espace métrique compact aléatoire, que nous appelons « l’arbre à boucles brownien ». Ce dernier est construit comme un espace quotient de l’arbre continu brownien d’Aldous, et nous prouvons que sa dimension de Hausdorff vaut presque sûrement.
Accepted:
DOI: 10.5802/jep.15
Keywords: Preferential attachment model, Brownian tree, Looptree, Poisson boundary
Mot clés : Modèle d’attachement préférentiel, arbre brownien, arbre à boucles, bord de Poisson
Nicolas Curien 1; Thomas Duquesne 2; Igor Kortchemski 3; Ioan Manolescu 4
CC-BY-ND 4.0
@article{JEP_2015__2__1_0,
author = {Nicolas Curien and Thomas Duquesne and Igor Kortchemski and Ioan Manolescu},
title = {Scaling limits and influence of the seed graph in preferential attachment trees},
journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
pages = {1--34},
publisher = {\'Ecole polytechnique},
volume = {2},
year = {2015},
doi = {10.5802/jep.15},
mrnumber = {3326003},
zbl = {1320.05110},
language = {en},
url = {https://jep.centre-mersenne.org/articles/10.5802/jep.15/}
}
TY - JOUR AU - Nicolas Curien AU - Thomas Duquesne AU - Igor Kortchemski AU - Ioan Manolescu TI - Scaling limits and influence of the seed graph in preferential attachment trees JO - Journal de l’École polytechnique — Mathématiques PY - 2015 SP - 1 EP - 34 VL - 2 PB - École polytechnique UR - https://jep.centre-mersenne.org/articles/10.5802/jep.15/ DO - 10.5802/jep.15 LA - en ID - JEP_2015__2__1_0 ER -
%0 Journal Article %A Nicolas Curien %A Thomas Duquesne %A Igor Kortchemski %A Ioan Manolescu %T Scaling limits and influence of the seed graph in preferential attachment trees %J Journal de l’École polytechnique — Mathématiques %D 2015 %P 1-34 %V 2 %I École polytechnique %U https://jep.centre-mersenne.org/articles/10.5802/jep.15/ %R 10.5802/jep.15 %G en %F JEP_2015__2__1_0
Nicolas Curien; Thomas Duquesne; Igor Kortchemski; Ioan Manolescu. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’École polytechnique — Mathématiques, Volume 2 (2015), pp. 1-34. doi : 10.5802/jep.15. https://jep.centre-mersenne.org/articles/10.5802/jep.15/
[1] - “The continuum limit of critical random graphs”, Probab. Theory Related Fields 152 (2012) no. 3-4, p. 367-406 | DOI | MR | Zbl
[2] - “The continuum random tree. I”, Ann. Probab. 19 (1991) no. 1, p. 1-28 | MR | Zbl
[3] - “Recursive self-similarity for random trees, random triangulations and Brownian excursion”, Ann. Probab. 22 (1994) no. 2, p. 527-545 | DOI | MR | Zbl
[4] - “On a characteristic property of Pólya’s urn”, Studia Sci. Math. Hungar. 4 (1969), p. 31-35 | Zbl
[5] - “Emergence of scaling in random networks”, Science 286 (1999) no. 5439, p. 509-512 | DOI | MR | Zbl
[6] - “Asymptotic behavior and distributional limits of preferential attachment graphs”, Ann. Probab. 42 (2014) no. 1, p. 1-40 | DOI | MR | Zbl
[7] - “The degree sequence of a scale-free random graph process”, Random Structures Algorithms 18 (2001) no. 3, p. 279-290 | DOI | MR | Zbl
[8] - “On the influence of the seed graph in the preferential attachment model” (2014), arXiv:1401.4849v2
[9] - “On the influence of the seed graph in the preferential attachment model” (2014), arXiv:1401.4849v3
[10] - A course in metric geometry, Graduate Studies in Mathematics, vol. 33, American Mathematical Society, Providence, RI, 2001 | MR | Zbl
[11] - “Smoothing equations for large Pólya urns.” (2013), to appear in Journal of Theoretical Probability, arXiv:1302.1412 | Zbl
[12] - “The stable trees are nested”, Probab. Theory Related Fields 157 (2013) no. 3-4, p. 847-883 | DOI | MR | Zbl
[13] - “Random stable looptrees” (2013), arXiv:1304.1044 | Zbl
[14] - “Percolation on random triangulations and stable looptrees” (2013), arXiv:1307.6818 | Zbl
[15] - “Random networks with sublinear preferential attachment: the giant component”, Ann. Probab. 41 (2013) no. 1, p. 329-384 | DOI | MR | Zbl
[16] - Probability and real trees, Lect. Notes in Math., vol. 1920, Springer, Berlin, 2008, Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005 | DOI | MR
[17] - “Probabilities on cladograms: Introduction to the alpha model” (2005), arXiv:math/0511246v1
[18] - “Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees”, Ann. Probab. 40 (2012) no. 6, p. 2589-2666 | DOI | MR | Zbl
[19] - “Random graphs and complex networks” (2013), in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf
[20] - “Random trees and applications”, Probab. Surv. 2 (2005), p. 245-311 | DOI | MR | Zbl
[21] - “Random geometry on the sphere”, Proceedings of ICM 2014, Seoul (2014), to appear, arXiv:1403.7943
[22] - Geometry of sets and measures in Euclidean spaces: Fractals and rectifiability, Cambridge Studies in Advanced Mathematics, vol. 44, Cambridge University Press, Cambridge, 1995 | DOI | Zbl
[23] - “Tessellations of random maps of arbitrary genus”, Ann. Sci. École Norm. Sup. (4) 42 (2009) no. 5, p. 725-781 | DOI | Numdam | MR | Zbl
[24] - “On random trees”, Studia Sci. Math. Hungar. 39 (2002) no. 1-2, p. 143-155 | DOI | MR | Zbl
[25] - “The maximum degree of the Barabási-Albert random tree”, Combin. Probab. Comput. 14 (2005) no. 3, p. 339-348 | DOI | Zbl
[26] - “Joint degree distributions of preferential attachment random graphs” (2014), arXiv:1402.4686
[27] - Combinatorial stochastic processes, Lect. Notes in Math., vol. 1875, Springer-Verlag, Berlin, 2006, Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002 | MR
[28] - “Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire”, RAIRO Inform. Théor. 19 (1985) no. 2, p. 179-195 | Zbl
[29] - “On a nonuniform random recursive tree”, in Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, p. 297-306 | MR | Zbl
[30] - Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000 | DOI | MR | Zbl
Cited by Sources: