Second largest Eigenpair Statistics for Sparse Graphs

Abstract

We develop a formalism to compute the statistics of the second largest eigenpair of weighted sparse graphs with $N\gg 1$ nodes, finite mean connectivity and bounded maximal degree, in cases where the top eigenpair statistics is known. The problem can be cast in terms of optimisation of a quadratic form on the sphere with a fictitious temperature, after a suitable deflation of the original matrix model. We use the cavity and replica methods to find the solution in terms of self-consistent equations for auxiliary probability density functions, which can be solved by an improved population dynamics algorithm enforcing eigenvector orthogonality on-the-fly. The analytical results are in perfect agreement with numerical diagonalisation of large (weighted) adjacency matrices, focussing on the cases of random regular and Erdős-Rényi graphs. We further analyse the case of sparse Markov transition matrices for unbiased random walks, whose second largest eigenpair describes the non-equilibrium mode with the largest relaxation time. We also show that the population dynamics algorithm with population size $N_P$ does not actually capture the thermodynamic limit $N\to \infty$ as commonly assumed: the accuracy of the population dynamics algorithm has a strongly non-monotonic behaviour as a function of $N_P$, thus implying that an optimal size $N_P^{\star }=N_P^{\star }(N)$ must be chosen to best reproduce the results from numerical diagonalisation of graphs of finite size $N$.

arXiv comment51 pages, 7 figures. Section 3.1 expanded and clarified w.r.t. the published version

References in corpus (22)

• A Tutorial on Principal Component Analysis
• The Bethe lattice spin glass revisited
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• A single defect approximation for localized states on random lattices
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Eigenvectors of the discrete Laplacian on regular graphs - a statistical approach
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Spectra of Modular and Small-World Matrices
• Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices
• Spectral density of random graphs with topological constraints
• Finitely coordinated models for low-temperature phases of amorphous systems
• Localization and universality of eigenvectors in directed random graphs
• Equivalence of replica and cavity methods for computing spectra of sparse random matrices
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Top Eigenpair Statistics for Weighted Sparse Graphs
• Mean field theory of spin glasses
• Glassy dynamics on networks: local spectra and return probabilities
• Complex networks and glassy dynamics: walks in the energy landscape

Cited by in corpus (5)

• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• Ranking influential nodes in networks from partial information
• Top eigenpair statistics of diluted Wishart matrices
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries