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...)


So the eigen vector matrix $R=[PR(p_1)\;PR(p_2)\;...\;PR(p_3)]^T$ follows the following mathematical equation. \begin{equation} \begin{bmatrix} R \end{bmatrix} = \begin{bmatrix} (1-\frac{d}{N})\\ (1-\frac{d}{N})\\ .\\ .\\ .\\ (1-\frac{d}{N}) \end{bmatrix}+d \begin{bmatrix} l(p_{1},p_{1}) & l(p_{1},p_{2})&.&.&.&.&.&.&l(p_{i},p_{N})\\ l(p_{1},p_{1})&.&.&.&.&.&.&.&.\\ .&.&.&.&.&.&.&l(p_{j},p_{j})&.\\ l(p_{N},p_{1})&.&.&.&.&.&.&.&l(p_{N},p_{N}) \end{bmatrix}R \end{equation}

We initialize our iteration using an eigenvector $R$. Function $l$($p_i$,$p_j$) shows the links between pages, if there is no link to this page, its value will be zero. We can represent this matrix as following equation $R = [(1-d)/N] +dLR$. For the first iteration we calculate, $LR$, for second iteration we calculate, $L(LR)$, and so on. Iteration continues till values of matrix $L(L^nR)$ stop changing. The matrix $ L^nR$, provides ranking of the pages.

A Simple Example

For simplicity let us assume that we have a small Internet consisting of just 4 web sites www.page1.com, www.page2.com, www.page3.com, www.page4.com, referencing each other in the manner suggested by the figure below.


Fig 1. Graph for web page linking

< Prev.Page   1   2   3   Next page>