On the extremal spectral properties of random graphs

Abstract

In this work, we study some statistical properties of the extreme eigenstates of the randomly-weighted adjacency matrices of random graphs. We focus on two random graph models: Erdős-Rényi (ER) graphs and random geometric graphs (RGGs). Indeed, the adjacency matrices of both graph models are diluted versions of the Gaussian Orthogonal Ensemble (GOE) of random matrix theory (RMT), such that a transition from the Poisson Ensemble (PE) and the GOE is observed by increasing the graph average degree $⟨k⟩$. First, we write down expressions for the spectral density in terms of $⟨k⟩$ for the regimes below and above the percolation threshold. Then, we show that the distributions of both, the largest ${\lambda }_1$ and second-largest ${\lambda }_2$ eigenvalues approach the Tracy-Widom distribution of type 1 for $⟨k⟩\gg 1$, while $⟨{\lambda }_1⟩=\sqrt{2⟨k⟩}$. Additionally, we demonstrate that the distributions of the normalized distance between ${\lambda }_1$ and ${\lambda }_2$, the distribution of the ratio between higher consecutive eigenvalues spacings, as well as the distributions of the inverse participation ratios of the extreme eigenstates display a clear PE--to--GOE transition as a function of $⟨k⟩$, so any of these distributions can be effectively used to probe the delocalization transition of the graph models without the need of the full spectrum.

References in corpus (6)

• Synchronization in complex networks
• Anderson Transitions
• Universality in the spectral and eigenfunction properties of random networks
• Random Rectangular Graphs
• Normal mode analysis of spectra of random networks
• A smooth transition towards a Tracy-Widom distribution for the largest eigenvalue of interacting $k$-body fermionic Embedded Gaussian Ensembles