## 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.

### MSC:

 60C05 Combinatorial probability 05C80 Random graphs (graph-theoretic aspects)

### Keywords:

preferential attachment; Stein’s method
Full Text:

### References:

  Abramowitz, M. and Stegun, I. A., eds. (1964). Handbook of Mathematical Functions with Formulas , Graphs , and Mathematical Tables . Dover, New York. · Zbl 0171.38503  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  Backhausz, Á. (2011). Limit distribution of degrees in random family trees. Electron. Commun. Probab. 16 29-37. · Zbl 1228.05242  Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223  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  Brown, M. (2006). Exploiting the waiting time paradox: Applications of the size-biasing transformation. Probab. Engrg. Inform. Sci. 20 195-230. · Zbl 1119.60073  Bustoz, J. and Ismail, M. E. H. (1986). On gamma function inequalities. Math. Comp. 47 659-667. · Zbl 0607.33002  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  Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method . Springer, Heidelberg. · Zbl 1213.62027  Durrett, R. (2007). Random Graph Dynamics . Cambridge Univ. Press, Cambridge. · Zbl 1116.05001  Durrett, R. (2010). Probability : Theory and Examples , 4th ed. Cambridge Univ. Press, Cambridge. · Zbl 1202.60001  Ford, E. (2009). Barabási-Albert random graphs, scale-free distributions and bounds for approximation through Stein’s method. Ph.D. thesis, Univ. Oxford.  Goldstein, L. (2007). $$L^{1}$$ bounds in normal approximation. Ann. Probab. 35 1888-1930. · Zbl 1144.60018  Goldstein, L. (2009). Personal communication and unpublished notes. Stein workshop, January 2009, Singapore.  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  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  Janson, S. (2006). Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 417-452. · Zbl 1112.60012  Janson, S. (2010). Moments of gamma type and the Brownian supremum process area. Probab. Surv. 7 1-52. · Zbl 1194.60019  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  Móri, T. F. (2005). The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput. 14 339-348. · Zbl 1078.05077  Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167-256 (electronic). · Zbl 1029.68010  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  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  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  Pitman, J. and Ross, N. (2012). Archimedes, Gauss, and Stein. Notices Amer. Math. Soc. 59 1416-1421. · Zbl 1284.60036  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.  Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv. 8 210-293. · Zbl 1245.60033  Ross, S. and Peköz, E. (2007). A Second Course in Probability . www.ProbabilityBookstore.com, Boston, MA.  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.