Spectra of Random Stochastic Matrices and Relaxation in Complex Systems

Abstract

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.

arXiv comment4 pages, 2 figures

References in corpus (13)

• The structure and function of complex networks
• The spread of epidemic disease on networks
• Critical phenomena in complex networks
• Search in Power-Law Networks
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Characteristic times of biased random walks on complex networks
• Signalling Entropy: a novel network-theoretical framework for systems analysis and interpretation of functional omic data
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• Eigenvalue Spectra of Modular Networks
• Circular Law Theorem for Random Markov Matrices
• Small-world spectra in mean field theory
• Spectrum of Markov generators on sparse random graphs
• Complex networks and glassy dynamics: walks in the energy landscape

Cited by in corpus (14)

• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Linear stability analysis for large dynamical systems on directed random graphs
• Localization and universality of eigenvectors in directed random graphs
• Eigenvalue spectra and stability of directed complex networks
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Second largest Eigenpair Statistics for Sparse Graphs
• Top Eigenpair Statistics for Weighted Sparse Graphs
• Glassy dynamics on networks: local spectra and return probabilities
• Spectral properties of the trap model on sparse networks
• Breakdown of random matrix universality in Markov models
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• The Fate of Articulation Points and Bredges in Percolation
• A Random Walk Perspective on Hide-and-Seek Games