[Limites d’échelle et ontogenèse des arbres construits par attachement préférentiel]
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 .
Accepté le :
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, Tome 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
Cité par Sources :