PageRank

In the Theoretical Computer Science seminar, students work in pairs to present a research topic, covering both its theoretical foundations and its practical applications. Below is the presentation my partner and I gave on PageRank (Brin & Page, 1998), the algorithm behind Google’s original search engine. PageRank models the web as a directed graph whose edge weights are transition probabilities and ranks each page by the long-run fraction of time a “random surfer” spends there, i.e. the stationary distribution of the resulting Markov chain.

We present a convergence proof based on a contraction argument. Thanks to the damping factor, the Google matrix contracts distances between probability vectors, so power iteration converges geometrically. We then show how the sparsity of the link structure allows the ranking to be computed efficiently at web scale. Finally, we discuss Personalized PageRank (Haveliwala, 2002), which biases the random jumps toward a chosen set of pages to produce user- or topic-specific rankings.

The slides are available here: PageRank presentation.