Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$ vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights $\{{\varphi }_u{\}}_{u=1}^n$ with second moment ${\mathrm{\Phi }}^{(2)}$. The intra-cluster connection probability for vertices $u$ and $v$ is $\frac{{\varphi }_u{\varphi }_v}{n}a$ and the inter-cluster connection probability is $\frac{{\varphi }_u{\varphi }_v}{n}b$. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix $B$ is asymptotic to $\rho = \frac{a+b}{2} \Phi^{(2)}$\mathrm{.}Thesecondeigenvalueisasymptoticto$\mu_2 = \frac{a-b}{2} \Phi^{(2)}$when$\mu_2^2 > \rho$,butasymptoticallyboundedby$\sqrt{\rho}$when$\mu_2^2 \leq \rho$. All the remaining eigenvalues are asymptotically bounded by $\sqrt{\rho }$. As a result, a clustering positively-correlated with the true communities can be obtained based on the second eigenvector of $B$ in the regime where ${\mu }_2^2>\rho \mathrm{.}$ In a previous work we obtained that detection is impossible when $\mu_2^2 < \rho,$ meaning that there occurs a phase-transition in the sparse regime of the Degree-Corrected Stochastic Block Model. As a corollary, we obtain that Degree-Corrected Erd\H{o}s-R'enyi graphs asymptotically satisfy the graph Riemann hypothesis, a quasi-Ramanujan property. A by-product of our proof is a weak law of large numbers for local-functionals on Degree-Corrected Stochastic Block Models, which could be of independent interest.