# zbMATH — the first resource for mathematics

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 · arxiv.org  Backhausz, Á. (2011). Limit distribution of degrees in random family trees. Electron. Commun. Probab. 16 29-37. · Zbl 1228.05242 · doi:10.1214/ECP.v16-1598 · emis:journals/EJP-ECP/_ejpecp/ECP/viewarticle7271.html  Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509  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 · doi:10.1002/rsa.1009  Brown, M. (2006). Exploiting the waiting time paradox: Applications of the size-biasing transformation. Probab. Engrg. Inform. Sci. 20 195-230. · Zbl 1119.60073 · doi:10.1017/S026996480606013X  Bustoz, J. and Ismail, M. E. H. (1986). On gamma function inequalities. Math. Comp. 47 659-667. · Zbl 0607.33002 · doi:10.2307/2008180  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 · doi:10.1023/A:1021649305082  Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method . Springer, Heidelberg. · Zbl 1213.62027 · doi:10.1007/978-3-642-15007-4  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 · doi:10.1214/009117906000001123  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 · doi:10.1214/aoap/1043862419  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 · doi:10.1214/aoms/1177731721  Janson, S. (2006). Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 417-452. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7  Janson, S. (2010). Moments of gamma type and the Brownian supremum process area. Probab. Surv. 7 1-52. · Zbl 1194.60019 · doi:10.1214/10-PS160 · eudml:227681  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 · doi:10.1214/aop/1176988176  Móri, T. F. (2005). The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput. 14 339-348. · Zbl 1078.05077 · doi:10.1017/S0963548304006133  Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167-256 (electronic). · Zbl 1029.68010 · doi:10.1137/S003614450342480  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 · doi:10.1111/j.1467-842X.1992.tb01363.x  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 · doi:10.1214/10-AOP559  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 · arxiv.org  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. · doi:10.1142/9789812567680_0004  Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv. 8 210-293. · Zbl 1245.60033 · doi:10.1214/11-PS182 · euclid:ps/1319806862  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.