A second, unrelated recent effort has been devoted to analyzing the spectral problem of sample auto-covariance matrices derived from time series. In contrast to the widely studied related problem of sample covariance matrices of multivariate random data (the Wishart-Laguerre ensemble), a theoretical understanding of the spectral problem of sample auto-covariance matrices has so far been almost entirely missing, although it is clear that such understanding has signifincant potential for a broad range of applications, including time series analysis, signal processing, information theory, and finance.
We review the problem of how to compute the spectral density of sparse symmetric random matrices, i.e. weighted adjacency matrices of undirected graphs. Starting from the Edwards-Jones formula, we illustrate the milestones of this line of research, including the pioneering work of Bray and Rodgers using replicas. We focus first on the cavity method, showing that it quickly provides the correct recursion equations both for single instances and at the ensemble level. We also describe an alternative replica solution that proves to be equivalent to the cavity method. Both the cavity and the replica derivations allow us to obtain the spectral density via the solution of an integral equation for an auxiliary probability density function. We show that this equation can be solved using a stochastic population dynamics algorithm, and we provide its implementation. In this formalism, the spectral density is naturally written in terms of a superposition of local contributions from nodes of given degree, whose role is thoroughly elucidated. This paper does not contain original material, but rather gives a pedagogical overview of the topic. It is indeed addressed to students and researchers who consider entering the field. Both the theoretical tools and the numerical algorithms are discussed in detail, highlighting conceptual subtleties and practical aspects.
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 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→∞ 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=N^*P(N) must be chosen to best reproduce the results from numerical diagonalisation of graphs of finite size N.
The slow relaxation and aging of glassy systems can be modelled as a Markov process on a simplified rough energy landscape: energy minima where the system tends to get trapped are taken as nodes of a random network, and the dynamics are governed by the transition rates among these. In this work we consider the case of purely activated dynamics, where the transition rates only depend on the depth of the departing trap. The random connectivity and the disorder in the trap depths make it impossible to solve the model analytically, so we base our analysis on the spectrum of eigenvalues λ of the master operator. We compute the local density of states ρ(λ|τ) for traps with a fixed lifetime τ by means of the cavity method. This exhibits a power law behaviour ρ(λ|τ)∼τ |λ|T in the regime of small relaxation rates |λ|, which we rationalize using a simple analytical approximation. In the time domain, we find that the probabilities of return to a starting node have a power law-tail that is determined by the distribution of excursion times F(t)∼t−(T+1). We show that these results arise only by the combination of finite configuration space connectivity and glassy disorder, and interpret them in a simple physical picture dominated by jumps to deep neighbouring traps.
We develop a formalism to compute the statistics of the top eigenpair of weighted sparse graphs with finite mean connectivity and bounded maximal degree. Framing the problem in terms of optimisation of a quadratic form on the sphere and introducing a fictitious temperature, we employ 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 population dynamics. This derivation allows us to identify and unpack the individual contributions to the top eigenvector’s components coming from nodes of degree k. The analytical results are in perfect agreement with numerical diagonalisation of large (weighted) adjacency matrices, and are further cross- checked on the cases of random regular graphs and sparse Markov transition matrices for unbiased random walks.
One of the simplest models for the slow relaxation and aging of glasses is the trap model by Bouchaud and others, which represents a system as a point in configuration-space hopping between local energy minima. The time evolution depends on the transition rates and the network of allowed jumps between the minima. We consider the case of sparse configuration-space connectivity given by a random graph, and study the spectral properties of the resulting master operator. We develop a general approach using the cavity method that gives access to the density of states in large systems, as well as localisation properties of the eigenvectors, which are important for the dynamics. We illustrate how, for a system with sparse connectivity and finite temperature, the density of states and the average inverse participation ratio have attributes that arise from a non-trivial combination of the corresponding mean field (fully connected) and random walk (infinite temperature) limits. In particular, we find a range of eigenvalues for which the density of states is of mean-field form but localisation properties are not, and speculate that the corresponding eigenvectors may be localised to extensively many clusters of network sites.
We describe a method for disentangling giant component and finite cluster contributions to sparse random matrix spectra, using sparse symmetric random matrices defined on Erdös-Renyi graphs as an example and test-bed. Our methods apply to sparse matrices defined in terms of arbitrary graphs in the configuration model class, as long as they have finite mean degree.
Rare event statistics for random walks on complex networks are investigated using the large deviation formalism. Within this formalism, rare events are realised as typical events in a suitably deformed path-ensemble, and their statistics can be studied in terms of spectral properties of a deformed Markov transition matrix. We observe two different types of phase transition in such systems: (i) rare events which are singled out for sufficiently large values of the deformation parameter may correspond to {\em localised\/} modes of the deformed transition matrix; (ii) ``mode-switching transitions" may occur as the deformation parameter is varied. Details depend on the nature of the observable for which the rare event statistics is studied, as well as on the underlying graph ensemble. In the present paper we report results on rare events statistics for path averages of random walks in Erd\H{o}s-R\'enyi and scale free networks. Large deviation rate functions and localisation properties are studied numerically. For observables of the type considered here, we also derive an analytical approximation for the Legendre transform of the large deviation rate function, which is valid in the large connectivity limit. It is found to agree well with simulations.
We evaluate spectra of stochastic matrices defined on complex random graphs, with edges $(i,j)$ of a graph being given positive random weights $W_{ij} >0$ in such a fashion that column sums are normalized to one. The structure of the graphs and the distribution of the non-zero edge weights $W_{ij}$ are largely arbitrary. We only require that the the mean vertex degree remains finite in the thermodynamic limit, and that the $W_{ij}$ satisfy a detailed balance condition. The main motivation for this work derives from the fact that knowing the spectra of stochastic matrices is tantamount to knowing the complete spectrum of relaxation times of stochastic processes described by them. One of the interesting new phenomena uncovered by our study is the appearance of localization transitions and mobility edges in the spectra of stochastic matrices of the type investigated in the present study.
We compute spectra of large stochastic matrices $W$, defined on sparse random graphs, where edges $(i,j)$ of the graph are given positive random weights $W_{ij}>0$ in such a fashion that column sums are normalized to one. We compute spectra of such matrices both in the thermodynamic limit, and for single large instances. The structure of the graphs and the distribution of the non-zero edge weights $W_{ij}$ are largely arbitrary, as long as the mean vertex degree remains finite in the thermodynamic limit and the $W_{ij}$ satisfy a detailed balance condition. Knowing the spectra of stochastic matrices is tantamount to knowing the complete spectrum of relaxation times of stochastic processes described by them, so our results should have many interesting applications for the description of relaxation in complex systems. Our approach allows to disentangle contributions to the spectral density related to extended and localized states, respectively, allowing to differentiate between time-scales associated with transport processes and those associated with the dynamics of local rearrangements.
We compute spectral densities of large sample auto-covariance matrices of stationary stochastic processes at fixed ratio $\alpha=N/M$ of matrix dimension $N$ and sample size $M$. We find a remarkable scaling relation which expresses the spectral density $\rho_\alpha(\lambda)$ of sample auto-covariance matrices for processes {\em with\/} correlations as a continuous superposition of copies of the spectral density $\rho_\alpha^{(0)}(\lambda)$ for a sequence of {\em uncorrelated\/} random variables at the same value of $\alpha$, rescaled in terms of the Fourier transform $\hat C(q)$ of the true auto-covariance function. We also obtain a closed-form approximation for the scaling function $\rho_\alpha^{(0)}(\lambda)$. Our results are in excellent agreement with numerical simulations using auto-regressive processes, and processes exhibiting a power-law decay of correlations.
We compute spectra of symmetric random matrices describing graphs with general modular structure and arbitrary inter- and intra-module degree distributions, subject only to the constraint of finite mean connectivities. We also evaluate spectra of a certain class of small-world matrices generated from random graphs by introducing short-cuts via additional random connectivity components. Both adjacency matrices and the associated graph Laplacians are investigated. For the Laplacians, we find Lifshitz type singular behaviour of the spectral density in a localised region of small $|\lambda|$ values. In the case of modular networks, we can identify contributions local densities of state from individual modules. For small-world networks, we find that the introduction of short cuts can lead to the creation of satellite bands outside the central band of extended states, exhibiting only localised states in the band-gaps. Results for the ensemble in the thermodynamic limit are in excellent agreement with those obtained via a cavity approach for large finite single instances, and with direct diagonalisation results.
We compute spectra of symmetric random matrices defined on graphs exhibiting a modular structure. Modules are initially introduced as fully connected sub-units of a graph. By contrast, inter-module connectivity is taken to be incomplete. Two different types of inter-module connectivity are considered, one where the number of intermodule connections per-node diverges, and one where this number remains finite in the infinite module-size limit. In the first case, results can be understood as a perturbation of a superposition of semicircular spectral densities one would obtain for uncoupled modules. In the second case, matters can be more involved, and depend in detail on inter-module connectivities. For suitable parameters we even find near-triangular shaped spectral densities, similar to those observed in certain scale-free networks, in a system of consisting of just two coupled modules. Analytic results are presented for the infinite module-size limit; they are well corroborated by numerical simulations.
The spectral density of the ensemble of sparse symmetric random matrices is analyzed using the cavity method. We consider two cases: matrices whose associated graphs are locally tree-like, and sparse covariance matrices. We derive a closed set of equations from which the density of eigenvalues can be efficiently calculated. Within this approach, the Wigner semicircle law for Gaussian matrices and the Marcenko-Pastur law for covariance matrices are recovered easily. Our results are compared with numerical diagonalization, finding excellent agreement.
We compute the spectral density for ensembles of sparse symmetric random matrices using replica. Our formulation of the replica-symmetric ansatz shares the symmetries of the one suggested in a seminal paper by Rodgers and Bray (symmetry with respect to permutation of replica and rotation symmetry in the space of replica), but uses a different representation in terms of superpositions of Gaussians. It gives rise to a pair of integral equations which can be solved by a stochastic population-dynamics algorithm. Remarkably our representation allows to identify pure-point contributions to the spectral density related to the existence of normalizable eigenstates. Our approach is not restricted to matrices defined on graphs with Poissonian degree distribution. Matrices defined on regular random graphs or on scale-free graphs, are easily handled. We also look at matrices with row constraints such as discrete graph Laplacians. Our approach naturally allows to unfold the total density of states into contributions coming from vertices of different local coordination and an example of such an unfolding is presented. Our results are well corroborated by numerical diagonalization studies of large finite random matrices.