Scaling limits and influence of the seed graph in preferential attachment trees
[Limites d’échelle et ontogenèse des arbres construits par attachement préférentiel]
Journal de l’École polytechnique — Mathématiques, Tome 2 (2015) , pp. 1-34.

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 2 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 2.

Reçu le : 2014-08-18
Accepté le : 2015-01-08
DOI : https://doi.org/10.5802/jep.15
Classification : 05C80,  60J80,  05C05,  60G42
Mots clés: Modèle d’attachement préférentiel, arbre brownien, arbre à boucles, bord de Poisson
@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'\'Ecole polytechnique --- Math\'ematiques},
     pages = {1--34},
     publisher = {\'Ecole polytechnique},
     volume = {2},
     year = {2015},
     doi = {10.5802/jep.15},
     zbl = {1320.05110},
     mrnumber = {3326003},
     language = {en},
     url = {jep.centre-mersenne.org/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. https://jep.centre-mersenne.org/item/JEP_2015__2__1_0/

[1] L. Addario-Berry, N. Broutin & C. Goldschmidt - “The continuum limit of critical random graphs”, Probab. Theory Related Fields 152 (2012) no. 3-4, p. 367-406 | Article | MR 2892951 | Zbl 1239.05165

[2] D. Aldous - “The continuum random tree. I”, Ann. Probab. 19 (1991) no. 1, p. 1-28 | MR 1085326 | Zbl 0722.60013

[3] D. Aldous - “Recursive self-similarity for random trees, random triangulations and Brownian excursion”, Ann. Probab. 22 (1994) no. 2, p. 527-545 | Article | MR 1288122 | Zbl 0808.60017

[4] K. B. Athreya - “On a characteristic property of Pólya’s urn”, Studia Sci. Math. Hungar. 4 (1969), p. 31-35 | Zbl 0185.47301

[5] A.-L. Barabási & R. Albert - “Emergence of scaling in random networks”, Science 286 (1999) no. 5439, p. 509-512 | Article | MR 2091634 | Zbl 1226.05223

[6] N. Berger, C. Borgs, J. T. Chayes & A. Saberi - “Asymptotic behavior and distributional limits of preferential attachment graphs”, Ann. Probab. 42 (2014) no. 1, p. 1-40 | Article | MR 3161480 | Zbl 1296.60010

[7] B. Bollobás, O. Riordan, J. Spencer & G. Tusnády - “The degree sequence of a scale-free random graph process”, Random Structures Algorithms 18 (2001) no. 3, p. 279-290 | Article | MR 1824277 | Zbl 0985.05047

[8] S. Bubeck, E. Mossel & M. Z. Rácz - “On the influence of the seed graph in the preferential attachment model” (2014), arXiv:1401.4849v2

[9] S. Bubeck, E. Mossel & M. Z. Rácz - “On the influence of the seed graph in the preferential attachment model” (2014), arXiv:1401.4849v3

[10] D. Burago, Y. Burago & S. Ivanov - A course in metric geometry, Graduate Studies in Mathematics, vol. 33, American Mathematical Society, Providence, RI, 2001 | MR 1835418 | Zbl 0981.51016

[11] B. Chauvin, C. Mailler & N. Pouyanne - “Smoothing equations for large Pólya urns.” (2013), to appear in Journal of Theoretical Probability, arXiv:1302.1412 | Zbl 1358.60010

[12] N. Curien & B. Haas - “The stable trees are nested”, Probab. Theory Related Fields 157 (2013) no. 3-4, p. 847-883 | Article | MR 3129805 | Zbl 1286.60074

[13] N. Curien & I. Kortchemski - “Random stable looptrees” (2013), arXiv:1304.1044 | Zbl 1307.60061

[14] N. Curien & I. Kortchemski - “Percolation on random triangulations and stable looptrees” (2013), arXiv:1307.6818 | Zbl 1342.60164

[15] S. Dereich & P. Mörters - “Random networks with sublinear preferential attachment: the giant component”, Ann. Probab. 41 (2013) no. 1, p. 329-384 | Article | MR 3059201 | Zbl 1260.05143

[16] S. N. Evans - 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 | Article | MR 2351587

[17] D. J. Ford - “Probabilities on cladograms: Introduction to the alpha model” (2005), arXiv:math/0511246v1

[18] B. Haas & G. Miermont - “Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees”, Ann. Probab. 40 (2012) no. 6, p. 2589-2666 | Article | MR 3050512 | Zbl 1259.60033

[19] R. van der Hofstad - “Random graphs and complex networks” (2013), in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf

[20] J.-F. Le Gall - “Random trees and applications”, Probab. Surv. 2 (2005), p. 245-311 | Article | MR 2203728 | Zbl 1189.60161

[21] J.-F. Le Gall - “Random geometry on the sphere”, Proceedings of ICM 2014, Seoul (2014), to appear, arXiv:1403.7943

[22] P. Mattila - Geometry of sets and measures in Euclidean spaces: Fractals and rectifiability, Cambridge Studies in Advanced Mathematics, vol. 44, Cambridge University Press, Cambridge, 1995 | Article | Zbl 0819.28004

[23] G. Miermont - “Tessellations of random maps of arbitrary genus”, Ann. Sci. École Norm. Sup. (4) 42 (2009) no. 5, p. 725-781 | Article | Numdam | MR 2571957 | Zbl 1228.05118

[24] T. F. Móri - “On random trees”, Studia Sci. Math. Hungar. 39 (2002) no. 1-2, p. 143-155 | Article | MR 1909153 | Zbl 1026.05095

[25] T. F. Móri - “The maximum degree of the Barabási-Albert random tree”, Combin. Probab. Comput. 14 (2005) no. 3, p. 339-348 | Article | Zbl 1078.05077

[26] E. A. Peköz, A. Röllin & N. Ross - “Joint degree distributions of preferential attachment random graphs” (2014), arXiv:1402.4686

[27] J. Pitman - 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 2245368

[28] J.-L. Rémy - “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 0565.05037

[29] J. Szymański - “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 930497 | Zbl 0646.05023

[30] W. Woess - Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000 | Article | MR 1743100 | Zbl 0951.60002