I’ve been meaning to post this video for a few years. Here was my Ph.D. Thesis defense.

http://www.youtube.com/watch?v=2CSaDB-sLR4

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

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.

Hope someone finds it useful! It’s about PageRank and our particular modification we developed.

Slides: Models and Algorithms for PageRank Sensitivity slides

Thesis: Models and Algorithms for PageRank Sensitivity

### Like this:

Like Loading...

*Related*