# Google Page Rank Algorithm



In this notebook, we learn and code up a simplified version of Google's Page Rank Algorithm, which is a direct application of Eigenvectors and Eigenvalues we learnt in Linear Algebra.



Reference to the original paper: $\href{http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf}{here}$

Reference to blog:
$\href{https://www.dhruvonmath.com/2019/03/20/pagerank/}{here}$

Google Page Rank Algorithm predicts a rank for each webpage on the internet. This rank depends on the number of ingoing and outgoing links to a webpage.

You can think of rank of a webpage as follows: If a web page gets rank $1$, it means that a random web searcher who clicks links randomly would spend the most amount of time in this web page. If a web page gets rank $2$, it means that a random web searcher who keeps clicking links randomly would spend the second most amount of time in this web page and so on and so forth.

Given the structure of the web, it is very obvious to model the web as a Graph Data structure. The nodes of the graph are the web pages. Edges of the graph represent links between the web pages.

Note that the graph is a directed graph. There maybe a link from webpage 'A' to webpage 'B', it may not always be the case that there exists a link from webpage 'B' to webpage 'A'.

A graph with $N$ nodes can be represented with a $N \times N$ matrix. This matrix is known as Adjacency matrix.

$A_{ij}$ represents the weight of the edge connecting the $j^{th}$ node to the $i^{th}$ node. 
We can think of this adjacency matrix as concatenation of $N$ column vectors. The $i^{th}$ column defines the edges from node $i$ to all other nodes.

**Exercise:**
Can you draw the graph corresponding to the following adjacency matrix?

\begin{equation}
A = \begin{pmatrix}
0 & 1/2 & 0 & 0\\
1/3 & 0 & 0 & 1/2\\
1/3 & 0 & 0 & 1/2\\
1/3 & 1/2 & 1 & 0\\
\end{pmatrix}
\end{equation}

**Exercise:**
Can you write down the adjacency matrix for the following graph?


Let us normalize each column of the adjacency matrix so that the entries sum upto $1$. This is because we want to output the rank as a probability value of the amount of time spent on that webpage.

We start with equiprobable ranks for all webpages. 

We update the ranks($r$) as follows:
\begin{equation}
r(i) = \underset{j}{\sum} r(j) * A(i, j)
\end{equation}
\begin{equation}
r' = A.r
\end{equation}
The above is a recursive definition.


```python
import numpy as np
```


```python
# Complete the below function to return A after normalizing
# each of it's columns
# Normalizing a column means sum of entries in each column adds to 1.
# PLEASE USE VECTORISED CODE FOR EFFICIENCY
def normalize_columns(A):
    sums = A.sum(axis=0)
    return (A/sums)
    
```


```python
A = np.array([[0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0]])
print(normalize_columns(A))
```

    [[0.         0.         1.         0.5       ]
     [0.33333333 0.         0.         0.        ]
     [0.33333333 0.5        0.         0.5       ]
     [0.33333333 0.5        0.         0.        ]]


**Expected Output:**

[[0.         0.         1.         0.5       ]
 [0.33333333 0.         0.         0.        ]
 [0.33333333 0.5        0.         0.5       ]
 [0.33333333 0.5        0.         0.        ]]


```python
# Complete the below function to take a matrix A and a vector r.
# Return the updated rank.
# PLEASE USE VECTORISED CODE WITHOUT LOOPS
def update_rank(A, r):
    r = np.dot(A,r)
    return r
```


```python
# Complete the below function to check if two vectors a and b are equal
# Since we are dealing with real numbers, 
# we say two elements(x and y) are equal if abs(x - y) <= epsilon

# PLEASE USE VECTORISED CODE WITHOUT LOOPS
ep = 1e-8
def check_equality(a, b):
    val = np.abs(a - b) <= ep
    if(np.any(val[:]== False)):
        return False
    return True
    
```


```python
# Complete the below function to compute ranks iteratively until 
# ranks stabilise.
# We say ranks become stabilised when the after updation the ranks
# do not change.
# Use the functions defined above.
def compute_iteratively(A, initial_rank):
    curr_rank = initial_rank
    prev_rank=np.zeros(initial_rank.shape[0])
    while(check_equality(curr_rank,prev_rank)!=True):
        prev_rank = curr_rank
        curr_rank = update_rank(A,curr_rank)
    return curr_rank
        
        
```


```python
# Complete the below function to compute final ranks at one shot using
# eigen values and eigen vectors
# You may use inbuilt functions to compute eigenvectors and eigenvalues
import scipy.linalg as la
def compute_using_eig(A, initial_rank):
    eigenvals, eigenvecs = la.eig(A)
    egi = eigenvals.astype(int)
    i = np.where(egi==1)
    i = i[0][0]
    
    
    return normalize_columns(eigenvecs[:,i])
```


```python
A = np.array([[0, 1, 0, 0], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, 1, 0]])
A = normalize_columns(A)
r = np.array([0.25, 0.25, 0.25, 0.25])
print("Rank computed iteratively: \n", compute_iteratively(A, r))
print("Rank computed using eigen values and eigen vectors: \n", compute_using_eig(A, r))
```

    Rank computed iteratively: 
     [0.12 0.24 0.24 0.4 ]
    Rank computed using eigen values and eigen vectors: 
     [0.12 0.24 0.24 0.4 ]


    /usr/lib/python3/dist-packages/ipykernel_launcher.py:7: ComplexWarning: Casting complex values to real discards the imaginary part
      import sys


**Expected Output:**

Rank computed iteratively: 
 [0.12       0.24       0.24       0.39999999]

Rank computed using eigen values and eigen vectors: 
 [0.12 0.24 0.24 0.4 ]


```python
A = np.array([[0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0]])
A = normalize_columns(A)
r = np.array([0.25, 0.25, 0.25, 0.25])
print("Rank computed iteratively: \n", compute_iteratively(A, r))
print("Rank computed using eigen values and eigen vectors: \n", compute_using_eig(A, r))
```

    Rank computed iteratively: 
     [0.38709677 0.12903226 0.29032258 0.19354839]
    Rank computed using eigen values and eigen vectors: 
     [0.38709677+0.j 0.12903226+0.j 0.29032258+0.j 0.19354839+0.j]


    /usr/lib/python3/dist-packages/ipykernel_launcher.py:7: ComplexWarning: Casting complex values to real discards the imaginary part
      import sys


**Expected Output:**

Rank computed iteratively: 

[0.38709677 0.12903226 0.29032258 0.19354839]

Rank computed using eigen values and eigen vectors: 

[0.38709677 0.12903226 0.29032258 0.19354839]

f109cf6edb299e272771fba288461a5b6090e987
ipynb
Jupyter Notebook
day8/morning/Google Page Rank Algorithm Assignment/Page Rank Algorithm.ipynb
avani17101/CVIT-Workshop
0339021123b82dfa55c6f6fa4d8c4322ecf7e687
MIT
2020-06-27T06:38:10.000Z
2021-06-01T15:37:33.000Z
day8/morning/Google Page Rank Algorithm Assignment/Page Rank Algorithm.ipynb
avani17101/CVIT-Workshop
0339021123b82dfa55c6f6fa4d8c4322ecf7e687
MIT
2020-06-08T18:41:11.000Z
2020-07-27T10:25:24.000Z
day8/morning/Google Page Rank Algorithm Assignment/Page Rank Algorithm.ipynb
avani17101/CVIT-Workshop
0339021123b82dfa55c6f6fa4d8c4322ecf7e687
MIT
Qwen/Qwen-72B
1. YES
2. YES