Some spectral properties of the non-backtracking matrix of a graph

DOI10.1016/J.LAA.2021.01.022MaRDI QIDQ2020643zbMATH OpenOpenAlexFDO

Authors Cory Glover, Mark Kempton

Publication date 24 April 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

spectral graph theoryeigenvalueseigenvectorsnon-backtracking walks

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: We investigate the spectrum of the non-backtracking matrix of a graph. In particular, we show how to obtain eigenvectors of the non-backtracking matrix in terms of eigenvectors of a smaller matrix. Furthermore, we find an expression for the eigenvalues of the non-backtracking matrix in terms of eigenvalues of the adjacency matrix and use this to upper-bound the spectral radius of the non-backtracking matrix and to give a lower bound on the spectrum. We also investigate properties of a graph that can be determined by the spectrum. Specifically, we prove that the number of components, the number of degree 1 vertices, and whether or not the graph is bipartite are all determined by the spectrum of the non-backtracking matrix.

Recommendations

• On the non-backtracking spectral radius of graphs
• Spectral theory of the non-backtracking Laplacian for graphs
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Eigenvalues of the non-backtracking operator detached from the bulk
• Non-backtracking spectrum of degree-corrected stochastic block models

Cites work

• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• Beyond non-backtracking: non-cycling network centrality measures
• Bounds on graph eigenvalues. I
• Cutoff on all Ramanujan graphs
• Cutoff phenomena for random walks on random regular graphs
• Ihara zeta function of finite graphs with circuit rank two
• Ihara zeta functions of coronae
• Inequalities for Graph Eigenvalues
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• On an upper bound of the spectral radius of graphs
• On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
• On the exponential generating function for non-backtracking walks
• Some new bounds on the spectral radius of graphs
• Some new bounds on the spectral radius of matrices
• Spectra of graphs
• Spectral redemption in clustering sparse networks

Cited in

(14)

• On the non-backtracking spectral radius of graphs
• The average connectivity matrix of a graph
• Localized eigenvectors of the non-backtracking matrix
• Spectral analysis of non-Hermitian matrices and directed graphs
• Two accelerated non-backtracking PageRank algorithms for large-scale networks
• There is no going back: properties of the non-backtracking Laplacian
• Non-backtracking spectrum of degree-corrected stochastic block models
• Generating functions of non-backtracking walks on weighted digraphs: radius of convergence and Ihara's theorem
• Maximal colourings for graphs
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Kemeny's constant for nonbacktracking random walks
• The non-backtracking spectrum of the universal cover of a graph
• Eigenvalues of the non-backtracking operator detached from the bulk
• Spectral theory of the non-backtracking Laplacian for graphs

This page was built for publication: Some spectral properties of the non-backtracking matrix of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020643)