Index statistical properties of sparse random graphs

Analytic approach for the number statistics of non-Hermitian random matrices

We introduce a powerful analytic method to study the statistics of the number N_{A}(γ) of eigenvalues inside any smooth Jordan curve γ∈C for infinitely large non-Hermitian random matrices A. Our generic approach can be applied to different random matrix ensembles of a mean-field type, even when the analytic expression for the joint distribution of eigenvalues is not known. We illustrate the method on the adjacency matrices of weighted random graphs with asymmetric couplings, for which standard random-matrix tools are inapplicable, and obtain explicit results for the diluted real Ginibre ensemble. The main outcome is an effective theory that determines the cumulant generating function of N_{A} via a path integral along γ, with the path probability distribution following from the numerical solution of a nonlinear self-consistent equation. We derive expressions for the mean and the variance of N_{A} as well as for the rate function governing rare fluctuations of N_{A}(γ). All theoretical results are compared with direct diagonalization of finite random matrices, exhibiting an excellent agreement.

Theory for the conditioned spectral density of noninvariant random matrices

We develop a theoretical approach to compute the conditioned spectral density of N×N noninvariant random matrices in the limit N→∞. This large deviation observable, defined as the eigenvalue distribution conditioned to have a fixed fraction k of eigenvalues smaller than x∈R, provides the spectrum of random matrix samples that deviate atypically from the average behavior. We apply our theory to sparse random matrices and unveil strikingly different and generic properties, namely, (i) their conditioned spectral density has compact support, (ii) it does not experience any abrupt transition for k around its typical value, and (iii) its eigenvalues do not accumulate at x. Moreover, our work points towards other types of transitions in the conditioned spectral density for values of k away from its typical value. These properties follow from the weak or absent eigenvalue repulsion in sparse ensembles and they are in sharp contrast to those displayed by classic or rotationally invariant random matrices. The exactness of our theoretical findings are confirmed through numerical diagonalization of finite random matrices.

Large-deviation theory for diluted Wishart random matrices

Wishart random matrices with a sparse or diluted structure are ubiquitous in the processing of large datasets, with applications in physics, biology, and economy. In this work, we develop a theory for the eigenvalue fluctuations of diluted Wishart random matrices based on the replica approach of disordered systems. We derive an analytical expression for the cumulant generating function of the number of eigenvalues I_{N}(x) smaller than x∈R^{+}, from which all cumulants of I_{N}(x) and the rate function Ψ_{x}(k) controlling its large-deviation probability Prob[I_{N}(x)=kN]≍e^{-NΨ_{x}(k)} follow. Explicit results for the mean value and the variance of I_{N}(x), its rate function, and its third cumulant are discussed and thoroughly compared to numerical diagonalization, showing very good agreement. The present work establishes the theoretical framework put forward in a recent letter [Phys. Rev. Lett. 117, 104101 (2016)PRLTAO0031-900710.1103/PhysRevLett.117.104101] as an exact and compelling approach to deal with eigenvalue fluctuations of sparse random matrices.

Large Deviation Function for the Number of Eigenvalues of Sparse Random Graphs Inside an Interval

We present a general method to obtain the exact rate function Ψ_{[a,b]}(k) controlling the large deviation probability Prob[I_{N}[a,b]=kN]≍e^{-NΨ_{[a,b]}(k)} that an N×N sparse random matrix has I_{N}[a,b]=kN eigenvalues inside the interval [a,b]. The method is applied to study the eigenvalue statistics in two distinct examples: (i) the shifted index number of eigenvalues for an ensemble of Erdös-Rényi graphs and (ii) the number of eigenvalues within a bounded region of the spectrum for the Anderson model on regular random graphs. A salient feature of the rate function in both cases is that, unlike rotationally invariant random matrices, it is asymmetric with respect to its minimum. The asymmetric character depends on the disorder in a way that is compatible with the distinct eigenvalue statistics corresponding to localized and delocalized eigenstates. The results also show that the level compressibility κ_{2}/κ_{1} for the Anderson model on a regular graph satisfies 0<κ_{2}/κ_{1}<1 in the bulk regime, in contrast with the behavior found in Gaussian random matrices. Our theoretical findings are thoroughly compared to numerical diagonalization in both cases, showing a reasonable good agreement.