Abstract
Motivated by community detection, we characterise the spectrum of the nonbacktracking matrix B in the DegreeCorrected Stochastic Block Model.
Specifically, we consider a random graph on n vertices partitioned into two asymptotically equalsized clusters. The vertices have i.i.d. weights {\phi_u}_{u=1}^n with second moment \PHItwo. The intracluster connection probability for vertices u and v is \frac{\phi_u \phi_v}{n}a and the intercluster connection probability is \frac{\phi_u \phi_v}{n}b.
We show that with high probability, the following holds: The leading eigenvalue of the nonbacktracking matrix B is asymptotic to \rho = \frac{a+b}{2} \PHItwo. The second eigenvalue is asymptotic to \mu_2 = \frac{ab}{2} \PHItwo when \mu_2^2 > \rho, but asymptotically bounded by \sqrt{\rho} when \mu_2^2 \leq \rho. All the remaining eigenvalues are asymptotically bounded by \sqrt{\rho}. As a result, a clustering positivelycorrelated with the true communities can be obtained based on the second eigenvector of B in the regime where \mu_2^2 > \rho.
In a previous work we obtained that detection is impossible when $\mu_2^2 \leq \rho,$ meaning that there occurs a phasetransition in the sparse regime of the DegreeCorrected Stochastic Block Model.
As a corollary, we obtain that DegreeCorrected ErdösRényi graphs asymptotically satisfy the graph Riemann hypothesis, a quasiRamanujan property.
A byproduct of our proof is a weak law of large numbers for localfunctionals on DegreeCorrected Stochastic Block Models, which could be of independent interest.
BibTeX  Entry
@InProceedings{gulikers_et_al:LIPIcs:2017:8179,
author = {Lennart Gulikers and Marc Lelarge and Laurent Massouli{\'e}},
title = {{NonBacktracking Spectrum of DegreeCorrected Stochastic Block Models}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {44:144:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8179},
URN = {urn:nbn:de:0030drops81795},
doi = {10.4230/LIPIcs.ITCS.2017.44},
annote = {Keywords: DegreeCorrected Stochastic Block Model, Nonbacktracking Matrix, Machine Learning, Social Networks}
}
Keywords: 

DegreeCorrected Stochastic Block Model, Nonbacktracking Matrix, Machine Learning, Social Networks 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 