×

On the spectra of general random mixed graphs. (English) Zbl 1468.05156

In this paper, the authors study the spectra of the Hermitian adjacency matrix and the normalized Hermitian Laplacian matrix of general random mixed graphs. They derive a new probability inequality and apply it to obtain an upper bound on the eigenvalues of the Hermitian adjacency matrix. Moreover, another main result shows that the eigenvalues of the normalized Hermitian Laplacian matrix can be approximated by the eigenvalues of a closely related weighted expectation matrix, with error bounds depending on the minimum expected degree of the underlying undirected graph.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. IEEE Trans. Inform. Theory,48(3) (2002), 569-579. · Zbl 1071.94530
[2] N. Alon, M. Krivelevich, and V. H. Vu. Concentration of eigenvalues of random matrices.Israel Math. J.,131(2002), 259-267. · Zbl 1014.15016
[3] R. Bhatia.Matrix Analysis, Graduate Texts in Mathematics, vol. 169, Springer, Berlin, 1997, p.10. · Zbl 0863.15001
[4] R. Bhatia.Positive Definite Matrices, Princeton Univ. Press, Princeton, 2007. · Zbl 1133.15017
[5] F. Chung.Spectral graph theory, AMS publications, 1997. · Zbl 0867.05046
[6] F. Chung, L. Lu, and V. H. Vu. Eigenvalues of random power law graphs.Ann. Combin.,7(2003), 21-33. · Zbl 1017.05093
[7] F. Chung, L. Lu, and V. H. Vu. Spectra of random graphs with given expected degrees.Proc. Nat. Acad. Sci. USA,100(11) (2003), 6313-6318. · Zbl 1064.05138
[8] F. Chung and M. Radcliffe. On the spectra of general random graphs.Electron. J. Combin.,18(2011), #P215. · Zbl 1229.05248
[9] A. Coja-Oghlan. On the Laplacian eigenvalues ofG(n, p).Combin. Probab. Comput., 16(2007), 923-946. · Zbl 1127.05062
[10] A. Coja-Oghlan and A. Lanka. The spectral gap of random graphs with given expected degrees.Electron. J. Combin.,16(2009), #R138. · Zbl 1187.05048
[11] D. Cristofides and K. Markstr¨om. Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales.Random Struct. Alg.,32(2008), 88-100. · Zbl 1130.05030
[12] D. M. Cvetkovi´c, M. Doob, and H. Sachs.Spectra of Graphs, Theory and Applications, Academic Press, 1980.
[13] X. Ding and T. Jiang. Spectral distributions of adjacency and Laplacian matrices of random graphs.Ann. Appl. Probab.,20(2010), 2086-2117. · Zbl 1231.05236
[14] U. Feige and E. Ofek. Spectral techniques applied to sparse random graphs.Random Struct. Alg.,27(2) (2005), 251-275. · Zbl 1076.05073
[15] J. Friedman.A Proof of Alon’s Second Eigenvalue Conjecture and Related Problem, Memoirs of the American Mathematical Society 2008, 100 pp. · Zbl 1177.05070
[16] J. Friedman. On the second eigenvalue and random walks in randomd-regular graphs. Combinatorica,11(4) (1991), 331-362. · Zbl 0760.05078
[17] J. Friedman, J. Kahn, and E. Szemer´edi. On the second eigenvalue in random regular graphs, inProc. 21st ACM Symp. Theory of Computing, 1989, 587-598.
[18] Z. F¨uredi and J. Koml´os. The eigenvalues of random symmetric matrices.Combinatorica,1(3) 1981, 233-241. · Zbl 0494.15010
[19] D. Gross. Recovering low-rank matrices from few coefficients in any basis.IEEE Trans. Inform. Theory,57(2011), 1548-1566. · Zbl 1366.94103
[20] K. Guo and B. Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. J. Graph Theory,85(2017), no. 1, 217-248. · Zbl 1365.05173
[21] R. A. Horn and C. R. Johnson.Matrix Analysis, 2nd, Cambridge University Press, 2012.
[22] M. Krivelevich and B. Sudakov. The largest eigenvalue of sparse random graphs. Combin. Probab. Comput.,12(2003), 61-72. · Zbl 1012.05109
[23] J. Liu and X. Li. Hermitian-adjacency matrices and Hermitian energies of mixed graphs.Linear. Algebra. Appl.,466(2015) 182-207. · Zbl 1302.05106
[24] L. Lu and X. Peng. Loose Laplacian spectra of random hypergraphs.Random Struct. Alg.,41(2012), no. 4, 521-545. · Zbl 1255.05116
[25] L. Lu and X. Peng. Spectra of edge-independent random graphs.Electron. J. Combin.,20(4) (2013), #P27. · Zbl 1295.05211
[26] R. Oliveira. Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges.arXiv:0911.0600, 2009.
[27] D. Petz. A survey of certain trace inequalities, inFunctional Analysis and Operator Theory, Banach Center Publications, vol. 30(Polish Acad. Sci., Warsaw, 1994), pp. 287-298. · Zbl 0802.15012
[28] B. Recht. Simpler approach to matrix completion.J. Mach. Learn. Res.,12(2011), 3413-3430. · Zbl 1280.68141
[29] J. Tropp. User-friendly tail bounds for sums of random matrices.Found. Comput. Math.,12(2012), 389-434. · Zbl 1259.60008
[30] H. Weyl.Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen.Math. Ann.,71(2010), 441-479. · JFM 43.0436.01
[31] F.
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.