# Before we begin, let's load the libraries. %pylab notebook import numpy as np import numpy.linalg as la from readonly.PageRankFunctions import * np.set_printoptions(suppress=True)

# Replace the ??? here with the probability of clicking a link to each website when leaving Website F (FaceSpace). L = np.array([[0, 1/2, 1/3, 0, 0, 0, ], [1/3, 0, 0, 0, 1/2, 0, ], [1/3, 1/2, 0, 1, 0, 1/2, ], [1/3, 0, 1/3, 0, 1/2, 1/2, ], [0, 0, 0, 0, 0, 0, ], [0, 0, 1/3, 0, 0, 0, ]])

eVals, eVecs = la.eig(L) # Gets the eigenvalues and vectors order = np.absolute(eVals).argsort()[::-1] # Orders them by their eigenvalues eVals = eVals[order] eVecs = eVecs[:,order] r = eVecs[:, 0] # Sets r to be the principal eigenvector 100 * np.real(r / np.sum(r)) # Make this eigenvector sum to one, then multiply by 100 Procrastinating Pats

r = 100 * np.ones(6) / 6 # Sets up this vector (6 entries of 1/6 × 100 each) r # Shows it's value

r = L @ r # Apply matrix L to r r # Show it's value # Re-run this cell multiple times to converge to the correct answer.

r = 100 * np.ones(6) / 6 # Sets up this vector (6 entries of 1/6 × 100 each) for i in np.arange(100) : # Repeat 100 times r = L @ r r

r = 100 * np.ones(6) / 6 # Sets up this vector (6 entries of 1/6 × 100 each) lastR = r r = L @ r i = 0 while la.norm(lastR - r) > 0.01 : lastR = r r = L @ r i += 1 print(str(i) + " iterations to convergence.") r

# We'll call this one L2, to distinguish it from the previous L. L2 = np.array([[0, 1/2, 1/3, 0, 0, 0, 0 ], [1/3, 0, 0, 0, 1/2, 0, 0 ], [1/3, 1/2, 0, 1, 0, 1/3, 0 ], [1/3, 0, 1/3, 0, 1/2, 1/3, 0 ], [0, 0, 0, 0, 0, 0, 0 ], [0, 0, 1/3, 0, 0, 0, 0 ], [0, 0, 0, 0, 0, 1/3, 1 ]])

r = 100 * np.ones(7) / 7 # Sets up this vector (6 entries of 1/6 × 100 each) lastR = r r = L2 @ r i = 0 while la.norm(lastR - r) > 0.01 : lastR = r r = L2 @ r i += 1 print(str(i) + " iterations to convergence.") r

d = 0.5 # Feel free to play with this parameter after running the code once. M = d * L2 + (1-d)/7 * np.ones([7, 7]) # np.ones() is the J matrix, with ones for each entry.

r = 100 * np.ones(7) / 7 # Sets up this vector (6 entries of 1/6 × 100 each) lastR = r r = M @ r i = 0 while la.norm(lastR - r) > 0.01 : lastR = r r = M @ r i += 1 print(str(i) + " iterations to convergence.") r

# PACKAGE # Here are the imports again, just in case you need them. # There is no need to edit or submit this cell. import numpy as np import numpy.linalg as la from readonly.PageRankFunctions import * np.set_printoptions(suppress=True)

# GRADED FUNCTION # Complete this function to provide the PageRank for an arbitrarily sized internet. # I.e. the principal eigenvector of the damped system, using the power iteration method. # (Normalisation doesn't matter here) # The functions inputs are the linkMatrix, and d the damping parameter - as defined in this worksheet. # (The damping parameter, d, will be set by the function - no need to set this yourself.) def pageRank(linkMatrix, d) : n = linkMatrix.shape[0] M = d * linkMatrix + (1-d)/n * np.ones([n, n]) r = 100 * np.ones(n) / n # Sets up this vector (6 entries of 1/6 × 100 each) lastR = r r = M @ r i = 0 while la.norm(lastR - r) > 0.01 : lastR = r r = M @ r i += 1 print(str(i) + " iterations to convergence.") return r

# Use the following function to generate internets of different sizes. generate_internet(5)

# Test your PageRank method against the built in "eig" method. # You should see yours is a lot faster for large internets L = generate_internet(10)

pageRank(L, 1)

# Do note, this is calculating the eigenvalues of the link matrix, L, # without any damping. It may give different results that your pageRank function. # If you wish, you could modify this cell to include damping. # (There is no credit for this though) eVals, eVecs = la.eig(L) # Gets the eigenvalues and vectors order = np.absolute(eVals).argsort()[::-1] # Orders them by their eigenvalues eVals = eVals[order] eVecs = eVecs[:,order] r = eVecs[:, 0] 100 * np.real(r / np.sum(r))

# You may wish to view the PageRank graphically. # This code will draw a bar chart, for each (numbered) website on the generated internet, # The height of each bar will be the score in the PageRank. # Run this code to see the PageRank for each internet you generate. # Hopefully you should see what you might expect # - there are a few clusters of important websites, but most on the internet are rubbish! %pylab notebook r = pageRank(generate_internet(100), 0.9) plt.bar(arange(r.shape[0]), r);