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.
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 .
@article{JEP_2015__2__1_0,
author = {Curien, Nicolas and Duquesne, Thomas and Kortchemski, Igor and Manolescu, Ioan},
title = {Scaling limits and influence of the seed graph in preferential attachment trees},
journal = {Journal de l'\'Ecole polytechnique - Math\'ematiques},
volume = {2},
year = {2015},
pages = {1-34},
doi = {10.5802/jep.15},
language = {en},
url = {http://dml.mathdoc.fr/item/JEP_2015__2__1_0}
}
Curien, Nicolas; Duquesne, Thomas; Kortchemski, Igor; Manolescu, Ioan. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l'École polytechnique - Mathématiques, Tome 2 (2015) pp. 1-34. doi : 10.5802/jep.15. http://gdmltest.u-ga.fr/item/JEP_2015__2__1_0/
[1] The continuum limit of critical random graphs, Probab. Theory Related Fields, Tome 152 (2012) no. 3-4, pp. 367-406 | Article | MR 2892951 | Zbl 1239.05165
[2] The continuum random tree. I, Ann. Probab., Tome 19 (1991) no. 1, pp. 1-28 http://www.jstor.org/stable/2244250 | MR 1085326 | Zbl 0722.60013
[3] Recursive self-similarity for random trees, random triangulations and Brownian excursion, Ann. Probab., Tome 22 (1994) no. 2, pp. 527-545 http://www.jstor.org/stable/2244884 | MR 1288122 | Zbl 0808.60017
[4] On a characteristic property of Pólya’s urn, Studia Sci. Math. Hungar., Tome 4 (1969), pp. 31-35 | MR 247643 | Zbl 0185.47301
[5] Emergence of scaling in random networks, Science, Tome 286 (1999) no. 5439, pp. 509-512 | Article | MR 2091634 | Zbl 1226.05223
[6] Asymptotic behavior and distributional limits of preferential attachment graphs, Ann. Probab., Tome 42 (2014) no. 1, pp. 1-40 | Article | MR 3161480 | Zbl 1296.60010
[7] The degree sequence of a scale-free random graph process, Random Structures Algorithms, Tome 18 (2001) no. 3, pp. 279-290 | Article | MR 1824277 | Zbl 0985.05047
[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, American Mathematical Society, Providence, RI, Graduate Studies in Mathematics, Tome 33 (2001), pp. xiv+415 | MR 1835418 | Zbl 0981.51016
[11] Smoothing equations for large Pólya urns. (2013) (to appear in Journal of Theoretical Probability, arXiv:1302.1412)
[12] The stable trees are nested, Probab. Theory Related Fields, Tome 157 (2013) no. 3-4, pp. 847-883 | Article | MR 3129805 | Zbl 1286.60074
[13] Random stable looptrees (2013) (arXiv:1304.1044)
[14] Percolation on random triangulations and stable looptrees (2013) (arXiv:1307.6818)
[15] Random networks with sublinear preferential attachment: the giant component, Ann. Probab., Tome 41 (2013) no. 1, pp. 329-384 | Article | MR 3059201 | Zbl 1260.05143
[16] Probability and real trees, Springer, Berlin, Lect. Notes in Math., Tome 1920 (2008), pp. xii+193 (Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005) | Article | MR 2351587 | Zbl 1139.60006
[17] Probabilities on cladograms: Introduction to the alpha model (2005) (arXiv:math/0511246v1) | MR 2708802
[18] Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, Ann. Probab., Tome 40 (2012) no. 6, pp. 2589-2666 | Article | MR 3050512 | Zbl 1259.60033
[19] Random graphs and complex networks (2013) (in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf)
[20] Random trees and applications, Probab. Surv., Tome 2 (2005), pp. 245-311 | Article | MR 2203728 | Zbl 1189.60161
[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 University Press, Cambridge, Cambridge Studies in Advanced Mathematics, Tome 44 (1995), pp. xii+343 | Article | MR 1333890 | Zbl 0819.28004
[23] Tessellations of random maps of arbitrary genus, Ann. Sci. École Norm. Sup. (4), Tome 42 (2009) no. 5, pp. 725-781 | Numdam | MR 2571957 | Zbl 1228.05118
[24] On random trees, Studia Sci. Math. Hungar., Tome 39 (2002) no. 1-2, pp. 143-155 | Article | MR 1909153 | Zbl 1026.05095
[25] The maximum degree of the Barabási-Albert random tree, Combin. Probab. Comput., Tome 14 (2005) no. 3, pp. 339-348 | Article | MR 2138118 | Zbl 1078.05077
[26] Joint degree distributions of preferential attachment random graphs (2014) (arXiv:1402.4686)
[27] Combinatorial stochastic processes, Springer-Verlag, Berlin, Lect. Notes in Math., Tome 1875 (2006), pp. x+256 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002) | MR 2245368 | Zbl 1103.60004
[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., Tome 19 (1985) no. 2, pp. 179-195 | Numdam | MR 803997 | Zbl 0565.05037
[29] On a nonuniform random recursive tree, Random graphs ’85 (Poznań, 1985), North-Holland, Amsterdam (North-Holland Math. Stud.) Tome 144 (1987), pp. 297-306 | MR 930497 | Zbl 0646.05023
[30] Random walks on infinite graphs and groups, Cambridge University Press, Cambridge, Cambridge Tracts in Mathematics, Tome 138 (2000), pp. xii+334 | Article | MR 1743100 | Zbl 0951.60002