Skip to main content
Logo image

Linear Algebra for Team-Based Inquiry Learning PREVIEW Edition

Steven Clontz, Drew Lewis

Section A.2 Computer Science: PageRank

Subsection A.2.1 Activities

Activity A.2.1. The $2,110,000,000,000 Problem.

In the picture below, each circle represents a webpage, and each arrow represents a link from one page to another.
🔗
described in detail following the image
A network consisting of seven numbered circles connected by red arrows. The circles are arranged in two rows: the top row from left to right is circles 1, 4, 5, and 6. The bottom row, from left to right, is circles 2, 3, and 7. Circles 2, 3, and 7 are directly below circles 1,4, and 5 respectively; no circle is below circle 6.
🔗
Circle 1 has arrows pointing right to circle 4 and down to circle 2. An incoming arrow arrives upward from circle 2.
🔗
Circle 2 has two arrows pointing out, one back up to circle 1, and one to the right to circle 3. Arrows come in from circle 1 above, from circle 4 which is above and to the right, and from circle 7 which is to the right past circle 3.
🔗
Circle 3 has a single arrow coming in from the left from circle 2. Two arrows go outward: one up to circle 4, and one to the right to circle 7.
🔗
Circle 4 has arrows come in from circle 1 on the left, circle 3 below, and circle 7 below and right. A single arrow points out, down and to the left to circle 2.
🔗
Circle 5 has one arrow arriving: from the right from circle 6. Two arrows point out: one to the right to circle 6 and one down to circle 7.
🔗
Circle 6 has one arrow coming in from the left from circle 5. Two arrows point out: to the left to circle 5 and down and left to circle 7.
🔗
Circle 7 has two arrows pointing out: left to circle 2 and up and left to circle 4. Three arrows point in: from the left from circle 3, from above from circle 5, and from above and right from circle 6.
🔗
Figure 78. A seven-webpage network
🔗
Based on how these pages link to each other, write a list of the 7 webpages in order from most important to least important.
🔗
🔗

Observation A.2.2. The $2,110,000,000,000 Idea.

Links are endorsements. That is:
🔗
  1. A webpage is important if it is linked to (endorsed) by important pages.
    🔗
    🔗
  2. A webpage distributes its importance equally among all the pages it links to (endorses).
    🔗
    🔗
🔗

Example A.2.3.

Consider this small network with only three pages. Let \(x_1, x_2, x_3\) be the importance of the three pages respectively.
🔗
described in detail following the image
A network consisting of three numbered circles connected by 4 red arrows. Arrows point from circle 1 to both circle 2 and circle 3. An arrow points from circle 2 to circle 1, and the final arrow points from circle 3 to circle 2.
🔗
Figure 79. A three-webpage network
🔗
  1. \(x_1\) splits its endorsement in half between \(x_2\) and \(x_3\)
    🔗
  2. \(x_2\) sends all of its endorsement to \(x_1\)
    🔗
  3. \(x_3\) sends all of its endorsement to \(x_2\text{.}\)
    🔗
This corresponds to the page rank system:
🔗
\begin{alignat*}{4} && x_2 && &=& x_1 \\ \frac{1}{2} x_1&& &+&x_3 &=& x_2\\ \frac{1}{2} x_1&& && &=& x_3 \end{alignat*}
🔗

Observation A.2.4.

described in detail following the image
The image from Figure 79 is reproduced.
Figure 80. A three-webpage network
🔗
\begin{alignat*}{4} && x_2 && &=& x_1 \\ \frac{1}{2} x_1&& &+&x_3 &=& x_2\\ \frac{1}{2} x_1&& && &=& x_3 \end{alignat*}
🔗
\begin{equation*} \left[\begin{array}{ccc}0&1&0\\\frac{1}{2}&0 & 1\\\frac{1}{2}&0&0\end{array}\right] \left[\begin{array}{c}x_1\\x_2\\x_3\end{array}\right] = \left[\begin{array}{c}x_1\\x_2\\x_3\end{array}\right] \end{equation*}
🔗
By writing this linear system in terms of matrix multiplication, we obtain the page rank matrix \(A = \left[\begin{array}{ccc} 0 & 1 & 0 \\ \frac{1}{2} & 0 & 1 \\ \frac{1}{2} & 0 & 0 \end{array}\right]\) and page rank vector \(\vec{x}=\left[\begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array}\right]\text{.}\)
🔗
Thus, computing the importance of pages on a network is equivalent to solving the matrix equation \(A\vec{x}=1\vec{x}\text{.}\)
🔗
🔗

Activity A.2.5.

Thus, our $2,110,000,000,000 problem is what kind of problem?
\begin{equation*} \left[\begin{array}{ccc}0&1&0\\\frac{1}{2}&0&\frac{1}{2}\\\frac{1}{2}&0&0\end{array}\right] \left[\begin{array}{c}x_1\\x_2\\x_3\end{array}\right] = 1\left[\begin{array}{c}x_1\\x_2\\x_3\end{array}\right] \end{equation*}
🔗
  1. An antiderivative problem
    🔗
  2. A bijection problem
    🔗
  3. A cofactoring problem
    🔗
  4. A determinant problem
    🔗
  5. An eigenvector problem
    🔗
🔗

Activity A.2.6.

Find a page rank vector \(\vec x\) satisfying \(A\vec x=1\vec x\) for the following network’s page rank matrix \(A\text{.}\)
🔗
That is, find the eigenspace associated with \(\lambda=1\) for the matrix \(A\text{,}\) and choose a vector from that eigenspace.
🔗
described in detail following the image
The image from Figure 79 is reproduced.
Figure 81. A three-webpage network
🔗
\begin{equation*} A = \left[\begin{array}{ccc} 0 & 1 & 0 \\ \frac{1}{2} & 0 & 1 \\ \frac{1}{2} & 0 & 0 \end{array}\right] \end{equation*}
🔗
🔗

Observation A.2.7.

Row-reducing \(A-I = \left[\begin{array}{ccc} -1 & 1 & 0 \\ \frac{1}{2} & -1 & 1 \\ \frac{1}{2} & 0 & -1 \end{array}\right] \sim \left[\begin{array}{ccc} 1 & 0 & -2 \\ 0 & 1 & -2 \\ 0 & 0 & 0 \end{array}\right]\) yields the basic eigenvector \(\left[\begin{array}{c} 2 \\ 2 \\1 \end{array}\right]\text{.}\)
🔗
Therefore, we may conclude that pages \(1\) and \(2\) are equally important, and both pages are twice as important as page \(3\text{.}\)
🔗
🔗

Activity A.2.8.

Compute the \(7 \times 7\) page rank matrix for the following network.
🔗
described in detail following the image
The network from Figure 78 is reproduced.
Figure 82. A seven-webpage network
🔗
For example, since website \(1\) distributes its endorsement equally between \(2\) and \(4\text{,}\) the first column is \(\left[\begin{array}{c} 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ 0 \\ 0 \end{array}\right]\text{.}\)
🔗
🔗

Activity A.2.9.

Find a page rank vector for the given page rank matrix.
🔗
\begin{equation*} A=\left[\begin{array}{ccccccc} 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & 0 & 1 & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{array}\right] \end{equation*}
🔗
described in detail following the image
The network from Figure 78 is reproduced.
Figure 83. A seven-webpage network
🔗
Which webpage is most important?
🔗
🔗

Observation A.2.10.

Since a page rank vector for the network is given by \(\vec x\text{,}\) it’s reasonable to consider page \(2\) as the most important page.
\begin{equation*} \vec{x} = \left[\begin{array}{c} 2 \\ 4 \\2 \\ 2.5 \\ 0 \\ 0 \\ 1\end{array}\right] \end{equation*}
🔗
Based on this page rank vector, here is a complete ranking of all seven pages from most important to least important:
\begin{equation*} 2, 4, 1, 3, 7, 5, 6 \end{equation*}
🔗
described in detail following the image
The network from Figure 78 is reproduced.
Figure 84. A seven-webpage network
🔗
🔗

Activity A.2.11.

Given the following diagram, use a page rank vector to rank the pages \(1\) through \(7\) in order from most important to least important.
🔗
described in detail following the image
A different network with seven numbered circles connected by red arrows.
🔗
  • Circle 1 has arrows outward to circles 2 and 5, and inward from circle 3.
    🔗
  • Circle 2 has arrows outward to circles 5 and 7, and inward from circles 1,3,6, and 7.
    🔗
  • Circle 3 has arrows outward to circles 1 and 2, and a single arrow inward from circle 4.
    🔗
  • Circle 4 has a single arrow outward to circle 3, and a single arrow inward from circle 7.
    🔗
  • Circle 5 has a single arrow outward to circle 6, and arrows inward from circles 1,2, and 6.
    🔗
  • Circle 6 has arrows outward to circles 5 and 2, and a single arrow inward from circle 6.
    🔗
  • Circle 7 has arrows outward to circles 2 and 4, and a single arrow inward from circle 2.
    🔗
Figure 85. Another seven-webpage network
🔗
🔗
🔗
🔗
PrevTopNext