Description
1. A ring-like network of links between web pages is shown below. Assume all feasible
transitions are equally likely.
a) Find the unweighted adjacency matrix for this network.
b) Find the weighted adjacency matrix for this network. Note that the entries in
each column of the weighted adjacency matrix are nonnegative and sum to one.
Such a matrix is called a column stochastic matrix.
c) Suppose the entries of a vector b sum to one. It is easy to show that the entries
of Ab also sum to one since each column of the weighted adjacency matrix A
sums to one.
The PageRank algorithm thus uses the power method without
normalizing the length of the vector at each iteration. Each iteration gives a new
vector with positive entries that sum to one. Find the estimate of the PageRank
vector after one iteration using an initial vector b0 =
1
8
1
1
.
.
.
1
. The initial vector
b0 gives equal importance to all pages.
d) Find the estimate of the PageRank vector after 1000 iterations of the power
method using an initial vector b0 =
1
8
1
1
.
.
.
1
. A skeleton script is available. You
will need to enter the adjacency matrix into the code.
e) Do any nodes seem to be more important than other nodes? Explain.
2. A hub-like network of links between web pages is shown below. Assume all feasible
transitions are equally likely.
a) Find the unweighted adjacency matrix for this network.
b) Find the weighted adjacency matrix for this network.
c) Find the estimate of the PageRank vector after one iteration using an initial
vector b0 =
1
9
1
1
.
.
.
1
.
d) Find the estimate of the PageRank vector after 1000 iterations of the power
method using an initial vector b0 =
1
9
1
1
.
.
.
1
.
e) Are any nodes more important than other nodes? Explain.
f) Experiment with the number of iterations of the power method that are needed
to find an answer that is correct to three decimal places.
3. Consider expressing the SVD of a rank-r matrix X as
X =
∑r
i=1
σiuiv
T
i
where σi
is the ith singular value with left singular vector ui and right singular vector
vi
. Is the sign of the singular vectors unique? Why or why not? Hint: Consider
replacing u1 with u˜1 = −u1.
