Abstract
The PageRank model helps evaluate the relative importance of nodes in a large graph, such as the graph of links on the world wide web. An important piece of the PageRank model is the teleportation parameter alpha. We explore the interaction between alpha and PageRank through the lens of sensitivity analysis. Writing the PageRank vector as a function of alpha allows us to take a derivative, which is a simple sensitivity measure. As an alternative approach, we apply techniques from the field of uncertainty quantification. Regarding alpha as a random variable produces a new PageRank model in which each PageRank value is a random variable. We explore the standard deviation of these variables to get another measure of PageRank sensitivity. One interpretation of this new model shows that it corrects a small oversight in the original PageRank formulation.
Both of the above techniques require solving multiple PageRank problems, and thus a robust PageRank solver is needed. We discuss an inner-outer iteration for this purpose. The method is low-memory, simple to implement, and has excellent performance for a range of teleportation parameters.
We show empirical results with these techniques on graphs with over 2 billion edges.
Available
- Personal site
- Models and Algorithms for PageRank Sensitivity
- Models and Algorithms for PageRank Sensitivity slides
- SOL website
- Models and Algorithms for PageRank Sensitivity
Supporting codes
Coming soon.
Notes
While preparing the thesis, I developed a variant of the Stanford thesis style. It fits more information onto a page.
Bibtex
@PHDTHESIS{gleich2009-thesis,
author = {David F. Gleich},
title = {Models and Algorithms for PageRank Sensitivity},
school = {Stanford University},
year = {2009},
month = {September},
url = {http://www.stanford.edu/group/SOL/dissertations/pagerank-sensitivity-thesis-online.pdf}
}