Introduction Case

The order of paid advertisements that you see on Google is partially determined by Google adwords. However, the website ranking for all other websites is determined by the Google PageRank algorithm. This exercise will cover this algorithm, using the following example.

PageRank

STEP 2: PageRank Update

In the following step we will update the initially assigned PageRanks according to the following algorithm:

Each page divides its current PageRank equally across out-going links and passes these equal shares to the pages it points to.
If a page has no out-going links, it passes all its current PageRank to itself.
Each page updates its new PageRank to be the sum of the shares it receives.

Since 5 nodes point to node A, A’s new PageRank is the sum of 5 numbers:

(1/8)/2 from node D,
(1/8)/2 from node E,
(1/8)/1 from node F,
(1/8)/1 from node G,
(1/8)/1 from node H.

We will choose to update the PageRanks 200 times. Therefore, we will iterate 200 times over the following algorithm. In the next step, we will optimize this k.

for (i in 1:200){
  pagerank[i+1,"A"] <- round(pagerank[i,]$F + pagerank[i,]$G + pagerank[i,]$H + 0.5*pagerank[i,]$D + 0.5*pagerank[i,]$E,8)
  pagerank[i+1,"B"] <- round(0.5*pagerank[i,]$A,8)
  pagerank[i+1,"C"] <- round(0.5*pagerank[i,]$A,8)
  pagerank[i+1,"D"] <- round(0.5*pagerank[i,]$B,8)
  pagerank[i+1,"E"] <- round(0.5*pagerank[i,]$B,8)
  pagerank[i+1,"F"] <- round(0.5*pagerank[i,]$C,8)
  pagerank[i+1,"G"] <- round(0.5*pagerank[i,]$C,8)
  pagerank[i+1,"H"] <- round(0.5*pagerank[i,]$D + 0.5*pagerank[i,]$E,8)
}

head(pagerank)
         A        B        C         D         E         F         G        H
1 0.125000 0.125000 0.125000 0.1250000 0.1250000 0.1250000 0.1250000 0.125000
2 0.500000 0.062500 0.062500 0.0625000 0.0625000 0.0625000 0.0625000 0.125000
3 0.312500 0.250000 0.250000 0.0312500 0.0312500 0.0312500 0.0312500 0.062500
4 0.156250 0.156250 0.156250 0.1250000 0.1250000 0.1250000 0.1250000 0.031250
5 0.406250 0.078125 0.078125 0.0781250 0.0781250 0.0781250 0.0781250 0.125000
6 0.359375 0.203125 0.203125 0.0390625 0.0390625 0.0390625 0.0390625 0.078125

Practice

PageRank_Exercise

Exercise

Update the PageRanks of the network that is shown above. You can set the number of iterations (k) equal to 200 and the numbers after the comma equal to 8.