Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

DOI10.4230/LIPIcs.ITCS.2017.44zbMath1402.05192arXiv1609.02487MaRDI QIDQ4638099

Marc Lelarge, Laurent Massoulié, Lennart Gulikers

Publication date: 3 May 2018

Full work available at URL: https://arxiv.org/abs/1609.02487

zbMATH Keywords

Ramanujan graphsdegree-corrected stochastic block modelnon-backtracking matrix

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (4)

Learning sparse graphons and the generalized Kesten-Stigum threshold ⋮ Unnamed Item ⋮ Optimal adaptivity of signed-polygon statistics for network testing ⋮ Eigenvalues of the non-backtracking operator detached from the bulk

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstruction and estimation in the planted partition model
• Ramanujan graphs
• The eigenvalues of random symmetric matrices
• Automorphic forms and geometry of arithmetic varieties
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• A proof of the block model threshold conjecture
• Broadcasting on trees and the Ising model.
• Spectral redemption in clustering sparse networks
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Community detection thresholds and the weak Ramanujan property
• The phase transition in inhomogeneous random graphs
• A Limit Theorem for Multidimensional Galton-Watson Processes
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes

This page was built for publication: Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models