Title: Models and Algorithms for PageRank Sensitivity

Speaker: David Gleich, University of British Columbia

Date/Time: Monday, January 18, 2010, 10:00 am        

Location: CSRI/90 in NM and 915/W133 in CA

Brief 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. 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 briefly 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.

CSRI POC: Erik Boman, (505) 844-2003