Objectives: Topics
-
Review of Markov chains
-
Steady-state theorem for Markov chains
-
Modeling website usage with Markov chains
-
Computing PageRank
Print preview
Section 10.2 Google PageRank
Handout 10.2 Google PageRank
Objectives: Goals
-
Determine whether a stochastic matrix is regular.
-
Use matrix powers and theorems to describe long-term behavior.
-
Construct transition and Google matrices and compute PageRank.
Example 7.1.
Recall Example 4.7: A rental company has three locations A, B, and C.
| rented from | ||||
| A | B | C | ||
| A | .8 | .1 | .2 | |
| returned to | B | .2 | .6 | .3 |
| C | .0 | .3 | .5 | |
There are 18 cars at each location initially. What happens in the long run?
Recall from Section 4.9/5.9 Markov Chains, that for Markov Chain problems involving a regular stochastic matrix \(P\text{,}\) we can find the unique steady-state vector \(\vec q\) by finding the unique probability eigenvector corresponding to an eigenvalue of \(\lambda = 1\text{.}\) This involves solving the equation
\begin{equation*}
P\vec q = \vec q\text{.}
\end{equation*}
For the stochastic matrices \(G\text{,}\) called Google Matrices, that we will create in our PageRank problems, it is going to be extremely difficult to solve \(G\vec q = \vec q\text{.}\) So, we instead determine a different way to identify the steady-state vector.
Theorem 7.3. Convergence of Regular Stochastic Matrices.
If \(P\) is a regular \(m\times m\) stochastic matrix with \(m\ge2\) and with unique steady-state vector \(\vec q\text{,}\) then:
-
There is a stochastic matrix \(\Pi\) such that\begin{equation*} \lim_{n\to\infty}P^n=\Pi\text{.} \end{equation*}
-
For any starting probability vector \(\vec x_0\text{,}\) we have that\begin{equation*} \lim_{n\rightarrow\infty}P^n\vec x_0 = \vec q\text{.} \end{equation*}
-
Each column of \(\Pi\) equals \(\vec q\text{.}\)
-
\(\vec q\) is the unique eigenvector with eigenvalue \(1\text{.}\)
-
All eigenvalues of \(P\) satisfy \(|\lambda| \leq 1\text{.}\)
Focusing on (3), we see that an alternative way to find the unique steady-state vector \(\vec q\) is to take large powers of \(P\) and see what vector the columns of \(P^n\) are converging to. This will require a computer.
Example 7.4.
Suppose we have 5 web pages that link to each other according to the following diagram:
Note that Page A has direct links to pages \(\underline{\hspace{1.5in}}\text{.}\)
If a user on a page in this web is equally likely to go to any of the pages that their page links to, construct a stochastic matrix that represents how users navigate this web.
-
Note that the matrix \(P\) formed in Example 7.4 describes how users transition between pages in the web after clicking a single link.
-
What does \(P^2\) describe?
-
What does \(\displaystyle\lim_{n\rightarrow \infty} P^n\) describe?
-
By Theorem 7.3, if \(P \) is a regular stochastic matrix, then\begin{equation*} \lim_{n\rightarrow \infty} P^n = \begin{bmatrix} \vec q \amp \vec q \amp \cdots \amp \vec q \end{bmatrix}\text{.} \end{equation*}Each entry of the unique steady-state vector \(\vec q \) is describing the how likely someone is to be on that webpage in the long run.
-
Therefore, \(\vec q\) is describing the popularity or importance of each page in the web.
-
The PageRank is the ranking assigned to each page based on its importance, which is determined from \(\vec q\text{.}\) The highest ranked page has PageRank 1, the second has PageRank 2, and so on.
Note 7.5. Adjustment 1.
If a page has no outgoing links, a user moves to any page with equal probability. We call this modified stochastic matrix to \(P_*\text{.}\)
Example 7.6.
Note 7.7. Adjustment 2.
A user at any page will navigate to any page among those that their webpage links to with equal probability \(p\text{,}\) and to any page in the web with equal probability \(1-p\text{.}\) Then, the stochastic matrix becomes
\begin{equation*}
G = pP_* + (1-p)K\text{,}
\end{equation*}
where \(K\) is an \(n \times n\) stochastic matrix with every entry equal to \(\frac{1}{n}\text{.}\) The matrix \(G\) is called the Google Matrix. The value \(p\) is known as the damping factor. Google is said to use \(p=0.85\text{.}\)
Example 7.8.
Because \(G\) is a regular stochastic matrix, we have that for any initial probability vector we have that
\begin{equation*}
\lim_{n\rightarrow \infty}G^n\vec x_0 \to \vec q\text{.}
\end{equation*}
In practice, we can compute the PageRank for each page in the web by evaluating
\begin{equation*}
G^n
\end{equation*}
for large \(n\) and then using Theorem 7.3. The elements of the resulting columns of \(G^n\) give the PageRanks of each page in the web.
Example 7.9.
Let \(G\) be the Google matrix from Example 7.8. Assuming
\begin{equation*}
G^{10} = \begin{bmatrix} 0.2517 \amp 0.25171 \amp 0.25171 \amp 0.25171 \amp 0.25171 \\ 0.2985 \amp 0.29855 \amp 0.29836 \amp 0.29835 \amp 0.2985 \\ 0.17661 \amp 0.17655 \amp 0.17674 \amp 0.17675 \amp 0.17661 \\ 0.15676 \amp 0.15677 \amp 0.15677 \amp 0.15676 \amp 0.15677 \\ 0.11643 \amp 0.11641 \amp 0.11641 \amp 0.11642 \amp 0.11642 \end{bmatrix}\text{,}
\end{equation*}
determine the PageRank of each of the pages in the web.
Remark 7.10.
-
When PageRank was devised, in 1996, Yahoo! used humans to provide a "index for the Internet", which was 10 million pages.
-
The PageRank algortihm was produced as a competing method. The patent was awarded to Stanford University, and exclusively licensed to the newly formed Google corporation.
-
Brin and Page combined the PageRank algorithm with a webcrawler to provide regular updates to the Google matrix for the web.
-
The explosive growth of the web soon overwhelmed human based approaches to searching the internet.
Example 7.11.
Consider the following webpage:
(a)
(b)
Determine the PageRank of each page if
\begin{equation*}
G^{12} = \begin{bmatrix} 0.11627 \amp 0.1163 \amp 0.1163 \amp 0.1163 \amp 0.11631 \amp 0.11628 \amp 0.1163 \\ 0.16859 \amp 0.16856 \amp 0.16855 \amp 0.16856 \amp 0.16855 \amp 0.16859 \amp 0.16856 \\ 0.19129 \amp 0.19126 \amp 0.19125 \amp 0.19126 \amp 0.19124 \amp 0.19129 \amp 0.19126 \\ 0.09883 \amp 0.098847 \amp 0.09885 \amp 0.098845 \amp 0.098855 \amp 0.09885 \amp 0.098845 \\ 0.16402 \amp 0.16406 \amp 0.16407 \amp 0.16406 \amp 0.16408 \amp 0.16402 \amp 0.16406 \\ 0.16859 \amp 0.16856 \amp 0.16855 \amp 0.16856 \amp 0.16855 \amp 0.16859 \amp 0.16856 \\ 0.092403 \amp 0.092415 \amp 0.092418 \amp 0.092424 \amp 0.092421 \amp 0.092403 \amp 0.092414 \end{bmatrix}\text{.}
\end{equation*}
