×

zbMATH — the first resource for mathematics

Spectral distributions of adjacency and Laplacian matrices of random graphs. (English) Zbl 1231.05236
Summary: We investigate the spectral properties of the adjacency and the Laplacian matrices of random graphs. We prove that:
(i)
the law of large numbers for the spectral norms and the largest eigenvalues of the adjacency and the Laplacian matrices;
(ii)
under some further independent conditions, the normalized largest eigenvalues of the Laplacian matrices are dense in a compact interval almost surely;
(iii)
the empirical distributions of the eigenvalues of the Laplacian matrices converge weakly to the free convolution of the standard Gaussian distribution and the Wigner’s semi-circular law;
(iv)
the empirical distributions of the eigenvalues of the adjacency matrices converge weakly to the Wigner’s semi-circular law.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
60B10 Convergence of probability measures
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Arnold, L. (1967). On the asymptotic distribution of the eigenvalues of random matrices. J. Math. Anal. Appl. 20 262-268. · Zbl 0246.60029 · doi:10.1016/0022-247X(67)90089-3
[2] Arnold, L. (1971). On Wigner’s semicircle law for the eigenvalues of random matrices. Z. Wahrsch. Verw. Gebiete 19 191-198. · Zbl 0212.51006 · doi:10.1007/BF00534107
[3] 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
[4] Bai, Z. and Zhou, W. (2008). Large sample covariance matrices without independence structures in columns. Statist. Sinica 18 425-442. · Zbl 1135.62009 · www3.stat.sinica.edu.tw
[5] Bai, Z. D. and Silverstein, J. (2009). Spectral Analysis of Large Dimensional Random Matrices , 2nd ed. Springer. · Zbl 1301.60002
[6] Bai, Z. D. (1999). Methodologies in spectral analysis of large-dimensional random matrices, a review. Statist. Sinica 9 611-677. · Zbl 0949.60077
[7] Bauer, M. and Golinelli, O. (2001). Random incidence matrices: Moments of the spectral density. J. Stat. Phys. 103 301-337. · Zbl 0999.82035 · doi:10.1023/A:1004879905284
[8] Ben Arous, G., Dembo, A. and Guionnet, A. (2001). Aging of spherical spin glasses. Probab. Theory Related Fields 120 1-67. · Zbl 0993.60055 · doi:10.1007/s004400000115
[9] Biggs, N. L., Lloyd, E. K. and Wilson, R. J. (1976). Graph Theory : 1736-1936. Clarendon, Oxford.
[10] Bollobás, B. (1985). Random Graphs . Academic Press, London. · Zbl 0567.05042
[11] Bollobás, B. (1979). Graph Theory : An Introductory Course. Graduate Texts in Mathematics 63 . Springer, New York. · Zbl 0411.05032
[12] Bryc, W., Dembo, A. and Jiang, T. (2006). Spectral measure of large random Hankel, Markov and Toeplitz matrices. Ann. Probab. 34 1-38. · Zbl 1094.15009 · doi:10.1214/009117905000000495
[13] Chow, Y. S. and Teicher, H. (1988). Probability Theory , Independence , Interchangeability , Martingales , 2nd ed. Springer, New York. · Zbl 0652.60001
[14] Chung, F. R. K. (1997). Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92 . Conf. Board Math. Sci., Washington, DC. · Zbl 0867.05046
[15] Chung, F. and Lu, L. (2006). Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics 107 . Conf. Board Math. Sci., Washington, DC. · Zbl 1114.90071
[16] Colin de Verdière, Y. (1998). Spectres de Graphes. Cours Spécialisés [ Specialized Courses ] 4 . Société Mathématique de France, Paris. · Zbl 0913.05071
[17] Dudley, R. M. (2002). Real Analysis and Probability. Cambridge Studies in Advanced Mathematics 74 . Cambridge Univ. Press, Cambridge. · Zbl 1023.60001
[18] Durrett, R. (2007). Random Graph Dynamics . Cambridge Univ. Press, Cambridge. · Zbl 1116.05001
[19] Erdös, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6 290-297. · Zbl 0092.15705
[20] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17-61. · Zbl 0103.16301
[21] Erdös, P. and Rényi, A. (1961). On the evolution of random graphs. Bull. Inst. Internat. Statist. 38 343-347. · Zbl 0106.12006
[22] Erdös, P. and Rényi, A. (1961). On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. 12 261-267. · Zbl 0103.16302 · doi:10.1007/BF02066689
[23] Erdős, P. and Spencer, J. (1974). Probabilistic Methods in Combinatorics . Academic Press, New York. · Zbl 0308.05001
[24] Evangelou, S. N. (1992). A numerical study of sparse random matrices. J. Stat. Phys. 69 361-383. · Zbl 0888.65046 · doi:10.1007/BF01053797
[25] Evangelou, S. N. and Economou, E. N. (1992). Spectral density singularities, level statistics, and localization in sparse random matrices. Phys. Rev. Lett. 68 361-364.
[26] Evangelou, S. N. (1983). Quantum percolation and the Anderson transition in dilute systems. Phys. Rev. B 27 1397-1400.
[27] Fey, A., Hofstad, R. and Klok, M. (2008). Large deviations for eigenvalues of sample covariance matrices, with applications to mobile communication systems. Adv. in Appl. Probab. 40 1048-1071. · Zbl 1255.60039 · doi:10.1239/aap/1231340164
[28] Füredi, Z. and Komlós, J. (1981). The eigenvalues of random symmetric matrices. Combinatorica 1 233-241. · Zbl 0494.15010 · doi:10.1007/BF02579329
[29] Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application . Academic Press [Harcourt Brace Jovanovich Publishers], New York. · Zbl 0462.60045
[30] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York.
[31] Juhász, F. (1981). On the spectrum of a random graph. In Algebraic Methods in Graph Theory , Vol. I , II ( Szeged , 1978). Colloquia Mathematica Societatis János Bolyai 25 313-316. North-Holland, Amsterdam. · Zbl 0475.05060
[32] Khorunzhy, O., Shcherbina, M. and Vengerovsky, V. (2004). Eigenvalue distribution of large weighted random graphs. J. Math. Phys. 45 1648-1672. · Zbl 1068.05062 · doi:10.1063/1.1667610
[33] Khorunzhy, A., Khoruzhenko, B., Pastur, L. and Shcherbina, M. (1992). The Large n-Limit in Statistical Mechanics and the Spectral Theory of Disordered Systems. Phase Transition and Critical Phenomenon 15 73. Academic Press, New York.
[34] Kolchin, V. F. (1999). Random Graphs. Encyclopedia of Mathematics and Its Applications 53 . Cambridge Univ. Press, Cambridge. · Zbl 0918.05001
[35] Krivelevich, M. and Sudakov, B. (2003). The largest eigenvalue of sparse random graphs. Combin. Probab. Comput. 12 61-72. · Zbl 1012.05109 · doi:10.1017/S0963548302005424
[36] Ledoux, M. (2007). Deviation inequalities on largest eigenvalues. In Geometric Aspects of Functional Analysis. Lecture Notes in Math. 1910 167-219. Springer, Berlin. · Zbl 1130.15012 · doi:10.1007/978-3-540-72053-9_10
[37] McKay, B. D. (1981). The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40 203-216. · Zbl 0468.05039 · doi:10.1016/0024-3795(81)90150-6
[38] Mirlin, A. D. and Fyodorov, Y. V. (1991). Universality of level correlation function of sparse random matrices. J. Phys. A 24 2273-2286. · Zbl 0760.15017 · doi:10.1088/0305-4470/24/10/016
[39] Novikov, S. P. (1998). Schrödinger operators on graphs and symplectic geometry. In The Arnoldfest 2 . Field Institute, Toronto. · Zbl 0991.47016
[40] Palmer, E. M. (1985). Graphical Evolution : An Introduction to the Theory of Random Graphs . Wiley, Chichester. · Zbl 0566.05002
[41] Pan, G.-M., Guo, M.-H. and Zhou, W. (2007). Asymptotic distributions of the signal-to-interference ratios of LMMSE detection in multiuser communications. Ann. Appl. Probab. 17 181-206. · Zbl 1221.15055 · doi:10.1214/105051606000000718
[42] Puppe, T. (2008). Spectral Graph Drawing : A Survey . VDM, Verlag.
[43] Rodgers, G. J. and Bray, A. J. (1988). Density of states of a sparse random matrix. Phys. Rev. B (3) 37 3557-3562. · doi:10.1103/PhysRevB.37.3557
[44] Rodgers, G. J. and De Dominicis, C. (1990). Density of states of sparse random matrices. J. Phys. A 23 1567-1573. · Zbl 0703.60106 · doi:10.1088/0305-4470/23/9/019
[45] Vivo, P., Majumdar, S. N. and Bohigas, O. (2007). Large deviations of the maximum eigenvalue in Wishart random matrices. J. Phys. A 40 4317-4337. · Zbl 1115.15019 · doi:10.1088/1751-8113/40/16/005
[46] Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature 393 440-442. · Zbl 1368.05139
[47] Wigner, E. P. (1958). On the distribution of the roots of certain symmetric matrices. Ann. of Math. (2) 67 325-327. JSTOR: · Zbl 0085.13203 · doi:10.2307/1970008 · links.jstor.org
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.