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

DOI10.1016/J.LAA.2021.01.022zbMATH Open1462.05223arXiv2011.09385OpenAlexW3128477922MaRDI QIDQ2020643FDOQ2020643

Cory Glover, Mark Kempton

Publication date: 24 April 2021

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Title not available (Why is that?)
• Generating functions of non-backtracking walks on weighted digraphs: radius of convergence and Ihara's theorem
• Maximal colourings for graphs
• There is no going back: properties of the non-backtracking Laplacian
• Kemeny's constant for nonbacktracking random walks
• The average connectivity matrix of a graph
• Spectral theory of the non-backtracking Laplacian for graphs
• Two accelerated non-backtracking PageRank algorithms for large-scale networks

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)