Math 272: Google's PageRank Algorithm

Names: 

	You will work on this lab in pairs. Please upload your completed file to Moodle by 1pm Friday: https://lms.ats.amherst.edu/mod/assign/view.php?id=310122

The following Exercises 1, 2, 3, 11, 12 and 13 are taken from the article by Bryan and Leise, available on the website. The code to analyze the web in Figure 1 and some helpful tips are given below:

A={{0,0,1,1/2},{1/3,0,0,0},{1/3,1/2,0,1/2},{1/3,1/2,0,0}};A//MatrixForm

Eigensystem[A]//N//MatrixForm

v=Eigensystem[A][[2,1]](* grabs eigenvector with eigenvalue 1, that is in the 2nd row, 1st column *)

u=v/Sum[Abs[v[[k]]],{k,1,4}] (* divides vector by the sum of its components, indexed 1 through 4, so that vector u's components will sum to 1 *)

Based on the vector u, page 1 has the highest ranking, followed by page 3, then page 4, then page 2.

Another way to find the sum of the absolute values of a vector's components (also known as the “1-norm”) is the Mathematica command Norm[v,1], so we could have said u=v/Norm[v,1].

Norm[v,1] (* without the 1 in this command, you'll just the ordinary length of v, so be sure to include it *)

Norm[u,1]

Figure 1.

Exercise 1. Suppose the people who own page 3 in the web of Figure 1 are infuriated by the fact that its importance score, computed using formula (1), is lower than the score of page 1. In an attempt to boost page 3’s score, they create a page 5  that links to page 3; page 3 also links to page 5. Does this boost page 3’s score above that of page 1?

Exercise 2. Construct a web consisting of three or more subwebs and verify that the dimension of the eigenspace for eigenvalue 1 equals (or exceeds) the number of subwebs.

Figure 2.

Exercise 3. Add a link from page 5 to page 1 in the web of Figure 2. The resulting web, considered as an undirected graph, is connected.  What is the dimension of the eigenspace for eigenvalue 1?

To find M in Mathematica, you can say M=(1-m)A+m/n.  That will add m/n to every entry of the matrix, so you don’t need to create a matrix S.

Exercise 11. Consider again the web in Figure 1, with the addition of a page 5 that links to page 3, where page 3 also links to page 5. Calculate the new ranking by finding the eigenvector of M (corresponding to λ = 1) that has positive components summing to 1. Use m = 0.15.

Exercise 12. Add a sixth page that links to every page of the web in the previous exercise, but to which no other page links. Rank the pages using A, then using M with m = 0.15, and compare the results.M 
k 
x0 
−q1 and 
M 
k 
x0 
−q1 
M 
k 
−1 x0 
−q1 for k = 1, 5, 10, 50 using an initial guess x0 not too close to the actual 
eigenvector q (so that you can watch the convergence). Determine c = max1 
≤j n 1 2 minM| and the absolute value of the second-largest eigenvalue of

Exercise 13*. (This exercise has been slightly modified from the original one in the article.) Determine the ranking of the pages in the web of Figure 2 given by M with m = 0.15.M 
k 
x0 
−q1 and 
M 
k 
x0 
−q1 
M 
k 
−1 x0 
−q1 for k = 1, 5, 10, 50 using an initial guess x0 not too close to the actual 
eigenvector q (so that you can watch the convergence). Determine c = max1 
≤j n 1 2 minM| and the absolute value of the second-largest eigenvalue of