Spectral distributions of adjacency and Laplacian matrices of random graphs

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.

arXiv commentPublished in at http://dx.doi.org/10.1214/10-AAP677 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Emergence of scaling in random networks
• Random incidence matrices: moments of the spectral density
• Large Deviations of the Maximum Eigenvalue in Wishart Random Matrices
• Large deviations for eigenvalues of sample covariance matrices, with applications to mobile communication systems
• Asymptotic distributions of the signal-to-interference ratios of LMMSE detection in multiuser communications

Cited by in corpus (14)

• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• A User Guide to Low-Pass Graph Signal Processing and its Applications
• Turing instability in Reaction-Diffusion models on complex networks
• Network topology near criticality in adaptive epidemics
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• Concentration of the Kirchhoff index for Erdos-Renyi graphs
• The Kato--Temple inequality and eigenvalue concentration with applications to graph inference
• 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
• Hammerstein equations for sparse random matrices
• Spectral density of random graphs: convergence properties and application in model fitting
• Spectral properties of unimodular lattice triangulations
• Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit