Calculate the PageRank of a Page Linkage Diagram

Question

Consider the below page linkage diagram among web pages A, B, C and D. As per page rank algorithm, what is the expected ranking among pages. Comment on the results.
page_linkage_diagram

Solution

==================================================================================================
PageRank of a page A is given by,

$\begin{align*} \left\ PR(A) = (1-d) + d[\frac{PR(T1)}{C(T1)} + .... + \frac{PR(Tn)}{C(Tn)}] \end{align*}$

Let d = 0.85 and initial guess be: PR(A) = PR(B) = PR(C) = PR(D) = 0.
C(B) is the number of outgoing links from page B.
There are no outgoing edges from D. This means that D is a sink.
In order to handle this, let’s add edges to every page in the diagram from the sink (D).

The updated linkage diagram is as below:
page_linkage_diagram_sink

$\Huge Iteration-1$

$\begin{align*} \left\ PR(A) = (1-0.85) + 0.85*[\frac{PR(C)}{C(C)} + \frac{PR(D)}{C(D)}] \left\ = 0.15 + 0.85*[\frac{0}{2} + \frac{0}{3}] = 0.15 \end{align*}$

$\begin{align*} \left\ PR(B) = 0.15 + 0.85*[\frac{PR(A)}{C(A)} + \frac{PR(D)}{C(D)}] \left\ = 0.15 + 0.85*[\frac{0.15}{1} + \frac{0}{3}] = 0.28 \end{align*}$

$\begin{align*} \left\ PR(C) = 0.15 + 0.85*[\frac{PR(B)}{C(B)} + \frac{PR(D)}{C(D)}] \left\ = 0.15 + 0.85*[\frac{0.28}{1} + \frac{0}{3}] = 0.39 \end{align*}$

$\begin{align*} \left\ PR(D) = 0.15 + 0.85*[\frac{PR(C)}{C(C)}] \left\ = 0.15 + 0.85*[\frac{0.39}{2}] = 0.32 \end{align*}$

$\Huge Iteration-2$

$\begin{align*} \left\ PR(A) = 0.15 + 0.85*[\frac{0.39}{2} + \frac{0.32}{3}] = 0.41 \end{align*}$

$\begin{align*} \left\ PR(B) = 0.15 + 0.85*[\frac{0.41}{1} + \frac{0.32}{3}] = 0.59 \end{align*}$

$\begin{align*} \left\ PR(C) = 0.15 + 0.85*[\frac{0.59}{1} + \frac{0.32}{3}] = 0.75 \end{align*}$

$\begin{align*} \left\ PR(D) = 0.15 + 0.85*[\frac{0.75}{2}] = 0.47 \end{align*}$

$\Huge Iteration-3$

$\begin{align*} \left\ PR(A) = 0.15 + 0.85*[\frac{0.75}{2} + \frac{0.47}{3}] = 0.61 \end{align*}$

$\begin{align*} \left\ PR(B) = 0.15 + 0.85*[\frac{0.61}{1} + \frac{0.47}{3}] = 0.80 \end{align*}$

$\begin{align*} \left\ PR(C) = 0.15 + 0.85*[\frac{0.80}{1} + \frac{0.47}{3}] = 0.96 \end{align*}$

$\begin{align*} \left\ PR(D) = 0.15 + 0.85*[\frac{0.96}{2}] = 0.56 \end{align*}$

As expected, the sink has the lowest rank. We can also see that the average page rank is converging to 1.

Question

Solution

Subscribe to Ehan Ghalib!

Leave a Reply Cancel Reply