Eigenvalues of the non-backtracking operator detached from the bulk

Abstract

We describe the non-backtracking spectrum of a stochastic block model with connection probabilities $p_{\mathrm{in}},p_{\mathrm{out}}=\omega (\log n)/n$. In this regime we answer a question posed in Dall'Amico and al. (2019) regarding the existence of a real eigenvalue `inside' the bulk, close to the location $\frac{p_{\mathrm{in}}+p_{\mathrm{out}}}{p_{\mathrm{in}}-p_{\mathrm{out}}}$. We also introduce a variant of the Bauer-Fike theorem well suited for perturbations of quadratic eigenvalue problems, and which could be of independent interest.

15 pages, 4 figures. Minor revision. To appear in Random Matrices: Theory and Applications

References in corpus (3)

• The dimension-free structure of nonhomogeneous random matrices
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Graph powering and spectral robustness

Cited by in corpus (1)

• Extreme singular values of inhomogeneous sparse random rectangular matrices