How does Google decide which web sites are important? It uses an ingenious algorithm that exploits the structure of the web and is resistant to hacking. Here, we describe this PageRank algorithm, illustrate it by example, and show how it can be interpreted as a Jacobi iteration and a teleporting random walk. We also ask the algorithm to rank the undergraduate mathematics classes offered at the University of Strathclyde. PageRank draws upon ideas from linear algebra, graph theory and stochastic processes, and it throws up research-level challenges in scientific computing. It thus forms an exciting and modern application area that could brighten up many a mathematics class syllabus.

PageRank, a sleek algorithm in computational graph theory, shows how one killer mathematical idea can build up a global brand name. Google began as a research project for Ph.D. candidates Page and Brin when they were, respectively, 24 and 23 years old. It now answers over 200 million queries per day. Our aim here is to describe PageRank, illustrate it via simple examples, and use it to pull together ideas from numerical analysis and stochastic processes. We also point out, via a somewhat frivolous example, how its utility extends well beyond the world wide web.

The observations in sections 4 and 5 are not new. Indeed, both the linear system/eigenvector formulation and the random walk interpretation are mentioned in the original work [15]. However, we believe that there are benefits to be had from a unified, low-level review—in particular, teachers in further and higher education may find that this material can be slipped into a class on linear algebra, graph theory, stochastic processes or scientific computation. We also see it as a jumping-off point for student projects.

Download pdf The Sleekest Link Algorithm