Degree asymptotics with rates for preferential attachment random graphs. (English) Zbl 1271.60019

The authors study the distribution of the degree of a fixed vertex in two preferential attachment models \(G_n\). Let \(W_{n,i}\) be the degree of vertex \(i\) in \(G_n\). They show the optimal rates of convergence in the Kolmogrov metric of \(W_{n,i}/(\operatorname{E}W^2_{n,i})^{1/2}\) to the asymptotic distribution of its distribution limit \(K_s\) as \(n\) goes to infinity. The distribution function \(K_s\) is defined by its density as \[ k_s(x)=\Gamma(s)\sqrt{\frac{2}{s\pi}}\exp\left(\frac{-x^2}{2s}\right)U\left(s-1,0.5,\frac{x^2}{2s}\right) \] for \(x>0\) and \(s\geq1/2\). Here, \(\Gamma\) and \(U\) represent the gamma function and the confluent hypergeometric function of the second kind, respectively. The main approach is a development of Stein’s method for the distribution \(K_s\) using fixed points of distributional transformations.


60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv Euclid


[1] Abramowitz, M. and Stegun, I. A., eds. (1964). Handbook of Mathematical Functions with Formulas , Graphs , and Mathematical Tables . Dover, New York. · Zbl 0171.38503
[2] Arratia, R. and Goldstein, L. (2010). Size bias, sampling, the waiting time paradox, and infinite divisibility: When is the increment independent? Unpublished manuscript. Available at [math.PR]. 1007.3910
[3] Backhausz, Á. (2011). Limit distribution of degrees in random family trees. Electron. Commun. Probab. 16 29-37. · Zbl 1228.05242
[4] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[5] 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. · Zbl 0985.05047
[6] Brown, M. (2006). Exploiting the waiting time paradox: Applications of the size-biasing transformation. Probab. Engrg. Inform. Sci. 20 195-230. · Zbl 1119.60073
[7] Bustoz, J. and Ismail, M. E. H. (1986). On gamma function inequalities. Math. Comp. 47 659-667. · Zbl 0607.33002
[8] Chamayou, J.-F. and Letac, G. (1999). Additive properties of the Dufresne laws and their multivariate extension. J. Theoret. Probab. 12 1045-1066. · Zbl 0966.60002
[9] Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method . Springer, Heidelberg. · Zbl 1213.62027
[10] Durrett, R. (2007). Random Graph Dynamics . Cambridge Univ. Press, Cambridge. · Zbl 1116.05001
[11] Durrett, R. (2010). Probability : Theory and Examples , 4th ed. Cambridge Univ. Press, Cambridge. · Zbl 1202.60001
[12] Ford, E. (2009). Barabási-Albert random graphs, scale-free distributions and bounds for approximation through Stein’s method. Ph.D. thesis, Univ. Oxford.
[13] Goldstein, L. (2007). \(L^{1}\) bounds in normal approximation. Ann. Probab. 35 1888-1930. · Zbl 1144.60018
[14] Goldstein, L. (2009). Personal communication and unpublished notes. Stein workshop, January 2009, Singapore.
[15] Goldstein, L. and Reinert, G. (1997). Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Probab. 7 935-952. · Zbl 0903.60019
[16] Gordon, R. D. (1941). Values of Mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. Ann. Math. Statistics 12 364-366. · Zbl 0026.33201
[17] Janson, S. (2006). Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 417-452. · Zbl 1112.60012
[18] Janson, S. (2010). Moments of gamma type and the Brownian supremum process area. Probab. Surv. 7 1-52. · Zbl 1194.60019
[19] Lyons, R., Pemantle, R. and Peres, Y. (1995). Conceptual proofs of \(L\log L\) criteria for mean behavior of branching processes. Ann. Probab. 23 1125-1138. · Zbl 0840.60077
[20] Móri, T. F. (2005). The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput. 14 339-348. · Zbl 1078.05077
[21] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167-256 (electronic). · Zbl 1029.68010
[22] Pakes, A. G. and Khattree, R. (1992). Length-biasing, characterizations of laws and the moment problem. Austral. J. Statist. 34 307-322. · Zbl 0759.62005
[23] Peköz, E. A. and Röllin, A. (2011). New rates for exponential approximation and the theorems of Rényi and Yaglom. Ann. Probab. 39 587-608. · Zbl 1213.60049
[24] Peköz, E., Röllin, A. and Ross, N. (2012). Total variation error bounds for geometric approximation. Bernoulli . To appear. Available at [math.PR]. 1005.2774 · Zbl 1412.60012
[25] Pitman, J. and Ross, N. (2012). Archimedes, Gauss, and Stein. Notices Amer. Math. Soc. 59 1416-1421. · Zbl 1284.60036
[26] Reinert, G. (2005). Three general approaches to Stein’s method. In An Introduction to Stein’s Method. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 4 183-221. Singapore Univ. Press, Singapore.
[27] Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv. 8 210-293. · Zbl 1245.60033
[28] Ross, S. and Peköz, E. (2007). A Second Course in Probability . www.ProbabilityBookstore.com, Boston, MA.
[29] Stein, C. (1986). Approximate Computation of Expectations . IMS, Hayward, CA. · Zbl 0721.60016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.