Scaling limits and influence of the seed graph in preferential attachment trees

Curien, Nicolas; Duquesne, Thomas; Kortchemski, Igor; Manolescu, Ioan

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

[1] Addario-Berry, L.; Broutin, N.; Goldschmidt, C. The continuum limit of critical random graphs, Probab. Theory Related Fields, Volume 152 (2012) no. 3-4, pp. 367-406 | DOI | MR | Zbl

[2] Aldous, D. The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1-28 http://www.jstor.org/stable/2244250 | MR | Zbl

[3] Aldous, D. Recursive self-similarity for random trees, random triangulations and Brownian excursion, Ann. Probab., Volume 22 (1994) no. 2, pp. 527-545 http://www.jstor.org/stable/2244884 | MR | Zbl

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

[5] Barabási, A.-L.; Albert, R. Emergence of scaling in random networks, Science, Volume 286 (1999) no. 5439, pp. 509-512 | DOI | MR | Zbl

[6] Berger, N.; Borgs, Ch.; Chayes, J. T.; Saberi, A. Asymptotic behavior and distributional limits of preferential attachment graphs, Ann. Probab., Volume 42 (2014) no. 1, pp. 1-40 | DOI | MR | Zbl

[7] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G. The degree sequence of a scale-free random graph process, Random Structures Algorithms, Volume 18 (2001) no. 3, pp. 279-290 | DOI | MR | Zbl

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

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

[10] Burago, D.; Burago, Y.; Ivanov, S. A course in metric geometry, Graduate Studies in Mathematics, 33, American Mathematical Society, Providence, RI, 2001, pp. xiv+415 | MR | Zbl

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

[12] Curien, N.; Haas, B. The stable trees are nested, Probab. Theory Related Fields, Volume 157 (2013) no. 3-4, pp. 847-883 | DOI | MR | Zbl

[13] Curien, N.; Kortchemski, I. Random stable looptrees (2013) (arXiv:1304.1044)

[14] Curien, N.; Kortchemski, I. Percolation on random triangulations and stable looptrees (2013) (arXiv:1307.6818)

[15] Dereich, S.; Mörters, P. Random networks with sublinear preferential attachment: the giant component, Ann. Probab., Volume 41 (2013) no. 1, pp. 329-384 | DOI | MR | Zbl

[16] Evans, S. N. Probability and real trees, Lect. Notes in Math., 1920, Springer, Berlin, 2008, pp. xii+193 (Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005) | DOI | MR | Zbl

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

[18] Haas, B.; Miermont, G. Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, Ann. Probab., Volume 40 (2012) no. 6, pp. 2589-2666 | DOI | MR | Zbl

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

[20] Le Gall, J.-F. Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | MR | Zbl

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

[22] Mattila, P. Geometry of sets and measures in Euclidean spaces: Fractals and rectifiability, Cambridge Studies in Advanced Mathematics, 44, Cambridge University Press, Cambridge, 1995, pp. xii+343 | DOI | MR | Zbl

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

[24] Móri, T. F. On random trees, Studia Sci. Math. Hungar., Volume 39 (2002) no. 1-2, pp. 143-155 | DOI | MR | Zbl

[25] Móri, T. F. The maximum degree of the Barabási-Albert random tree, Combin. Probab. Comput., Volume 14 (2005) no. 3, pp. 339-348 | DOI | MR | Zbl

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

[27] Pitman, J. Combinatorial stochastic processes, Lect. Notes in Math., 1875, Springer-Verlag, Berlin, 2006, pp. x+256 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002) | MR | Zbl

[28] Rémy, J.-L. Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., Volume 19 (1985) no. 2, pp. 179-195 | Numdam | MR | Zbl

[29] Szymański, J. On a nonuniform random recursive tree, Random graphs ’85 (Poznań, 1985) (North-Holland Math. Stud.), Volume 144, North-Holland, Amsterdam, 1987, pp. 297-306 | MR | Zbl

[30] Woess, W. Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, 138, Cambridge University Press, Cambridge, 2000, pp. xii+334 | DOI | MR | Zbl