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:
mclustReferences:
| [1] | Aldous, D.J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivariate. Anal.11, 581-598. · Zbl 0474.60044 · doi:10.1016/0047-259X(81)90099-3 |
| [2] | Bickel, P.J. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA106, 21, 068-73. · Zbl 1359.62411 |
| [3] | Bickel, P.J., Chen, A. and Levina E. (2011). The method of moments and degree distributions for network models. Ann. Statist.39, 38-59. · Zbl 1232.91577 · doi:10.1214/11-AOS904 |
| [4] | Choi, D.S., Wolfe, P.J. and Airoldi, E.M. (2012). Stochastic blockmodels with a growing number of classes. Biometrika99, 273-284. · Zbl 1318.62207 · doi:10.1093/biomet/asr053 |
| [5] | Chung, F.R.K. (1997). Spectral Graph Theory. American Mathematical Society. · Zbl 0867.05046 |
| [6] | Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl.28, 33-61. · Zbl 1162.60009 |
| [7] | Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Math. J23, 298-305. · Zbl 0265.05119 |
| [8] | Fishkind, D.E., Sussman D.L., Tang, M., Vogelstein, J.T. and Priebe, C.E. (2013). Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown. SIAM J. Matrix Anal. Appl.34, 23- 39. · Zbl 1314.05186 · doi:10.1137/120875600 |
| [9] | Fortunato, S. (2010). Community detection in graphs. Phys. Rep.486, 75-174. · doi:10.1016/j.physrep.2009.11.002 |
| [10] | Fraley, C. and Raftery, A.E. (1999). MCLUST: Software for model-based cluster analysis. J. Classif.16, 297-306. · Zbl 0951.91500 · doi:10.1007/s003579900058 |
| [11] | Füredi, Z. and Komlós, J. (1981). The eigenvalues of random symmetric matrices. Combinatorica1, 233-241. · Zbl 0494.15010 · doi:10.1007/BF02579329 |
| [12] | Goldenberg, A., Zheng A.X., Fienberg, S.E. and Airoldi, E.M. (2010). A survey of statistical network models. Foundations and Trends®; in Machine Learning2, 129-233. · Zbl 1184.68030 · doi:10.1561/2200000005 |
| [13] | Hoff, P.D., Raftery A.E., and Handcock, M.S. (2002). Latent space approaches to social network analysis. J. Am. Statist. Assoc.97, 1090-1098. · Zbl 1041.62098 · doi:10.1198/016214502388618906 |
| [14] | Hoover, D.N. (1979). Relations on probability spaces and arrays of random variables. Tech. rep. Institute for Advanced Study. |
| [15] | Janson, S. (2005). The first eigenvalue of random graphs. Comb. Probab. Comput.14, 815-828. · Zbl 1077.05092 · doi:10.1017/S0963548305007030 |
| [16] | Knowles, A. and Yin, J. (2011). Eigenvector distribution of Wigner matrices. Probab. Theory Related Fields, 1-40. · Zbl 1268.15033 |
| [17] | Krivelevich, M. and Sudakov, B. (2003). The largest eigenvalue of sparse random graphs. Comb. Probab. Comput.12, 61-72. · Zbl 1012.05109 · doi:10.1017/S0963548302005424 |
| [18] | Luxburg, U.V. (2007). A tutorial on spectral clustering. Stat. Comput.17, 395-416. · doi:10.1007/s11222-007-9033-z |
| [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. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist.39, 1878-1915. · Zbl 1227.62042 · doi:10.1214/11-AOS887 |
| [22] | Sarkar, P. and Bickel, P.J. (2015). Role of normalization in spectral clustering for stochastic blockmodels. Ann. Statist.43, 962-990. · Zbl 1320.62150 · doi:10.1214/14-AOS1285 |
| [23] | Silverstein, J.W. (1994). The spectral radii and norms of large-dimensional non-central random matrices. Comm. Statist. Stochastic Models10, 3, 525-532. · Zbl 0806.15018 · doi:10.1080/15326349408807308 |
| [24] | Sussman, D.L. (2014). Foundations of Adjacency Spectral Embedding. PhD Thesis, Johns Hopkins University. · Zbl 1452.62214 |
| [25] | Sussman, D.L., Tang, M., Fishkind, D.E. and Priebe, C.E. (2012). A consistent adjacency spectral embedding for stochastic blockmodel graphs. J. Am. Statist. Assoc107, 1119-1128. · Zbl 1443.62188 · doi:10.1080/01621459.2012.699795 |
| [26] | Sussman, D.L., Tang, M. and Priebe, C.E. (2014). Consistent latent position estimation and vertex classification for random dot product graphs. IEEE T. Pattern. Anal.36, 48-57. · doi:10.1109/TPAMI.2013.135 |
| [27] | Tang, M., Sussman D.L. and Priebe C.E. (2013). Universally consistent vertex classification for latent position graphs. Ann. Statist.41, 1406-1430. · Zbl 1273.62147 · doi:10.1214/13-AOS1112 |
| [28] | Tao, T. and Vu, V. (2012). Random matrices: Universal properties of eigenvectors. Random Matrices: Theory and Applications 1. · Zbl 1248.15031 |
| [29] | Tropp, J.A. (2011). Freedmans inequality for matrix martingales. Electron. Commun. Probab.16, 262-270. · Zbl 1225.60017 · doi:10.1214/ECP.v16-1624 |
| [30] | Yan, T. and Xu, J. (2013). A central limit thereom in the ß-model for undirected random graphs with a diverging number of vertices. Biometrika100, 519-524. · Zbl 1452.62214 · doi:10.1093/biomet/ass084 |
| [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. 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.
