staple
Avec cedram.org
logo JEP
Table des matières de ce volume | Article suivant
Nicolas Curien; Thomas Duquesne; Igor Kortchemski; Ioan Manolescu
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, 2 (2015), p. 1-34, doi: 10.5802/jep.15
Article PDF | TeX source
Class. Math.: 05C80, 60J80, 05C05, 60G42
Mots clés: Modèle d’attachement préférentiel, arbre brownien, arbre à boucles, bord de Poisson

Résumé - Abstract

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.

Bibliographie

[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  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  MR 247643 |  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, Ch. 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”, arXiv:1401.4849v2, 2014
[9] S. Bubeck, E. Mossel & M. Z. Rácz, “On the influence of the seed graph in the preferential attachment model”, arXiv:1401.4849v3, 2014
[10] D. Burago, Y. Burago & S. Ivanov, A course in metric geometry, Graduate Studies in Mathematics 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.”, to appear in Journal of Theoretical Probability, arXiv:1302.1412, 2013
[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”, arXiv:1304.1044, 2013
[14] N. Curien & I. Kortchemski, “Percolation on random triangulations and stable looptrees”, arXiv:1307.6818, 2013
[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. 1920, Springer, Berlin, 2008, Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005 Article |  MR 2351587 |  Zbl 1139.60006
[17] D. J. Ford, “Probabilities on cladograms: Introduction to the alpha model”, arXiv:math/0511246v1, 2005  MR 2708802
[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”, in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf, 2013
[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, in Proceedings of ICM 2014, Seoul, to appear, arXiv:1403.7943, 2014
[22] P. Mattila, Geometry of sets and measures in Euclidean spaces: Fractals and rectifiability, Cambridge Studies in Advanced Mathematics 44, Cambridge University Press, Cambridge, 1995 Article |  MR 1333890 |  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 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 |  MR 2138118 |  Zbl 1078.05077
[26] E. A. Peköz, A. Röllin & N. Ross, “Joint degree distributions of preferential attachment random graphs”, arXiv:1402.4686, 2014
[27] J. Pitman, Combinatorial stochastic processes, Lect. Notes in Math. 1875, Springer-Verlag, Berlin, 2006, Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002  MR 2245368 |  Zbl 1103.60004
[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 Numdam |  MR 803997 |  Zbl 0565.05037
[29] J. Szymański, On a nonuniform random recursive tree, Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud. 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 138, Cambridge University Press, Cambridge, 2000 Article |  MR 1743100 |  Zbl 0951.60002