2021/04/15 by Joseph Farnan, Farnan, Joseph, Franklin Kenter +1
Engineering · Mathematics · Physics and Astronomy · #05C35 #05C50 #05C81 #Advanced Mathematical Theories and Applications #Combinatorics (math.CO) #FOS: Mathematics #Random Matrices and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2104.07727
openalex publication_date 2021/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a directed graph, the Pagerank algorithm emulates a random walker on the graph that occasionally "jumps" to a random vertex based on a jumping parameter α. Upon completion, the algorithm generates a stochastic vector whose entries correspond to the limiting probability that the walker will be at that vertex. This vector is a right eigenvector of a corresponding Markov trasition matrix. Undoubtedly, this vector can drastically change based upon the jumping parameter α. In this article, we investigate the maximum possible discrepancy for different Pagerank vectors on the same unweighted directed (perhaps with loops) graph as measured by the 2-norm. We show that the limsup of this discrepancy can be as large as √((67)/(50)) using a very specific construction. (For contrast, the norm of the difference for any two stochastic vectors is at most √(2).) Interestingly, on this construction this discrepancy occurs when α= 1 and when α is very close to 1.