Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T11:05:47.695Z Has data issue: false hasContentIssue false
  • English
  • Français

Joint degree distributions of preferential attachment random graphs

Part of:Graph theoryLimit theoremsSpecial processesCombinatorial probability

Published online by Cambridge University Press:  26 June 2017

Erol Peköz,
Adrian Röllin and
Nathan Ross
Erol Peköz*
Affiliation:
Boston University
Adrian Röllin*
Affiliation:
National University of Singapore
Nathan Ross*
Affiliation:
University of Melbourne
*
* Postal address: Questrom School of Business, Boston University, 595 Commonwealth Avenue, Room 607, Boston, MA 02215, USA. Email address: pekoz@bu.edu
** Postal address: Department of Statistics and Applied Probability, National University of Singapore, 6 Science Drive 2, Singapore 117546, Singapore. Email address: adrian.roellin@nus.edu.sg
*** Postal address: School of Mathematics and Statistics, University of Melbourne, Richard Berry Building, VIC 3010, Australia. Email address: nathan.ross@unimelb.edu.au
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the joint degree counts in linear preferential attachment random graphs and find a simple representation for the limit distribution in infinite sequence space. We show weak convergence with respect to the p-norm topology for appropriate p and also provide optimal rates of convergence of the finite-dimensional distributions. The results hold for models with any general initial seed graph and any fixed number of initial outgoing edges per vertex; we generate nontree graphs using both a lumping and a sequential rule. Convergence of the order statistics and optimal rates of convergence to the maximum of the degrees is also established.

Keywords

Preferential attachment random graphmulticolor Pólya urndistributional approximation

MSC classification

Primary:60F05: Central limit and other weak theorems60C05: Combinatorial probability
Secondary:05C80: Random graphs60K99: None of the above, but in this section

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 2 , June 2017, pp. 368 - 387
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Aldous, D. (1991). The continuum random tree. I. Ann. Prob. 19, 1–28. CrossRefGoogle Scholar
[2] Aldous, D. (1993). The continuum random tree. III. Ann. Prob. 21, 248–289. Google Scholar
[3] Antunović, T., Mossel, E. and Rácz, M. Z. (2016). Coexistence in preferential attachment networks. Combinatorics Prob. Comput. 25, 797–822. Google Scholar
[4] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512. Google Scholar
[5] Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Prob. 42, 1–40. Google Scholar
[6] Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290. Google Scholar
[7] Bubeck, S., Mossel, E. and Rácz, M. Z. (2015). On the influence of the seed graph in the preferential attachment model. IEEE Trans. Network Sci. Eng. 2, 30–39. Google Scholar
[8] Collevecchio, A., Cotar, C. and LiCalzi, M. (2013). On a preferential attachment and generalized Polya's urn model. Ann. Appl. Prob. 23, 1219–1253. Google Scholar
[9] Curien, N., Duquesne, T., Kortchemski, I. and Manolescu, I. (2015). Scaling limits and influence of the seed graph in preferential attachment trees. J. Éc. Polytech. Math. 2, 1–34. Google Scholar
[10] Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York. Google Scholar
[11] Goldstein, L. and Reinert, G. (2013). Stein's method for the beta distribution and the Pólya–Eggenberger urn. J. Appl. Prob. 50, 1187–1205. Google Scholar
[12] James, L. F. (2015). Generalized Mittag Leffler distributions arising as limits in preferential attachment models. Preprint. Available at https://arxiv.org/abs/1509.07150v4. Google Scholar
[13] Janson, S. (2006). Limit theorems for triangular urn schemes. Prob. Theory Relat. Fields 134, 417–452. Google Scholar
[14] Krapivsky, P. L., Redner, S. and Leyvraz, F. (2000). Connectivity of growing random networks. Phys. Rev. Lett. 85, 4629. Google Scholar
[15] Lieb, E. H. and Loss, M. (2001). Analysis (Graduate Stud. Math. 14), 2nd edn. American Mathematical Society, Providence, RI. Google Scholar
[16] Móri, T. F. (2005). The maximum degree of the Barabási–Albert random tree. Combinatorics Prob. Comput. 14, 339–348. Google Scholar
[17] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45, 167–256. Google Scholar
[18] Newman, M., Barabási, A.-L. and Watts, D. J. (2006). The Structure and Dynamics of Networks. Princeton University Press. Google Scholar
[19] Peköz, E. A., Röllin, A. and Ross, N. (2013). Degree asymptotics with rates for preferential attachment random graphs. Ann. Appl. Prob. 23, 1188–1218. Google Scholar
[20] Peköz, E. A., Röllin, A. and Ross, N. (2013). Total variation error bounds for geometric approximation. Bernoulli 19, 610–632. CrossRefGoogle Scholar
[21] Peköz, E. A., Röllin, A. and Ross, N. (2016). Generalized gamma approximation with rates for urns, walks and trees. Ann. Prob. 44, 1776–1816. Google Scholar
[22] Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1–79. Google Scholar
[23] Pitman, J. (1999). Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times. Electron. J. Prob. 4, 33pp. Google Scholar
[24] Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin. Google Scholar
[25] Ross, N. (2013). Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution. Adv. Appl. Prob. 45, 876–893. CrossRefGoogle Scholar
[26] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31, 186–202. Google Scholar
[27] Suquet, C. (1999). Tightness in Schauder decomposable Banach spaces. In Proc. St. Petersburg Mathematical Society (Amer. Math. Soc. Transl. Ser. 193), Vol. V, American Mathematical Society, Providence, RI, pp. 201–224. Google Scholar
[28] Van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press. Google Scholar