This thesis studies two problems centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly expresses the non-backtracking matrix eigenvalues. Additionally, we develop upper and lower bounds on the matrix spectrum and use the spectrum to investigate properties of the graph. Second, we investigate the difference between PageRank and non-backtracking PageRank. We show some instances where there is no difference and develop an algorithm to compare PageRank and non-backtracking PageRank under certain conditions using $\mu$-PageRank.
College and Department
BYU ScholarsArchive Citation
Glover, Cory, "The Non-Backtracking Spectrum of a Graph and Non-Bactracking PageRank" (2021). Theses and Dissertations. 9194.
graph theory, combinatorics, random walks, non-backtracking random walks, non-backtracking spectrum, pagerank