Spectral density of the non-backtracking operator

Abstract

The non-backtracking operator was recently shown to provide a significant improvement when used for spectral clustering of sparse networks. In this paper we analyze its spectral density on large random sparse graphs using a mapping to the correlation functions of a certain interacting quantum disordered system on the graph. On sparse, tree-like graphs, this can be solved efficiently by the cavity method and a belief propagation algorithm. We show that there exists a paramagnetic phase, leading to zero spectral density, that is stable outside a circle of radius $\sqrt{\rho }$, where $\rho$ is the leading eigenvalue of the non-backtracking operator. We observe a second-order phase transition at the edge of this circle, between a zero and a non-zero spectral density. That fact that this phase transition is absent in the spectral density of other matrices commonly used for spectral clustering provides a physical justification of the performances of the non-backtracking operator in spectral clustering.

arXiv comment6 pages, 6 figures, submitted to EPL

References in corpus (7)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Lifshitz tails for spectra of Erdős--Rényi random graphs

Cited by in corpus (9)

• Statistical physics of inference: Thresholds and algorithms
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Spacing ratio characterization of the spectra of directed random networks
• Spectral Detection in the Censored Block Model
• Graph Comparison via the Non-backtracking Spectrum
• Comparative analysis on the selection of number of clusters in community detection
• Top Eigenpair Statistics for Weighted Sparse Graphs