The PageRank Algorithm

Joshua R. Davis, Carleton College, Math 134, Fall 2024

Introduction

Discussion Problem 4 talks about Google’s PageRank algorithm, which assigns values to each web page based on how many other web pages point to that page and what their values are. This notebook shows that there are two ways to think about PageRank.

Probabilistic version

A piece of software called a web crawler can be used to simulate humans browsing the World Wide Web. The crawler starts at a random web page. That page contains links to other web pages. The crawler picks one of those links at random (with all of the links having equal chances). The crawler follows that link to a new page, which also contains links. The crawler picks one of those links at random and follows that link to a new page. It keeps repeating this pick-and-follow step over and over again. So, as the crawler proceeds through its crawl, it hops around the World Wide Web, sampling more and more of the available web pages.

(There is also a kind of web crawler that follows all links at each page. That kind of crawler is used to discover all of the pages that are available on the World Wide Web, which is important, but not relevant to what we’re currently doing.)

The following matrix P captures the transition probabilities for the mini-web shown in Discussion Problem 4. Notice that P is a stochastic matrix.

p = {
{0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 1/4, 0, 1/3, 0, 0}, 
{0, 0, 0, 1/4, 1/3, 1/3, 0, 0}, 
{0, 0, 1/2, 0, 1/3, 0, 0, 0}, 
{0, 0, 0, 1/4, 0, 1/3, 1/2, 1}, 
{0, 1/3, 0, 1/4, 0, 0, 0, 0}, 
{0, 1/3, 1/2, 0, 1/3, 0, 0, 0}, 
{1, 1/3, 0, 0, 0, 0, 1/2, 0}
};
MatrixForm[p]

For example, if the crawler starts at the third page, then after the first step it has a 50% chance of being at the fourth page and a 50% chance of being at the seventh page.

p.{0, 0, 1, 0, 0, 0, 0, 0}

At it continues its crawl, the probabilities get more complicated. The sequence of probability vectors forms a Markov chain. There’s always a 0% probability of ending up at the first page. Why?

p.p.{0, 0, 1, 0, 0, 0, 0, 0}
p.p.p.{0, 0, 1, 0, 0, 0, 0, 0}
p.p.p.p.{0, 0, 1, 0, 0, 0, 0, 0}

What we just computed was the third column of P, P^2, P^3, P^4, .... If we look at those matrices themselves, then we can see probabilities for all starting pages.

MatrixForm[p]
MatrixForm[p.p]
MatrixForm[p.p.p]
MatrixForm[p.p.p.p]

It’s not hard to guess that the first row is always going to be zero. So the stochastic matrix P does not quite have the property that some power P^k is strictly positive. But it’s pretty close. It seems plausible that there is a unique steady state q, which is the solution to P q = q, to which the probabilities eventually converge for all starting positions.

Finding the steady state

To find the steady state q, we solve P q = q, which is tantamount to (P - I) q = 0. Let A = P - I, so that we’re solving A q = 0. Then the solution goes like this.

a = p - IdentityMatrix[8];
MatrixForm[a]
sol = Solve[
a.{x1, x2, x3, x4, x5, x6, x7, x8} == {0, 0, 0, 0, 0, 0, 0, 0}, 
{x1, x2, x3, x4, x5, x6, x7, x8}]

It seems that Mathematica has picked x2 as its unique free variable. So we get a concrete solution by setting x2 = 1.

sol /. {x2 -> 1}
q = ({x1, x2, x3, x4, x5, x6, x7, x8} /. sol /. {x2 -> 1})[[1]]

That q doesn’t add to one. So we divide it by its total, to make it add to one.

q = q / Total[q]
Total[q]
N[q]

That’s the steady state of the system. If we launch a gazillion web crawlers, then eventually 48 / 293 ~ 16% of them will hang out around the fourth page, for example.

Deterministic version

Our original treatment of the PageRank algorithm didn’t use probability, Markov chains, or anything like that. Rather, we said that each page has a value xi, which is determined through a “voting” process. If page j links to page i, then it is voting for page i. The value of that vote is the total value of page j, divided by how many votes it casts.

For example, page 1 gets no votes, so the equation that describes its value x1 is this:

x1 == 0

Meanwhile, page 8 gets three votes, from pages 1, 2, and 7. It receives all of page 1’s value, but only 1/3 of page 2’s value and only 1/2 of page 7’s value. So its equation is like this:

x8 == x1 + (1 / 3) x2 + (1 / 2) x7

Here are all eight equations at once.

(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[1]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[1]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[2]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[2]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[3]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[3]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[4]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[4]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[5]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[5]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[6]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[6]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[7]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[7]]
(p.{x1, x2, x3, x4, x5, x6, x7, x8})[[8]] == {x1, x2, x3, x4, x5, x6, x7, x8}[[8]]

If you look carefully at the web in Discussion Problem #4 (or at the code above), then you might realize that this linear system is of the form P x = x, where P is exactly the stochastic matrix above. So the solution is the solution to (P - I) x = 0 or A x = 0, exactly as above.

What have we learned?

The point is that there are two ways to look at the PageRank algorithm. One way is about a web crawler that randomly walks around the World Wide Web. It is probabilistic, meaning that it uses randomness. The other way is about a voting process. It is deterministic, meaning that it uses no randomness. These two approaches end up giving the same answer.

From a bird’s eye view, maybe it makes sense that they end up being equivalent. After all, they use exactly the same information: how many links come out of each page, and which pages link to which pages. In more detail, a web crawler tends to end up at popular pages, that are pointed to by many other pages. The effect is especially strong if those pages themselves are popular. And the popularity of a web page is the value that we assign to it. But still I find it a bit surprising, that there should be these two equivalent ways of valuing web pages.

As always, keep in mind that the number of pages on the World Wide Web is not eight but rather more than one billion. So the matrices involved in the actual PageRank algorithm are very large indeed.