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 :
Accepté le :
DOI : 10.5802/jep.15
Classification : 05C80, 60J80, 05C05, 60G42
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

1 Département de mathématiques, Université Paris-Sud Orsay Bâtiment 425, 91405 Orsay, France
2 LPMA, Université Pierre et Marie Curie (Paris 6) Case courrier 188, 4 place Jussieu, 75252 Paris Cedex 05, France
3 Département de Mathématiques et Applications, École Normale Supérieure 45 rue d’Ulm, 75230 Paris Cedex 05, France
4 Département de Mathématiques, Université de Genève 2-4 rue du Lièvre, Case postale 64, 1211 Genève 4, Suisse
Licence : CC-BY-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@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] 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 | DOI | MR | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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

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

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

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

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

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | Zbl

[23] G. Miermont - “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] T. F. Móri - “On random trees”, Studia Sci. Math. Hungar. 39 (2002) no. 1-2, p. 143-155 | DOI | MR | Zbl

[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 | DOI | Zbl

[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

[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

[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 | Zbl

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

Cité par Sources :