×

zbMATH — the first resource for mathematics

A limit theorem for scaled eigenvectors of random dot product graphs. (English) Zbl 1338.62061
Summary: We prove a central limit theorem for the components of the largest eigenvectors of the adjacency matrix of a finite-dimensional random dot product graph whose true latent positions are unknown. We use the spectral embedding of the adjacency matrix to construct consistent estimates for the latent positions, and we show that the appropriately scaled differences between the estimated and true latent positions converge to a mixture of Gaussian random variables. We state several corollaries, including an alternate proof of a central limit theorem for the first eigenvector of the adjacency matrix of an Erdős-Rényi random graph.

MSC:
62E20 Asymptotic distribution theory in statistics
05C80 Random graphs (graph-theoretic aspects)
60F05 Central limit and other weak theorems
Software:
mclust
PDF BibTeX Cite
Full Text: DOI
References:
[1] Aldous, DJ, Representations for partially exchangeable arrays of random variables, J. Multivariate. Anal., 11, 581-598, (1981) · Zbl 0474.60044
[2] Bickel, PJ; Chen, A, A nonparametric view of network models and Newman-girvan and other modularities, Proc. Natl. Acad. Sci. USA, 106, 068-73, (2009) · Zbl 1359.62411
[3] Bickel, PJ; Chen, A; Levina, E, The method of moments and degree distributions for network models, Ann. Statist., 39, 38-59, (2011) · Zbl 1232.91577
[4] Choi, DS; Wolfe, PJ; Airoldi, EM, Stochastic blockmodels with a growing number of classes, Biometrika, 99, 273-284, (2012) · Zbl 1318.62207
[5] Chung, F.R.K. (1997). Spectral Graph Theory. American Mathematical Society. · Zbl 0867.05046
[6] Diaconis, P; Janson, S, Graph limits and exchangeable random graphs, Rend. Mat. Appl., 28, 33-61, (2008) · Zbl 1162.60009
[7] Fiedler, M, Algebraic connectivity of graphs, Czechoslovak Math. J, 23, 298-305, (1973) · Zbl 0265.05119
[8] Fishkind, DE; Sussman, DL; Tang, M; Vogelstein, JT; Priebe, CE, Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown, SIAM J. Matrix Anal. Appl., 34, 23-39, (2013) · Zbl 1314.05186
[9] Fortunato, S, Community detection in graphs, Phys. Rep., 486, 75-174, (2010)
[10] Fraley, C; Raftery, AE, MCLUST: software for model-based cluster analysis, J. Classif., 16, 297-306, (1999) · Zbl 0951.91500
[11] Füredi, Z; Komlós, J, The eigenvalues of random symmetric matrices, Combinatorica, 1, 233-241, (1981) · Zbl 0494.15010
[12] Goldenberg, A; Zheng, AX; Fienberg, SE; Airoldi, EM, A survey of statistical network models, Foundations and Trends®; in Machine Learning, 2, 129-233, (2010) · Zbl 1184.68030
[13] Hoff, PD; Raftery, AE; Handcock, MS, Latent space approaches to social network analysis, J. Am. Statist. Assoc., 97, 1090-1098, (2002) · Zbl 1041.62098
[14] Hoover, D.N. (1979). Relations on probability spaces and arrays of random variables. Tech. rep. Institute for Advanced Study.
[15] Janson, S, The first eigenvalue of random graphs, Comb. Probab. Comput., 14, 815-828, (2005) · Zbl 1077.05092
[16] Knowles, A. and Yin, J. (2011). Eigenvector distribution of Wigner matrices. Probab. Theory Related Fields, 1-40. · Zbl 1318.62207
[17] Krivelevich, M; Sudakov, B, The largest eigenvalue of sparse random graphs, Comb. Probab. Comput., 12, 61-72, (2003) · Zbl 1012.05109
[18] Luxburg, UV, A tutorial on spectral clustering, Stat. Comput., 17, 395-416, (2007)
[19] Marchette, D., Priebe, C.E. and Coppersmith, G. (2011). Vertex nomination via attributed random dot product graphs. In Proceedings of the 57th ISI World Statistic Congress. · Zbl 1077.05092
[20] Oliveira, R.I. (2010). Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. arXiv:preprint. · Zbl 1273.62147
[21] Rohe, K; Chatterjee, S; Yu, B, Spectral clustering and the high-dimensional stochastic blockmodel, Ann. Statist., 39, 1878-1915, (2011) · Zbl 1227.62042
[22] Sarkar, P; Bickel, PJ, Role of normalization in spectral clustering for stochastic blockmodels, Ann. Statist., 43, 962-990, (2015) · Zbl 1320.62150
[23] Silverstein, JW, The spectral radii and norms of large-dimensional non-central random matrices, Comm. Statist. Stochastic Models, 10, 525-532, (1994) · Zbl 0806.15018
[24] Sussman, D.L. (2014). Foundations of Adjacency Spectral Embedding. PhD Thesis, Johns Hopkins University. · Zbl 1452.62214
[25] Sussman, DL; Tang, M; Fishkind, DE; Priebe, CE, A consistent adjacency spectral embedding for stochastic blockmodel graphs, J. Am. Statist. Assoc, 107, 1119-1128, (2012) · Zbl 1443.62188
[26] Sussman, DL; Tang, M; Priebe, CE, Consistent latent position estimation and vertex classification for random dot product graphs, IEEE T. Pattern. Anal., 36, 48-57, (2014)
[27] Tang, M; Sussman, DL; Priebe, CE, Universally consistent vertex classification for latent position graphs, Ann. Statist., 41, 1406-1430, (2013) · Zbl 1273.62147
[28] Tao, T. and Vu, V. (2012). Random matrices: Universal properties of eigenvectors. Random Matrices: Theory and Applications 1. · Zbl 1248.15031
[29] Tropp, JA, Freedmans inequality for matrix martingales, Electron. Commun. Probab., 16, 262-270, (2011) · Zbl 1225.60017
[30] Yan, T; Xu, J, A central limit thereom in the ß-model for undirected random graphs with a diverging number of vertices, Biometrika, 100, 519-524, (2013) · Zbl 1452.62214
[31] Young, S. and Scheinerman, E. (2007). Random dot product graph models for social networks. In Algorithms and models for the web-graph. Springer, p. 138-149. · Zbl 1136.05322
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.