Spectral distributions of adjacency and Laplacian matrices of random graphs

DOI10.1214/10-AAP677MaRDI QIDQ614116zbMATH OpenFDO

Authors Xue Ding, Tiefeng Jiang

Publication date 27 December 2010

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.2608

zbMATH Keywords

adjacency matrixfree convolutionLaplacian matrixlargest eigenvaluerandom graphrandom matrixsemi-circle lawspectral distribution

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Convergence of probability measures (60B10)

Abstract: In this paper, 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.

Recommendations

• Empirical distributions of Laplacian matrices of large dilute random graphs
• Low eigenvalues of Laplacian matrices of large random graphs
• A spectral analysis of the normalized Laplacian matrix in random graphs
• Empirical spectral distributions of sparse random graphs
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs

Cites work

• A numerical study of sparse random matrices
• Aging of spherical spin glasses
• Asymptotic distributions of the signal-to-interference ratio of LMMSE detection in multiuser communications
• Collective dynamics of `small-world' networks
• Complex graphs and networks
• Density of states of sparse random matrices
• Deviation Inequalities on Largest Eigenvalues
• Discrete Schrödinger operators and topology
• Eigenvalue distribution of large weighted random graphs
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 5278585 (Why is no real title available?)
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3723610 (Why is no real title available?)
• scientific article; zbMATH DE number 3745227 (Why is no real title available?)
• scientific article; zbMATH DE number 193660 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 1219775 (Why is no real title available?)
• scientific article; zbMATH DE number 1231233 (Why is no real title available?)
• scientific article; zbMATH DE number 1347881 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Large deviations for eigenvalues of sample covariance matrices, with applications to mobile communication systems
• Large deviations of the maximum eigenvalue in Wishart random matrices
• On the asymptotic distribution of the eigenvalues of random matrices
• On the distribution of the roots of certain symmetric matrices
• On the strength of connectedness of a random graph
• On Wigner's semicircle law for the eigenvalues of random matrices
• Random graph dynamics
• Random incidence matrices: moments of the spectral density
• Real Analysis and Probability
• Spectral analysis of large dimensional random matrices
• Spectral measure of large random Hankel, Markov and Toeplitz matrices
• The eigenvalues of random symmetric matrices
• The expected eigenvalue distribution of a large regular graph
• The Largest Eigenvalue of Sparse Random Graphs
• Universality of level correlation function of sparse random matrices

Cited in

(61)

• Correlation between graphs with an application to brain network analysis
• Turing instability in reaction-diffusion models on complex networks
• Eigenvalue location in graphs of small clique-width
• Random Laplacian matrices and convex relaxations
• Empirical spectral distributions of sparse random graphs
• Proof of a conjecture on the infinite dimension limit of a unifying model for random matrix theory
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• On asymptotic properties of Bell polynomials and concentration of vertex degree of large random graphs
• Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices
• Brouwer's conjecture holds asymptotically almost surely
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• On the spectra of general random mixed graphs
• Asymptotic values of four Laplacian-type energies for matrices with degree-distance-based entries of random graphs
• Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit
• Measuring edge importance: a quantitative analysis of the stochastic shielding approximation for random processes on graphs
• On some spectral properties of large block Laplacian random matrices
• Random matrix theory in statistics: a review
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• The spectra of random mixed graphs
• The evolution of beliefs over signed social networks
• Empirical distributions of Laplacian matrices of large dilute random graphs
• Spectral properties of unimodular lattice triangulations
• Loose Laplacian spectra of random hypergraphs
• The limiting distributions of large heavy Wigner and arbitrary random matrices
• Spectra of edge-independent random graphs
• Graph connection Laplacian and random matrices with random blocks
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• Eigenvalue distribution of large weighted random graphs
• Eigenvalue distribution of a large weighted bipartite random graph
• scientific article; zbMATH DE number 7626709 (Why is no real title available?)
• Spectral properties for the Laplacian of a generalized Wigner matrix
• The spectral distribution of random mixed graphs
• Spectral bounds in random graphs applied to spreading phenomena and percolation
• A spectral analysis of the normalized Laplacian matrix in random graphs
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
• Random incidence matrices: moments of the spectral density
• On the normalized Laplacian spectra of random geometric graphs
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• On the limiting spectral distributions of stochastic block models
• The skew spectral radius and skew Randić spectral radius of general random oriented graphs
• Limiting spectral distribution of stochastic block model
• Spectrum of Lévy-Khintchine random Laplacian matrices
• On the spectra of general random graphs
• Induced synchronization by endogenous noise modulation in finite-size random neural networks: a stochastic mean-field study
• Extreme eigenvalues of Laplacian random matrices with Gaussian entries (with an appendix by Santiago Arenas-Velilla and Victor Perez-Abreu)
• Average-case optimization analysis for distributed consensus algorithms on regular graphs
• Random line graphs and edge-attributed network inference
• Central limit theorem for linear eigenvalue statistics of the adjacency matrices of random simplicial complexes
• Hammerstein equations for sparse random matrices
• Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs
• Low eigenvalues of Laplacian matrices of large random graphs
• Spectra of large random trees
• Labeled graph rearrangements on matched and star products
• Concentration of the adjacency matrix and of the normalized Laplacian matrix in general random signed graphs
• The spectrum estimates for random graphs with given expected degrees
• Spectral analysis of normalized Hermitian Laplacian matrices in random mixed graphs
• Noisy random graphs and their laplacians
• Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices

This page was built for publication: Spectral distributions of adjacency and Laplacian matrices of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q614116)