闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

AM 147: Computational Methods and Applications: Winter 2022

Homework #9

Problem 1

Power iteration to compute PageRank (50 points)

We learnt in Lec. 24-25 that for a given Word Wide Web, or equivalently given its adjacency matrix A, the PageRank p is simply the dominant eigenvector of the corresponding Google matrix G (see Lec. 25, p. 3–6).

(a) [5 + 10 = 15 points]

Write a MATLAB code YourlastnameYourfirstnameHW9p1 .m that loads the 500 × 500 adja- cency matrix A from the ﬁle AdjacencyMatrix .txt in the CANVAS Files Section, folder: HW Problems. Use this A matrix to construct the column-stochastic matrix S . You must write the S matrix construction code in a way that dangling nodes are accounted as per Lec. 24, p. 7. In other words, your code should be general enough to handle any A that has one or more zero columns.

(b) [10 + 15 = 25 points]

In the same .m ﬁle in part (a), deﬁne the damping vector alpha = 0 .25 :0 .25 :1. Each entry of alpha denotes a speciﬁc damping factor α in Lec. 25, p. 3. For each entry of alpha, perform 10 power iterations on the corresponding Google matrix to compute the associated damped PageR- ank p(α). For all power iterations, use the initial guess (1/n, 1/n, . . . , 1/n)⊤ with n = 500.

Write a MATLAB function TVdist .m that takes two probability vectors a, b of same size as 1

input, and outputs the total variation (TV) distance TV(a, b) := "a − b"1 , that is, the half of

the 1 norm of a − b.

For each α , obtain the convergence trend as the following ﬁgure. Plot power iteration index k in the horizontal axis, and the “relative error during iteration” TV(pk+1 (α), pk(α)) in the vertical axis using the MATLAB command semilogy. To do so, you need to call TVdist in the executable YourlastnameYourfirstnameHW9p1 .m.

This should generate a single ﬁgure with four lineplots in four different linecolors: red for α = 0.25, green for α = 0.50, blue for α = 0.75, black for α = 1.00. Please also use MATLAB legend in your ﬁgure to clarify which curve is which. Review Lec. 25, p. 9 and the lecture video to get intuition on how this plot should look like.

Recall that α = 1 is the true (undamped) PageRank. Use the same .m ﬁle as in part (a), to print the loss of accuracy in PageRank due to damping in the command window, as the following three % errors: