Second largest eigenpair statistics for sparse graphs

We develop a formalism to compute the statistics of the second largest eigenpair of weighted sparse graphs with N >> 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 Erdos-Renyi (ER) 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 -> infinity 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.