1 Search Results for "Gulikers, Lennart"

Document

DOI: 10.4230/LIPIcs.ITCS.2017.44

Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Authors: Lennart Gulikers, Marc Lelarge, and Laurent Massoulié

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

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 asymptotically 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 \frac{\phi_u \phi_v}{n}a and the inter-cluster connection probability is \frac{\phi_u \phi_v}{n}b. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix B is asymptotic to \rho = \frac{a+b}{2} \PHItwo. The second eigenvalue is asymptotic to \mu_2 = \frac{a-b}{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 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 \leq \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 Erdös-Rényi 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.

Cite as

Lennart Gulikers, Marc Lelarge, and Laurent Massoulié. Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 44:1-44:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gulikers_et_al:LIPIcs.ITCS.2017.44,
  author =	{Gulikers, Lennart and Lelarge, Marc and Massouli\'{e}, Laurent},
  title =	{{Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{44:1--44:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.44},
  URN =		{urn:nbn:de:0030-drops-81795},
  doi =		{10.4230/LIPIcs.ITCS.2017.44},
  annote =	{Keywords: Degree-Corrected Stochastic Block Model, Non-backtracking Matrix, Machine Learning, Social Networks}
}

Refine by Author
1 Gulikers, Lennart
1 Lelarge, Marc
1 Massoulié, Laurent

Refine by Classification

Refine by Keyword
1 Degree-Corrected Stochastic Block Model
1 Machine Learning
1 Non-backtracking Matrix
1 Social Networks

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Gulikers, Lennart"

Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Abstract

Cite as

Thanks for your feedback!

Could not send message