Draft

Example for Google's PageRank

Assume we have a small web with six web pages, A, B, C, D, E, and F, and the links as indicated in the digraph to the right (arrows indicate links):

Again, A, B, C, D, E, and F should also denote the page ranks of the corresponding pages. In the same way as in the previous example we get the system of six equations:

1.
2.
3.
4.
5.
6.

Note that throughout, m is just a constant. Later we will see what happens if we vary m (treat it as a variable), but for now we may think of m as being equal to 0.85. The reason why we use expressions with m², m³, and so on, will become clear later again, but for now just assume we don't have our calculator handy.

We solve this system using substitution method. The first equation is already solved for A. We eliminate this equation from our system, substitute A in the second equation (the only other equation where A also appears), thereby also eliminating the variable A, and get the following five equations in the five variables B, C, D, E, F:

2.

3. unchanged

4. unchanged

5. unchanged

6. unchanged

Next we are going to eliminate equation #3, which is already solved for C. We substitute it into equation #4, the only other equation where C appears, to get 4 equations with the variables B, D, E, F:

2.	unchanged
4.
5.	unchanged
6.	unchanged

Then we substitute equation #6 into #2 and #4 to get three equations in three variables:

2.
4.
5.	unchanged

Then we substitute equation #5 into #2 and #4 to get two equations with the two variables B and D:

2.
4.

Now, for the first time, none of the equations is already solved for some variable. We have to do it. We decide to solve equation #2 for B and get B = . Then we substitute this into equation #4 and get

This one equation has to be solved for D. What we get is

D =

This is part of the solution, but we also need formulas for A, B, C, E, and F. We derive them by going backwards and looking which equation was used for the substitution. The last one was the equation B = . Now we plug the above solution for D in and get

B =

Next we arrive at the formula . Plugging in the previous two solution formulas for D and B yields

E =

Continuing in this way, we also get the formulas

F =

C =

A =

For m= 0.85, the resulting values are in descending order E=1.459, F=1.39, D=1.15, B=0.78, A=0.74, C=0.48.

.

Varying m

For varying m, the six expressions for A, B, C, D, E, F derived above are (rational) functions in m. If we graph them in the same coordinate system for m between 0 and 1 we get the following picture:

Surprisingly, the ranking of the six sites depend on m. For m smaller than 0.5, the ranking is E, D, F, B, A, C. This is in contradiction to what is described in the literature (at least on the Web).

Erich Prisner, September 2005