| Speaker : | Lennart Gulikers |
| INRIA | |
| Date: | 28/09/2016 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | LINCS Meeting Room 40 |
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 $ 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.