I’ve been meaning to post this video for a few years. Here was my Ph.D. Thesis defense.
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 mistake in the original
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.
Hope someone finds it useful! It’s about PageRank and our particular modification we developed.