A Tale of Two Limits: An Extremal Pagerank Problem

MaRDI QIDQ6365402zbMATH OpenFDO

Authors Joseph Farnan, Franklin Kenter

Publication date 15 April 2021

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81)

Abstract: 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 $alpha$. 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 $alpha$. 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 $sqrtfrac6750$ using a very specific construction. (For contrast, the norm of the difference for any two stochastic vectors is at most $sqrt2$.) Interestingly, on this construction this discrepancy occurs when $alpha=1$ and when $alpha$ is very close to 1.

This page was built for publication: A Tale of Two Limits: An Extremal Pagerank Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365402)