TY - JOUR
T1 - Cavity and replica methods for the spectral density of sparse symmetric random matrices
AU - Susca, Vito A.R.
AU - Vivo, Pierpaolo
AU - Kühn, Reimer
N1 - Funding Information:
Funding information The authors acknowledge funding by the Engineering and Physical Sciences Research Council (EPSRC) through the Centre for Doctoral Training in Cross Disciplinary Approaches to Non-Equilibrium Systems (CANES, Grant Nr. EP/L015854/1).
Publisher Copyright:
Copyright V. A. R. Susca et al. This work is licensed under the Creative Commons Attribution 4.0 International License.
PY - 2021/8/10
Y1 - 2021/8/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85123264584&partnerID=8YFLogxK
U2 - 10.21468/SciPostPhysLectNotes.33
DO - 10.21468/SciPostPhysLectNotes.33
M3 - Review article
AN - SCOPUS:85123264584
SN - 2590-1990
JO - SciPost Physics Lecture Notes
JF - SciPost Physics Lecture Notes
IS - 33
ER -