You’ll verify for yourself that PageRank works by performing calculations on a small
universe of web pages.
Let’s use the 6 page universe that we had in the course notes. For this directed graph,
perform the following calculations in R.
Form the A matrix. Then, introduce decay and form the B matrix as we did in
the course notes
A <- matrix(c(0, 1/2, 1/2, 0, 0,  0,
              0, 0, 1, 0, 0, 0,
              1/4, 1/4, 0, 0, 1/4, 1/4,
              0, 0, 0, 0, 1/2, 1/2,
              0, 0, 0, 1/2, 0, 1/2,
              0, 0, 1/2, 1/2, 0, 0), nrow=6)
A
##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]  0.0    0 0.25  0.0  0.0  0.0
## [2,]  0.5    0 0.25  0.0  0.0  0.0
## [3,]  0.5    1 0.00  0.0  0.0  0.5
## [4,]  0.0    0 0.00  0.0  0.5  0.5
## [5,]  0.0    0 0.25  0.5  0.0  0.0
## [6,]  0.0    0 0.25  0.5  0.5  0.0
Start with a uniform rank vector r and perform power iterations on B till convergence.
That is, compute the solution r = Bn × r. Attempt this for a sufficiently
large n so that r actually converges.
Introduce decay d = 0.85
decay <- 0.85

B <- decay*A + ((1- decay)/6)
B
##       [,1]  [,2]   [,3]  [,4]  [,5]  [,6]
## [1,] 0.025 0.025 0.2375 0.025 0.025 0.025
## [2,] 0.450 0.025 0.2375 0.025 0.025 0.025
## [3,] 0.450 0.875 0.0250 0.025 0.025 0.450
## [4,] 0.025 0.025 0.0250 0.025 0.450 0.450
## [5,] 0.025 0.025 0.2375 0.450 0.025 0.025
## [6,] 0.025 0.025 0.2375 0.450 0.450 0.025
r <- matrix(c(1/6,1/6,1/6,1/6,1/6,1/6),nrow=6)
r
##           [,1]
## [1,] 0.1666667
## [2,] 0.1666667
## [3,] 0.1666667
## [4,] 0.1666667
## [5,] 0.1666667
## [6,] 0.1666667
powermatrix <- function (B,r,power) {

X <- B%*%r
temp <- diag(6)

  for (n in 1:power) {
       X<- temp%*%X
       X<- B%*%X
       #print(X)
       #print(n)
       n<-n+1
      }
return(X)
}

powermatrix(B,r,200)
##            [,1]
## [1,] 0.07735886
## [2,] 0.11023638
## [3,] 0.24639464
## [4,] 0.18635389
## [5,] 0.15655927
## [6,] 0.22309696

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.

B <- decay*A + ((1- decay)/6)
#B
# Eigen values
eigen(B, only.values = FALSE)$vectors[,1] 
## [1] -0.1784825+0i -0.2543376+0i -0.5684822+0i -0.4299561+0i -0.3612138+0i
## [6] -0.5147297+0i
# scale out the Eigen vectors by 1 / sum of ejgen vectors.
eigen_vectors<- eigen(B, only.values = FALSE)$vectors[,1] * (1/ sum(eigen(B, only.values = FALSE)$vectors[,1] ))
data.frame(eigen_vectors)
##   eigen_vectors
## 1 0.07735886+0i
## 2 0.11023638+0i
## 3 0.24639464+0i
## 4 0.18635389+0i
## 5 0.15655927+0i
## 6 0.22309696+0i
# quick validation of equality of eigen values and power matrix rank...  data.frame(eigen_vectors)  == power.df
power.df<- powermatrix(B,r,200)
f<- (data.frame(eigen_vectors))
f<- as.numeric(f[,1])
power.df<- data.frame(power.df)

x<- data.frame(as.numeric(f))
y<- data.frame(as.numeric(power.df[,1]))

all.equal(x,y, check.names= FALSE)
## [1] TRUE
Use the igraph 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.

You can also embed plots, for example:

library(igraph)
## 
## Attaching package: 'igraph'
## 
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## 
## The following object is masked from 'package:base':
## 
##     union
# I created the relationships between the six nodes and saved them in text file called g.network.txt
txt.network<-read.table("C:/CUNY/Courses/IS605/Assignments/Assignment10/g.network.txt", sep=',', dec='.', header=T)
txt.network
##    From To Weight
## 1     1  2   0.50
## 2     1  3   0.50
## 3     2  3   1.00
## 4     3  1   0.25
## 5     3  2   0.25
## 6     3  5   0.25
## 7     3  6   0.25
## 8     4  5   0.50
## 9     4  6   0.50
## 10    5  4   0.50
## 11    5  6   0.50
## 12    6  3   0.50
## 13    6  4   0.50
g.network <- graph.data.frame(txt.network, directed=TRUE)

# Verify that you do get the same PageRank vector as 
# the two approaches above.

data.frame(page.rank(g.network)$vector)
##   page.rank.g.network..vector
## 1                  0.07735886
## 2                  0.11023638
## 3                  0.24639464
## 4                  0.18635389
## 5                  0.15655927
## 6                  0.22309696
# We can also color the connecting edges differently depending on the 'weight'.  
E(g.network)$color<-ifelse(E(g.network)$Weight==.25, "blue", ifelse(E(g.network)$Weight==1, "red", "grey"))


plot( g.network,
      #layout=layout.fruchterman.reingold,
      #layout=layout.circle,
      #vertex.size=5,
      main='Toy Example with 6 URLs')