×

Power laws in preferential attachment graphs and Stein’s method for the negative binomial distribution. (English) Zbl 1273.05205

Summary: For a family of linear preferential attachment graphs, we provide rates of convergence for the total variation distance between the degree of a randomly chosen vertex and an appropriate power law distribution as the number of vertices tends to \(\infty \). Our proof uses a new formulation of Stein’s method for the negative binomial distribution, which stems from a distributional transformation that has the negative binomial distributions as the only fixed points.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C07 Vertex degrees
60F05 Central limit and other weak theorems
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Adell, J. A. and Jodrá, P. (2006). Exact Kolmogorov and total variation distances between some familiar discrete distributions. J. Inequal. Appl. 2006 , 64307, 8 pp. · Zbl 1090.60506
[2] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 , 509-512. · Zbl 1226.05223
[3] Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation (Oxford Stud. Prob. 2 ). The Clarendon Press, Oxford University Press, New York. · Zbl 0746.60002
[4] 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
[5] Brown, T. C. and Phillips, M. J. (1999). Negative binomial approximation with Stein’s method. Methodology Comput. Appl. Prob. 1 , 407-421. · Zbl 0992.62015
[6] Brown, T. C. and Xia, A. (2001). Stein’s method and birth-death processes. Ann. Prob. 29 , 1373-1403. · Zbl 1019.60019
[7] Buckley, P. G. and Osthus, D. (2004). Popularity based random graph models leading to a scale-free degree sequence. Discrete Math. 282 , 53-68. · Zbl 1042.05089
[8] Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method . Springer, Heidelberg. · Zbl 1213.62027
[9] Goldstein, L. and Reinert, G. (1997). Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Prob. 7 , 935-952. · Zbl 0903.60019
[10] Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application . John Wiley, New York. · Zbl 0352.60001
[11] Jordan, J. (2006). The degree sequences and spectra of scale-free random graphs. Random Structures Algorithms 29 , 226-242. · Zbl 1108.05083
[12] Klar, B. (2000). Bounds on tail probabilities of discrete distributions. Prob. Eng. Inf. Sci. 14 , 161-171. · Zbl 0967.62014
[13] Móri, T. F. (2005). The maximum degree of the Barabási-Albert random tree. Combinatorics Prob. Comput. 14 , 339-348. · Zbl 1078.05077
[14] Peköz, E. A. (1996). Stein’s method for geometric approximation. J. Appl. Prob. 33 , 707-713. · Zbl 0865.60014
[15] Peköz, E. A. and Röllin, A. (2011). New rates for exponential approximation and the theorems of Rényi and Yaglom. Ann. Prob. 39 , 587-608. · Zbl 1213.60049
[16] Peköz, E. A., Röllin, A. and Ross, N. (2013). Total variation error bounds for geometric approximation. Bernoulli 19 , 610-632. · Zbl 1412.60012
[17] 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. · Zbl 1271.60019
[18] Pitman, J. and Ross, N. (2012). Archimedes, Gauss, and Stein. Notices AMS 59 , 1416-1421. · Zbl 1284.60036
[19] Ross, N. (2011). Fundamentals of Stein’s method. Prob. Surveys 8 , 210-293. · Zbl 1245.60033
[20] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 , 186-202. · Zbl 1144.60051
[21] Van Der Hofstad, R. (2012). Random graphs and complex networks. Lecture Notes, Eindhoven University of Technology. Available at http://www.win.tue.nl/\(\sim\)rhofstad/NotesRGCN.pdf. · Zbl 1238.60116
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.