- Form the A matrix. Then, introduce decay and form the B matrix as we
did in the course notes. (5 Points)
(A_matrix <- matrix(c(0,0,1/3,0,0,0,1/2,0,1/3,0,0,0,1/2,0,0,0,0,0,0,0,0,0,1/2,1,0,0,1/3,1/2,0,0,0,0,0,1/2,1/2,0), nrow=6, ncol=6))
## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.0000000 0.5000000 0.5 0.0 0.0000000 0.0
## [2,] 0.0000000 0.0000000 0.0 0.0 0.0000000 0.0
## [3,] 0.3333333 0.3333333 0.0 0.0 0.3333333 0.0
## [4,] 0.0000000 0.0000000 0.0 0.0 0.5000000 0.5
## [5,] 0.0000000 0.0000000 0.0 0.5 0.0000000 0.5
## [6,] 0.0000000 0.0000000 0.0 1.0 0.0000000 0.0
n <- 4
(B_matrix <- (A_matrix * 0.85) + (0.15/n))
## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.0375000 0.4625000 0.4625 0.0375 0.0375000 0.0375
## [2,] 0.0375000 0.0375000 0.0375 0.0375 0.0375000 0.0375
## [3,] 0.3208333 0.3208333 0.0375 0.0375 0.3208333 0.0375
## [4,] 0.0375000 0.0375000 0.0375 0.0375 0.4625000 0.4625
## [5,] 0.0375000 0.0375000 0.0375 0.4625 0.0375000 0.4625
## [6,] 0.0375000 0.0375000 0.0375 0.8875 0.0375000 0.0375
- Start with a uniform rank vector r and perform power iterations on B
till conver- gence. That is, compute the solution r = B^n × r. Attempt
this for a sufficiently large n so that r actually converges. (5
Points)
(R_vector <- matrix(c(.167,.167,.167,.167,.167,.167),nrow=6, ncol=1))
## [,1]
## [1,] 0.167
## [2,] 0.167
## [3,] 0.167
## [4,] 0.167
## [5,] 0.167
## [6,] 0.167
n <- 2
(B_matrix_n2 <- (B_matrix^n) %*% R_vector)
## [,1]
## [1,] 0.072384062
## [2,] 0.001409062
## [3,] 0.052274479
## [4,] 0.072384062
## [5,] 0.072384062
## [6,] 0.132712812
n <- 3
(B_matrix_n3 <- round(((B_matrix^n) %*% R_vector),3))
## [,1]
## [1,] 0.033
## [2,] 0.000
## [3,] 0.017
## [4,] 0.033
## [5,] 0.033
## [6,] 0.117
n <- 5
(B_matrix_n5 <- round(((B_matrix^n) %*% R_vector),3))
## [,1]
## [1,] 0.007
## [2,] 0.000
## [3,] 0.002
## [4,] 0.007
## [5,] 0.007
## [6,] 0.092
n <- 10
(B_matrix_n10 <- round(((B_matrix^n) %*% R_vector),3))
## [,1]
## [1,] 0.000
## [2,] 0.000
## [3,] 0.000
## [4,] 0.000
## [5,] 0.000
## [6,] 0.051
n <- 15
(B_matrix_n15 <- round(((B_matrix^n) %*% R_vector),3))
## [,1]
## [1,] 0.000
## [2,] 0.000
## [3,] 0.000
## [4,] 0.000
## [5,] 0.000
## [6,] 0.028
- Compute the eigen-decomposition of B and verify that you indeed get
an eigenvalue of 1 as the largest eigenvalue and that its corresponding
eigenvector is the same vector that you obtained in the previous power
iteration method. Further, this eigenvector has all positive entries and
it sums to 1.(10 points)
eigen(B_matrix)
## eigen() decomposition
## $values
## [1] 1.00988354 0.43758588 -0.42500000 -0.42500000 -0.34747279 -0.02499663
##
## $vectors
## [,1] [,2] [,3] [,4] [,5]
## [1,] -0.25439856 -0.7750410 -5.345225e-01 -5.345225e-01 -0.775256378
## [2,] -0.08292686 -0.0990471 -2.610981e-10 2.610983e-10 0.012910298
## [3,] -0.32452362 -0.5969656 5.345225e-01 5.345225e-01 0.631481410
## [4,] -0.52379669 0.1050925 -2.672612e-01 -2.672612e-01 0.003746204
## [5,] -0.52379669 0.1050925 -2.672612e-01 -2.672612e-01 0.003746204
## [6,] -0.52379669 0.1050925 5.345225e-01 5.345225e-01 0.003746204
## [,6]
## [1,] 0.54093188
## [2,] -0.62769027
## [3,] 0.55895706
## [4,] -0.01793166
## [5,] -0.01793166
## [6,] -0.01793166
eigen(B_matrix)$values
## [1] 1.00988354 0.43758588 -0.42500000 -0.42500000 -0.34747279 -0.02499663
round(eigen(B_matrix)$vector,3)
## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] -0.254 -0.775 -0.535 -0.535 -0.775 0.541
## [2,] -0.083 -0.099 0.000 0.000 0.013 -0.628
## [3,] -0.325 -0.597 0.535 0.535 0.631 0.559
## [4,] -0.524 0.105 -0.267 -0.267 0.004 -0.018
## [5,] -0.524 0.105 -0.267 -0.267 0.004 -0.018
## [6,] -0.524 0.105 0.535 0.535 0.004 -0.018
- Use the graph package in R and its page.rank method to compute the
Page Rank of the graph as given in A. Note that you don’t need to apply
decay. The package starts with a connected graph and applies decay
internally. Verify that you do get the same PageRank vector as the two
approaches above. (10 points)
(A_matrix_2 <- g <- graph.formula(1 -+ 2, 1 -+ 3, 3 -+ 2, 3 -+ 1, 3 -+ 5, 5 -+ 6, 5 -+ 4, 4 -+ 5, 4 -+ 6, 6 -+ 4))
## IGRAPH 4fe817e DN-- 6 10 --
## + attr: name (v/c)
## + edges from 4fe817e (vertex names):
## [1] 1->2 1->3 3->1 3->2 3->5 5->6 5->4 6->4 4->5 4->6
page.rank(A_matrix_2) #$vector
## $vector
## 1 2 3 5 6 4
## 0.05170475 0.07367926 0.05741241 0.19990381 0.26859608 0.34870369
##
## $value
## [1] 1
##
## $options
## NULL