Abstract

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.

Degree

MS

College and Department

Mathematics

Rights

https://lib.byu.edu/about/copyright/

Date Submitted

2021-07-15

Document Type

Thesis

Handle

http://hdl.lib.byu.edu/1877/etd11832

Keywords

graph theory, combinatorics, random walks, non-backtracking random walks, non-backtracking spectrum, pagerank

Language

english

Share

COinS