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.
Categories: math.PR cs.NA math.CO math.NA