Random matrices with row constraints and eigenvalue distributions of graph Laplacians

Abstract

Symmetric matrices with zero row sums occur in many theoretical settings and in real-life applications. When the offdiagonal elements of such matrices are i.i.d. random variables and the matrices are large, the eigenvalue distributions converge to a peculiar universal curve $p_{\mathrm{zrs}}(\lambda )$ that looks like a cross between the Wigner semicircle and a Gaussian distribution. An analytic theory for this curve, originally due to Fyodorov, can be developed using supersymmetry-based techniques. We extend these derivations to the case of sparse matrices, including the important case of graph Laplacians for large random graphs with $N$ vertices of mean degree $c$. In the regime $1\ll c\ll N$, the eigenvalue distribution of the ordinary graph Laplacian (diffusion with a fixed transition rate per edge) tends to a shifted and scaled version of $p_{\mathrm{zrs}}(\lambda )$, centered at $c$ with width $\sim \sqrt{c}$. At smaller $c$, this curve receives corrections in powers of $1/\sqrt{c}$ accurately captured by our theory. For the normalized graph Laplacian (diffusion with a fixed transition rate per vertex), the large $c$ limit is a shifted and scaled Wigner semicircle, again with corrections captured by our analysis.

v3: clarifications and references added, accepted for publication in J. Phys. A

References in corpus (9)

• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• Spherical harmonics and integration in superspace
• The spectral dimension of simplicial complexes: a renormalization group theory
• Random generators of Markovian evolution: A quantum-classical transition by superdecoherence
• Integration of Grassmann variables over invariant functions on flat superspaces
• On the Efetov-Wegner terms by diagonalizing a Hermitian supermatrix
• Random sparse generators of Markovian evolution and their spectral properties

Cited by in corpus (11)

• Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
• Spectral properties, localization transition and multifractal eigenvectors of the Laplacian on heterogeneous networks
• Spectral properties of Levy Rosenzweig-Porter model via supersymmetric approach
• Random sparse generators of Markovian evolution and their spectral properties
• Hammerstein equations for sparse random matrices
• A Gaussian integral that counts regular graphs
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• A path integral approach to sparse non-Hermitian random matrices
• First return times on sparse random graphs
• Statistical field theory of random graphs with prescribed degrees
• Analytic and numerical toolkit for the Anderson model in one dimension