Remaking Google PageRank Algorithm in Python

Introduction

• Google PageRank is the algorithm used by the Google search engine that ranks relevant webpages based on how "popular" they are.
• The metric of popularity is measured by how many links do webpages have to reach other webpages.
• The next section demonstrates how this algorithm basically works.

Process

• In general, the Internet contains N number of webpages.
  Imagine a tiny internet of only three webpages: W1, W2, W3.
• A large matrix A stores how many links does a column site have to go to a row site.
  It basically means that each column is linked to a row. For instance:

  $$ A=\begin{bmatrix}0&0&1\\1&0&0\\1&1&0\end{bmatrix}\longrightarrow \begin{matrix}&a&b&c\\a&0&0&1\\b&1&0&0\\c&1&1&0\end{matrix} $$

• If a website links to n sites, each of those sites is (1/n) times accessible through that website.
  This information is kept in a probability matrix P.

  $$ P=\begin{bmatrix}0&0&1\\0.5&0&0\\0.5&1&0\end{bmatrix} $$

• A new matrix G is made.

  $$ G= 0.85(P)+ 0.15\begin{bmatrix} \frac{1}{N}&\frac{1}{N}&\frac{1}{N}\\ \frac{1}{N}&\frac{1}{N}&\frac{1}{N}\\ \frac{1}{N}&\frac{1}{N}&\frac{1}{N}\end{bmatrix} $$

  The second term in the addition states: there could be a small chance (15%) that:
  The user randomly teleports to a different webpage instead of following links.
  This 15% also helps the algorithm to not reach some dead ends.

  $$ \Rightarrow G= 0.85 \begin{bmatrix}0&0&1\\0.5&0&0\\0.5&1&0\end{bmatrix} + 0.15\begin{bmatrix}\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\ \frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\ \frac{1}{3}&\frac{1}{3}&\frac{1}{3}\end{bmatrix}= \begin{bmatrix}0.05&0.05&0.9\\0.475&0.05&0.05\\0.475&0.9&0.05\end{bmatrix} $$

• The matrix G is multiplied by a column matrix R containing N elements, all of them equal to (1/N).
  

  $$ R= \begin{bmatrix}\frac{1}{N}\\\frac{1}{N}\\\frac{1}{N}\end{bmatrix}= \begin{bmatrix}\frac{1}{3}\\\frac{1}{3}\\\frac{1}{3}\end{bmatrix}= \begin{bmatrix}0.333\\0.333\\0.333\end{bmatrix} $$

  $$ R_{1} = G\times R = \begin{bmatrix}0.05&0.05&0.9\\0.475&0.05&0.05\\0.475&0.9&0.05\end{bmatrix} \begin{bmatrix}0.333\\0.333\\0.333\end{bmatrix}= \begin{bmatrix}0.333\\0.191\\0.475\end{bmatrix} $$

• The matrix G is then multiplied to the new product above.

  $$ R_{2} = G\times R_{1} = \begin{bmatrix}0.05&0.05&0.9\\0.475&0.05&0.05\\0.475&0.9&0.05\end{bmatrix} \begin{bmatrix}0.333\\0.191\\0.475\end{bmatrix}= \begin{bmatrix}0.454\\0.191\\0.353\end{bmatrix} $$

• This step is repeated many times until the product shows little to no change.
  After many iterations, the product settles down to:

  $$ R_{f} = \begin{bmatrix}0.388\\0.215\\0.397\end{bmatrix} $$

  This final matrix ranks the corresponing webpages:

  $$ \begin{matrix}W1&\rightarrow&0.388\\W2&\rightarrow&0.215\\W3&\rightarrow&0.397\end{matrix} \Longrightarrow \begin{bmatrix}W3&\rightarrow&0.397\\W1&\rightarrow&0.388\\W2&\rightarrow&0.215\end{bmatrix}$$

• The next section demonstrates how this process was programmed in Python.

Program

• The main program was created using several small programs combined into one.
• Here is a flowchart that demonstrates the flow of program:




• Let us take a closer look at the files.
1. Data extraction    
2. Creating matrix from query    
3. Creating probability matrix    
4. Creating the matrix G    
5. The iteration step    
6. The main program    

1. Data extraction

• In this demo, we have eight (.txt) files that act as websites, each with the followinf info:



Webpage name	Content inside	Links towards
W1	news, clothes, food	W3, W8
W2	animals, movies	W7, W5
W3	food, clothes, education	W8, W1, W5
W4	people, shopping, movies	W7, W2
W5	movies, news, food	W3, W1
W6	movies, clothes	W5, W8
W7	people, animals, shopping	W4, W8, W2
W8	people, education, clothes	W6



• This image shows how one of those websites (.txt) looks like:


• This is the snippet of the code written in extractdata.py

2. Creating matrix from query

• This is the snippet of the code written in processquery.py

3. Creating probability matrix

• This is the snippet of the code written in probtransmtrx.py

• The exception is that a webpage may not link to any other webpage.
  Then it is assumed that the user jumps to a different webpage.
  So, the completely zero column is asigned the value (1/N)

4. Creating the matrix G

• This is the snippet of the code written in googlemtrx.py

• The scalarmultiply.py file is imported to multiply 0.85 to the probability matrix.
  This is the snippet of the code written in scalarmultiply.py

5. The iteration step

• This is the snippet of the code written in poweriterat.py

• The matricesmultiply.py file is imported to multiply the matrices.
  This is the snippet of the code written in matricesmultiply.py

6. The main program

• These are snippets of the code written in the main program:

Output

• Here is a video that demonstrates the main program.

Closing

• This program emphasises the need of matrices in technology, especially for search engines like Google.
• Fun fact: this program was inspired by the research done during completion of a school assignment.
• Here are some challenges that were encountered during development of the project:
  • Some parts of the program were inefficient.
    One such problem was the exception handling in the creation of the probability matrix.
    The issue was rectified by gathering more insights on the real PageRank algorithm, using Google.
  • Usage of multiple lists and dictionaries made the program confusing.
    So the program was simplified as much as possible to avoid confusion.

Note From The Dev.

I would sincerely like to thank the organisers on Devpost.com for giving me an opportunity to showcase
this project. It was really fun to work on it and I am satisfied with how it came out.
If you acknowledge the effort, consider leaving a comment on this project in my portfolio on Devpost.com.
Thank you for reading.
— Samrat Saxena