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.
| Identifer | oai:union.ndltd.org:BGMYU2/oai:scholarsarchive.byu.edu:etd-10203 |
| Date | 15 July 2021 |
| Creators | Glover, Cory |
| Publisher | BYU ScholarsArchive |
| Source Sets | Brigham Young University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | https://lib.byu.edu/about/copyright/ |
Page generated in 0.0023 seconds