Skip to main content

Section A.2 Computer Science: PageRank

Subsection A.2.1 Activities

Activity A.2.1. The $978,000,000,000 Problem.

In the picture below, each circle represents a webpage, and each arrow represents a link from one page to another.

Figure 81. 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 $978,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 x1,x2,x3 be the importance of the three pages respectively.

Figure 82. A three-webpage network
  1. x1 splits its endorsement in half between x2 and x3

  2. x2 sends all of its endorsement to x1

  3. x3 sends all of its endorsement to x2.

This corresponds to the page rank system:

x2=x112x1+x3=x212x1=x3

Observation A.2.4.

Figure 83. A three-webpage network
x2=x112x1+x3=x212x1=x3
[01012011200][x1x2x3]=[x1x2x3]

By writing this linear system in terms of matrix multiplication, we obtain the page rank matrix A=[01012011200] and page rank vector x=[x1x2x3].

Thus, computing the importance of pages on a network is equivalent to solving the matrix equation Ax=1x.

Activity A.2.5.

Thus, our $978,000,000,000 problem is what kind of problem?

[010120121200][x1x2x3]=1[x1x2x3]
  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 x satisfying Ax=1x for the following network's page rank matrix A.

That is, find the eigenspace associated with λ=1 for the matrix A, and choose a vector from that eigenspace.

Figure 84. A three-webpage network
A=[01012011200]

Observation A.2.7.

Row-reducing AI=[11012111201][102012000] yields the basic eigenvector [221].

Therefore, we may conclude that pages 1 and 2 are equally important, and both pages are twice as important as page 3.

Activity A.2.8.

Compute the 7×7 page rank matrix for the following network.

Figure 85. A seven-webpage network

For example, since website 1 distributes its endorsement equally between 2 and 4, the first column is [012012000].

Activity A.2.9.

Find a page rank vector for the given page rank matrix.

A=[0120000012001001201200000120120001200000120000012000012012120]
Figure 86. A seven-webpage network

Which webpage is most important?

Observation A.2.10.

Since a page rank vector for the network is given by x, it's reasonable to consider page 2 as the most important page.

x=[2422.5001]

Based upon this page rank vector, here is a complete ranking of all seven pages from most important to least important:

2,4,1,3,7,5,6
Figure 87. 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.

Figure 88. Another seven-webpage network

Subsection A.2.2 Slideshow

Slideshow of activities available at https://teambasedinquirylearning.github.io/linear-algebra/2022/pagerank.slides.html.

You have attempted 1 of 1 activities on this page.