# Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

arXiv: https://arxiv.org/abs/1609.02487 · HTML: https://mlsanity.com/paper/1609.02487/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2016.

## Built on by (most cited first, 3 of 3)

- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)
- [Complex non-backtracking matrix for directed graphs](https://mlsanity.com/paper/2507.12503/) (2025)

## Abstract (arXiv)

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  φu u=1n with second moment Phi(2). The intra-cluster connection probability for vertices u and v is fracφu φvna and the inter-cluster connection probability is fracφu φvnb. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix B is asymptotic to ρ = fraca+b2 Phi(2). The second eigenvalue is asymptotic to μ2 = fraca-b2 Phi(2) when μ22 > ρ, but asymptotically bounded by √ρ when μ22 ≤ ρ. All the remaining eigenvalues are asymptotically bounded by √ρ. 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 μ22 > ρ. In a previous work we obtained that detection is impossible when μ22 < ρ, 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 ErdHos-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.