n-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

When

28/09/2016    
2:00 pm-3:00 pm
Lennart Gulikers
INRIA

Where

LINCS Meeting Room 40
23, avenue d'Italie, Paris, 75013

Event Type

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 $ phi_u _u=1^n$ with second moment $PHItwo$. The intra-cluster connection probability for vertices $u$ and $v$ is $ phi_u phi_v a/b$ and the inter-cluster connection probability is $phi_u phi_v b/n$. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix $B$ is asymptotic to $rho = (a+b)/2 PHItwo$. The second eigenvalue is asymptotic to $mu_2 = (a+b)/2 PHItwo$ when $mu_2^2 > rho$, but asymptotically bounded by $sqrtrho$ when $mu_2^2 leq rho$. All the remaining eigenvalues are asymptotically bounded by $sqrtrho$. 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.$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 Erdos-Renyi 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.

Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.