Cavity and replica methods for the spectral density of sparse symmetric random matrices

Abstract

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.

arXiv comment52 pag., 5 fig. Typos fixed. Submission to SciPost

References in corpus (45)

• Statistical mechanics of complex networks
• Evolution of networks
• Random Matrix Theories in Quantum Physics: Common Concepts
• The Bethe lattice spin glass revisited
• Localization and Spreading of Diseases in Complex Networks
• Spectra of complex networks
• Cleaning large correlation matrices: tools from random matrix theory
• Introduction to Random Matrices - Theory and Practice
• Anderson localization on random regular graphs
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Fractality of wave functions on a Cayley tree: Difference between a tree and a locally tree-like graph without boundary
• Message passing on networks with loops
• Random incidence matrices: moments of the spectral density
• Randomly Crosslinked Macromolecular Systems: Vulcanisation Transition to and Properties of the Amorphous Solid State
• A single defect approximation for localized states on random lattices
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• On the localization transition in symmetric random matrices
• Anderson model on Bethe lattices: density of states, localization properties and isolated eigenvalue
• Eigenvector localization in real networks and its implications for epidemic spreading
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Analytic computation of the Instantaneous Normal Modes spectrum in low density liquids
• Extended States in a Lifshitz Tail Regime for Random Schrödinger Operators on Trees
• Signal and Noise in Financial Correlation Matrices
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Stress Relaxation of Near-Critical Gels
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Localization of eigenvectors in random graphs
• 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
• Anderson Localization in Euclidean Random Matrices
• 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
• Spectral Density of Complex Networks with a Finite Mean Degree
• The spectral density of dense random networks and the breakdown of the Wigner semicircle law
• Spectral density of the non-backtracking operator
• Second largest Eigenpair Statistics for Sparse Graphs
• Top Eigenpair Statistics for Weighted Sparse Graphs
• Spectral properties of the trap model on sparse networks
• Imaginary replica analysis of loopy regular random graphs
• Index of a matrix, complex logarithms, and multidimensional Fresnel integrals

Cited by in corpus (17)

• Eigenvalues of random matrices with generalised correlations: a path integral approach
• Fully localized and partially delocalized states in the tails of Erdös-Rényi graphs in the critical regime
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• Complete mathematical theory of the jamming transition: A perspective
• Random sparse generators of Markovian evolution and their spectral properties
• Hammerstein equations for sparse random matrices
• Soft modes in vector spin glass models on sparse random graphs
• Local sign stability and its implications for spectra of sparse random graphs and stability of ecosystems
• Sparse Random Block Matrices
• Eigenvalue spectral tails and localization properties of asymmetric networks
• A path integral approach to sparse non-Hermitian random matrices
• Top eigenpair statistics of diluted Wishart matrices
• Statistical field theory of random graphs with prescribed degrees
• Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries
• Localization properties of the sparse Barrat-Mézard trap model