@phdthesis{gleich2009-thesis,
  title = {Models and Algorithms for {PageRank} Sensitivity},
  author = {David F. Gleich},
  school = {Stanford University},
  year = {2009},
  month = {September},
  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.},
  file = {:gleich 2009 - pagerank thesis.pdf},
  keywords = {self},
  owner = {David Gleich},
  timestamp = {2009.09.13},
  url = {http://www.stanford.edu/group/SOL/dissertations/pagerank-sensitivity-thesis-online.pdf}
}