tutorialpoint.org

# Google page ranking algorithm(cont'd...)

### Example(cont'd...)

In our model, each page has equal importance. Node 1 has 3 outgoing edges, so it will pass on 1/3 of its importance to each of the other 3 nodes. Node 3 has only one outgoing edge, so it will pass on all of its importance to node 1. In general, if a node has $k$ outgoing edges, it will pass on $1/k$ of its importance to each of the nodes that it links to. Let us better visualize the process by assigning weights to each edge as shown in figure 2.

Fig 2. Assigning weight of each page

The transition matrix of the graph $L$ becomes $$\begin{bmatrix} L \end{bmatrix} = \begin{bmatrix} 0&0&1& \frac {1}{2}\\ \frac {1}{3}&0&0&0\\ \frac {1}{3}&\frac {1}{2}&0&\frac {1}{2}\\ \frac {1}{3}&\frac {1}{2}&0&0 \end{bmatrix}$$

Now, as described earlier, through the iteration the values of $L^nR$ becomes as follows $\begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.25\\ 0.25\\ 0.25\\ 0.25 \end{bmatrix}$,$\begin{bmatrix} L \end{bmatrix} \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.37\\ 0.08\\ 0.33\\ 0.20 \end{bmatrix}$, $\ \begin{bmatrix} L \end{bmatrix}^2 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.43\\ 0.12\\ 0.27\\ 0.16 \end{bmatrix}$,

$\begin{bmatrix} L \end{bmatrix}^3 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.35\\ 0.14\\ 0.29\\ 0.20 \end{bmatrix}$, $\ \begin{bmatrix} L \end{bmatrix}^4 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.39\\ 0.11\\ 0.29\\ 0.19 \end{bmatrix}$, $\ \begin{bmatrix} L \end{bmatrix}^5 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.39\\ 0.13\\ 0.28\\ 0.19 \end{bmatrix}$,

$\ \begin{bmatrix} L \end{bmatrix}^6 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.28\\ 0.13\\ 0.29\\ 0.19 \end{bmatrix}$, $\ \begin{bmatrix} L \end{bmatrix}^7 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.38\\ 0.12\\ 0.29\\ 0.19 \end{bmatrix}$, $\ \begin{bmatrix} L \end{bmatrix}^8 \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} 0.38\\ 0.12\\ 0.29\\ 0.19 \end{bmatrix}$

Final matrix $L^8R$ is called PageRank'' matrix. From this matrix we get following results. Page 1 receives first rank, Page 3 receives second rank, Page 4, and Page 2 receive third and fourth rank respectively. From these results, we can see that the pages those are connected to more pages, have higher ranking.