Exercise 9

We saw a couple of model Internets in which a Markov chain defined by the Google matrix \(G\) did not converge to an appropriate PageRank vector. For this reason, Google defines the matrix

\begin{equation*} H_n = \left[\begin{array}{rrrr} \frac1n \amp \frac1n \amp \ldots \amp \frac1n \\ \frac1n \amp \frac1n \amp \ldots \amp \frac1n \\ \vdots \amp \vdots \amp \ddots \amp \vdots \\ \frac1n \amp \frac1n \amp \ldots \amp \frac1n \\ \end{array}\right]\text{,} \end{equation*}

where \(n\) is the number of web pages, and constructs a Markov chain from the modified Google matrix

\begin{equation*} G' = \alpha G + (1-\alpha)H_n\text{.} \end{equation*}

Since \(G'\) is positive, the Markov chain is guaranteed to converge to a unique steady-state vector.

We said that Google chooses \(\alpha = 0.85\) so we might wonder why this is a good choice. We will explore the role of \(\alpha\) in this exercise. Let's consider the model Internet described in FigureĀ 4.5.9 and construct the Google matrix \(G\text{.}\) In the Sage cell below, you can enter the matrix \(G\) and choose a value for \(\alpha\text{.}\)

  1. Let's begin with \(\alpha=0\text{.}\) With this choice, what is the matrix \(G'=\alpha G + (1-\alpha)H_n\text{?}\) Construct a Markov chain using the Sage cell above. How many steps are required for the Markov chain to converge to the accuracy with which the vectors \(\xvec_k\) are displayed?

  2. Now choose \(\alpha=0.25\text{.}\) How many steps are required for the Markov chain to converge to the accuracy at which the vectors \(\xvec_k\) are displayed?

  3. Repeat this experiment with \(\alpha = 0.5\) and \(\alpha=0.75\text{.}\)

  4. What happens if \(\alpha = 1\text{?}\)

This experiment gives some insight into the choice of \(\alpha\text{.}\) The smaller \(\alpha\) is, the faster the Markov chain converges. This is important; since the matrix \(G'\) that Google works with is so large, we would like to minimize the number of terms in the Markov chain that we need to compute. On the other hand, as we lower \(\alpha\text{,}\) the matrix \(G' = \alpha G + (1-\alpha)H_n\) begins to resemble \(H_n\) more and \(G\) less. The value \(\alpha=0.85\) is chosen so that the matrix \(G'\) sufficiently resembles \(G\) while having the Markov chain converge in a reasonable amount of steps.