×

Consistency of Hill estimators in a linear preferential attachment model. (English) Zbl 1432.60056

Summary: Preferential attachment is widely used to model power-law behavior of degree distributions in both directed and undirected networks. Statistical estimates of the tail exponent of the power-law degree distribution often use the Hill estimator as one of the key summary statistics. The consistency of the Hill estimator for network data has not been explored and the major goal in this paper is to prove consistency in certain models. To do this, we first derive the asymptotic behavior of the degree sequence via embedding the degree growth of a fixed node into a birth immigration process and then show the convergence of the tail empirical measure. From these steps, the consistency of the Hill estimator is obtained. Simulations are provided as an illustration for the asymptotic distribution of the Hill estimator.

MSC:

60G70 Extreme value theory; extremal stochastic processes
05C80 Random graphs (graph-theoretic aspects)
60B10 Convergence of probability measures
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
60G57 Random measures

Software:

plfit; KONECT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Athreya, K.B.: Preferential attachment random graphs with general weight function. Internet Math. 4(4), 401-418 (2007). https://doi.org/10.1080/15427951.2007.10129150 · Zbl 1206.68225 · doi:10.1080/15427951.2007.10129150
[2] Athreya, K.B., Ghosh, A.P., Sethuraman, S.: Growth of preferential attachment random graphs via continuous-time branching processes. Proc. Math. Sci. 118(3), 473-494 (2008) · Zbl 1153.05020 · doi:10.1007/s12044-008-0036-2
[3] Bhamidi, S.: Universal techniques to analyze preferential attachment trees: Global and local analysis. Available: http://www.unc.edu/bhamidi/preferent.pdf (2007)
[4] Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003), pp 132-139. ACM, New York (2003) · Zbl 1094.68605
[5] Clauset, A., Shalizi, C.R., Newman, M.E.J.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661-703 (2009). https://doi.org/10.1137/070710111. ISSN 0036-1445 · Zbl 1176.62001 · doi:10.1137/070710111
[6] Csörgö, S., Haeusler, E., Mason, D.M.: The quantile-transform – empirical-process approach to limit theorems for sums of order statistics. In: Sums, Trimmed Sums and Extremes, volume 23 of Progr. Probab., pp 215-267. Birkhäuser, Boston (1991a) · Zbl 0736.60024
[7] de Haan, L., Ferreira, A.: Extreme Value Theory: An Introduction. Springer, New York (2006) · Zbl 1101.62002 · doi:10.1007/0-387-34471-3
[8] de Haan, L., Resnick, S.I.: On asymptotic normality of the Hill estimator. Stoch. Model. 14, 849-867 (1998) · Zbl 1002.60519 · doi:10.1080/15326349808807504
[9] Drees, H., Janßen, A., Wang, T., Resnick, S.I.: Threshold selection by distance minimization. In preparation · Zbl 1484.62057
[10] Durrett, R.T.: Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2010)
[11] Gao, F., van der Vaart, A.: On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees. Stoch. Process. Appl. 127(11), 3754-3775 (2017). ISSN: 0304-4149 · Zbl 1491.62080 · doi:10.1016/j.spa.2017.03.008
[12] Gao, F., van der Vaart, A., Castro, R., van der Hofstad, R.: Consistent estimation in general sublinear preferential attachment trees Electron. J. Statist. 11 (2), 3979-3999 (2017). https://doi.org/10.1214/17-EJS1356. ISSN: 0304-4149 · Zbl 1387.62064 · doi:10.1214/17-EJS1356
[13] Hall, P.: On some simple estimates of an exponent of regular variation. J. Roy. Statist. Soc. Ser. B 44(1), 37-42 (1982). ISSN 0035-9246 · Zbl 0521.62024
[14] Hill, B.M.: A simple general approach to inference about the tail of a distribution. Ann. Statist. 3, 1163-1174 (1975) · Zbl 0323.62033 · doi:10.1214/aos/1176343247
[15] Hsing, T.: On tail estimation using dependent data. Ann. Statist. 19, 1547-1569 (1991) · Zbl 0738.62026 · doi:10.1214/aos/1176348261
[16] Kallenberg, O.: Random Measures, Theory and Applications. Springer Series in Probability Theory and Stochastic Modelling. Springer eBooks. ISBN:978-3-319-41598-7 (2017) · Zbl 1376.60003
[17] Kendall, D.G.: Branching processes since 1873. J. London Math. Soc. 41, 385-406 (1966). https://doi.org/10.1112/jlms/s1-41.1.385. ISSN 0024-6107 · Zbl 0154.42505 · doi:10.1112/jlms/s1-41.1.385
[18] Krapivsky, P.L., Redner, S.: Organization of growing random networks. Phys. Rev. E 63(6), 066123:1-14 (2001) · doi:10.1103/PhysRevE.63.066123
[19] Krapivsky, P., Rodgers, G., Redner, S.: Degree distributions of growing networks. Phys. Rev. Lett., 86. https://doi.org/10.1103/PhysRevLett.86.5401 (2001)
[20] Kunegis, J.: Konect: The Koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343-1350. ACM (2013)
[21] Mason, D.: Laws of large numbers for sums of extreme values. Ann. Probab. 10, 754-764 (1982) · Zbl 0493.60039 · doi:10.1214/aop/1176993783
[22] Mason, D., Turova, T.: Weak convergence of the Hill estimator process. In: Galambos, J., Lechner, J., Simiu, E. (eds.) Extreme Value Theory and Applications, pp 419-432. Kluwer Academic Publishers, Dordrecht (1994)
[23] Oliveira, R., Spencer, J.: Connectivity transitions in networks with superlinear preferential attachment. Internet Math. 2(2), 121-163 (2005) · Zbl 1097.68016 · doi:10.1080/15427951.2005.10129101
[24] Resnick, S.I.: Extreme Values, Regular Variation and Point Processes. Springer, New York (1987) · Zbl 0633.60001 · doi:10.1007/978-0-387-75953-1
[25] Resnick, S.I.: Adventures in Stochastic Processes. Birkhäuser, Boston (1992) · Zbl 0762.60002
[26] Resnick, S.I.: Heavy Tail Phenomena: Probabilistic and Statistical Modeling. Springer Series in Operations Research and Financial Engineering. Springer, New York (2007). ISBN: 0-387-24272-4
[27] Resnick, S.I., Samorodnitsky, G.: Tauberian theory for multivariate regularly varying distributions with application to preferential attachment networks. Extremes 18(3), 349-367 (2015). https://doi.org/10.1007/s10687-015-0216-2 · Zbl 1345.60118 · doi:10.1007/s10687-015-0216-2
[28] Resnick, S.I., Samorodnitsky, G.: Asymptotic normality of degree counts in a preferential attachment model. Adv. Appl. Probab. 48, 283-299, 7 (2016). https://doi.org/10.1017/apr.2016.56. ISSN 1475-6064 · Zbl 1426.05152 · doi:10.1017/apr.2016.56
[29] Resnick, S.I., Stărică, C.: Consistency of Hill’s estimator for dependent data. J. Appl. Probab. 32(1), 139-167 (1995). ISSN 0021-9002 · Zbl 0836.60020 · doi:10.2307/3214926
[30] Resnick, S.I., Stărică, C.: Tail index estimation for dependent data. Ann. Appl. Probab. 8(4), 1156-1183 (1998). ISSN 1050-5164 · Zbl 0942.60037 · doi:10.1214/aoap/1028903376
[31] Rootzén, H, Leadbetter, M.R., de Haan, L.: Tail and quantile estimation for strongly mixing stationary sequences. Technical Report 292, Center for Stochastic Processes, Department of Statistics, University of North Carolina, Chapel Hill, NC, pp. 27599-3260 (1990)
[32] Ross, N.: Power laws in preferential attachment graphs and Stein’s method for the negative binomial distribution. Adv. Appl. Probab. 45(3), 876-893 (2013) · Zbl 1273.05205 · doi:10.1239/aap/1377868543
[33] Rudas, A., Tóth, B., Valkó, B.: Random trees and general branching processes. Random Struct. Algor. 31(2), 186-202 (2007) · Zbl 1144.60051 · doi:10.1002/rsa.20137
[34] Samorodnitsky, G., Resnick, S., Towsley, D., Davis, R., Willis, A., Wan, P.: Nonstandard regular variation of in-degree and out-degree in the preferential attachment model. J. Appl. Probab. 53(1), 146-161 (2016) · Zbl 1343.60138 · doi:10.1017/jpr.2015.15
[35] Tavaré, S.: The birth process with immigration, and the genealogical structure of large populations. J. Math. Biol. 25(2), 161-168 (1987) · Zbl 0625.92010 · doi:10.1007/BF00276387
[36] van der Hofstad, R.: Random Graphs and Complex Networks, vol. 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2017). ISBN 978-1-107-17287-6 · Zbl 1361.05002 · doi:10.1017/9781316779422
[37] Wan, P., Wang, T., Davis, R.A., Resnick, S.I.: Fitting the linear preferential attachment model. Electron. J. Statist. 11(2), 3738-3780 (2017). https://doi.org/10.1214/17-EJS1327. ISSN 1935-7524 · Zbl 1387.62074 · doi:10.1214/17-EJS1327
[38] Wan, P., Wang, T., Davis, R.A., Resnick, S.I.: Are extreme value estimation methods useful for network data? Submitted (2017) · Zbl 1460.62085
[39] Wang, T., Resnick, S.I.: Multivariate regular variation of discrete mass functions with applications to preferential attachment networks. Methodol. Comput. Appl. Probab., 1-14. ISSN 1573-7713. https://doi.org/10.1007/s11009-016-9503-x (2016)
[40] Wang, T., Resnick, S.I.: Asymptotic normality of in- and out-degree counts in a preferential attachment model. Stoch. Model. 33(2), 229-255 (2017). https://doi.org/10.1080/15326349.2016.1256219 · Zbl 1367.05091 · doi:10.1080/15326349.2016.1256219
[41] Waugh, W.A.O’N.: Transformation of a birth process into a Poisson process. J. Roy. Statist. Soc. Ser. B 32, 418-431 (1970). ISSN 0035-9246. http://links.jstor.org/sici?sici=0035-9246(1970)32:3<418:TOABPI>2.0.CO;2-A&origin=MSN · Zbl 0219.60067
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.