Spectrum of Markov generators on sparse random graphs
From MaRDI portal
Abstract: We investigate the spectrum of the infinitesimal generator of the continuous time random walk on a randomly weighted oriented graph. This is the non-Hermitian random nxn matrix L defined by L(j,k)=X(j,k) if k<>j and L(j,j)=-sum(L(j,k),k<>j), where X(j,k) are i.i.d. random weights. Under mild assumptions on the law of the weights, we establish convergence as n tends to infinity of the empirical spectral distribution of L after centering and rescaling. In particular, our assumptions include sparse random graphs such as the oriented Erd"os-R'enyi graph where each edge is present independently with probability p(n)->0 as long as np(n) >> (log(n))^6. The limiting distribution is characterized as an additive Gaussian deformation of the standard circular law. In free probability terms, this coincides with the Brown measure of the free sum of the circular element and a normal operator with Gaussian spectral measure. The density of the limiting distribution is analyzed using a subordination formula. Furthermore, we study the convergence of the invariant measure of L to the uniform distribution and establish estimates on the extremal eigenvalues of L.
Recommendations
- Empirical spectral distributions of sparse random graphs
- Spectra of large diluted but bushy random graphs
- Spectral radii of sparse random matrices
- Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
- Empirical distributions of Laplacian matrices of large dilute random graphs
Cites work
- Around the circular law
- Asymptotic freeness by generalized moments for Gaussian and Wishart matrices. Application to beta random matrices
- Brown measures of unbounded operators affiliated with a finite von Neumann algebra
- Brown's spectral distribution measure for \(R\)-diagonal elements in finite von Neumann algebras
- Circular law for noncentral random matrices
- Circular law for random matrices with unconditional log-concave distribution
- Circular law theorem for random Markov matrices
- Computation of some examples of Brown's spectral measure in free probability
- Concentration of the spectral measure of large Wishart matrices with dependent entries
- Eigenvalues and singular values of certain random matrices
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- scientific article; zbMATH DE number 3171472 (Why is no real title available?)
- scientific article; zbMATH DE number 3719745 (Why is no real title available?)
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- scientific article; zbMATH DE number 1436291 (Why is no real title available?)
- Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
- Non-hermitian random matrix theory: Method of hermitian reduction
- On the free convolution with a semi-circular distribution
- On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
- RANDOM MATRICES: THE CIRCULAR LAW
- Random matrices: universality of ESDs and the circular law
- Smallest singular value of random matrices and geometry of random polytopes
- Spectral measure of large random Hankel, Markov and Toeplitz matrices
- Spectral norm of random matrices
- Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
- Spectrum of non-Hermitian heavy tailed random matrices
- Stationary distribution and cover time of random walks on random digraphs
- The circular law for random matrices
- The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
- The eigenvalues of random symmetric matrices
- The Littlewood-Offord problem and invertibility of random matrices
- The spectral radii and norms of large dimensional non-central random atrices matrices
- Universal sum and product rules for random matrices
- Universality and the circular law for sparse random matrices
Cited in
(25)- Circular law for the sum of random permutation matrices
- Spectrum of heavy-tailed elliptic random matrices
- The circular law for sparse non-Hermitian matrices
- Circular law for random matrices with exchangeable entries
- Outlier eigenvalues for deformed i.i.d. random matrices
- scientific article; zbMATH DE number 1421105 (Why is no real title available?)
- Spectral properties for the Laplacian of a generalized Wigner matrix
- Circular law for random matrices with unconditional log-concave distribution
- Asymptotic spectral analysis of generalized Erdős-Rényi random graphs
- Random Lindblad dynamics
- From Boltzmann to random matrices and beyond
- Random matrices with row constraints and eigenvalue distributions of graph Laplacians
- The Brown measure of a sum of two free random variables, one of which is triangular elliptic
- Random Lindblad Operators Obeying Detailed Balance
- Spectrum of Lévy-Khintchine random Laplacian matrices
- Wegner estimate and upper bound on the eigenvalue condition number of non-Hermitian random matrices
- Deformed single ring theorems
- Brown measure of the sum of an elliptic operator and a free random variable in a finite von Neumann algebra
- Bulk universality for deformed GinUEs
- Limiting eigenvalue distribution of the general deformed Ginibre ensemble
- Density of Brown measure of free circular Brownian motion
- Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
- Repeated erfc statistics for deformed GinUEs
- Brown measures of deformed L^-valued circular elements
- Spectrum of Laplacian matrices associated with large random elliptic matrices
This page was built for publication: Spectrum of Markov generators on sparse random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5413960)
