Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Abstract

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=1^n with second moment ^(2). The intra-cluster connection probability for vertices u and v is _u _vna and the inter-cluster connection probability is _u _vnb. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix B is asymptotic to = a+b2 ^(2). The second eigenvalue is asymptotic to _2 = a-b2 ^(2) when _2^2 > , but asymptotically bounded by when _2^2 . 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 _2^2 > . In a previous work we obtained that detection is impossible when _2^2 < , 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 Erdos-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.

Tasks

Reproductions