tutorialpoint.org

Blogs

Algorithm for Friendship, Affair, and Love

IIT Patna: A Journey Began

Google page ranking algorithm

Crawling a website

Performance measure of a website

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.

page_ranking_graph

Fig 2. Assigning weight of each page

The transition matrix of the graph $L$ becomes \begin{equation} \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} \end{equation}

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.

< Prev.Page   1   2   3   Next page>