Every time we pose a question to Google—whether it’s “Why isn’t 11 pronounced onety-one?” or “Why isn’t there an E grade?”—we are utilizing one of the most formidable search engines globally. In the background, Google operates intricate algorithms that sift through billions of web pages to provide the most pertinent answers. PageRank is one of the core algorithms driving this process. Created in 1998 by Larry Page and Sergey Brin, Google’s co-founders, PageRank transformed search by evaluating pages based on their significance, authority, and relevance.
In this article, we will simplify how the PageRank mechanism operates, using straightforward keyword analysis and mathematical formulas. Additionally, we’ll delve into the essential framework of querying and indexing and clarify how a search query is processed to yield ranked web pages.
What is PageRank?
PageRank is a mechanism that assesses the “significance” of web pages based on the quantity and quality of links directed to them. Consider every link to a page as an endorsement. The greater the number of quality links from respected sites a page possesses, the more authoritative it is deemed.
Google encounters two main challenges:
– Space Complexity: The storage necessary to manage an extensive data corpus.
– Time Complexity: The time required to compute and deliver relevant results.
To tackle this, Google employs two key operations: Querying and Indexing.
The Query Class: Deciphering the Search Input
Before a search result can be calculated, the search input must be refined and comprehended through the following stages:
1. Parsing: HTML/XML is refined to extract textual content.
2. Tokenizing: The text input is divided into useful words (tokens), eliminating spaces and punctuation.
3. Removing Stop Words: Common terms like “the,” “is,” or “that” are omitted as they contribute little to search relevance.
4. Stemming: Words are simplified to their foundational or root form. For example, “running” becomes “run”.
Example Keywords Extracted from Input Phrases:
Given the phrases:
– “Dogs, dogs, dogs”
– “The running dogs”
– “Adopt a dog”
– “Cute video of a dog running”
These would tokenize to something like:
– [Dog, Dog, Dog]
– [Run, Dog]
– [Adopt, Dog]
– [Cute, Video, Dog, Run]
The Index Class: Determining Word Importance
The following phase is to assess the importance of each term on a webpage. To accomplish this, two principal calculations are executed:
1. Term Frequency (TF): Indicates how frequently a keyword shows up on a page.
Formula:
TF = x / y
Where:
– x = number of instances a particular word appears
– y = number of instances the most repeated word on the page appears
Example:
The word “run” appears once, while the most frequent word (e.g., “dog”) appears four times in the content.
TF = 1 / 4 = 0.25
2. Inverse Document Frequency (IDF): Reflects how commonplace or rare a word is throughout all documents.
Formula:
IDF = log(n / n(i))
Where:
– n = total number of documents
– n(i) = number of documents containing the word i
Example:
Assuming “run” shows up in two documents among four.
IDF = log(4 / 2) = log(2) = 0.301
Merging TF and IDF aids in computing the Relevance Score:
Relevance = TF × IDF
For “run”: 0.25 × 0.301 = 0.075
This relevance score enables Google to ascertain which pages are more pertinent for a given keyword query.
Determining Page Authority with PageRank
Now that we’ve evaluated page relevance through keywords, we need to account for how one page’s authority enhances another’s through links. This is the crux of the PageRank algorithm.
Assumptions:
– If numerous pages link to one page, it’s likely important.
– If high-quality pages link to a page, that connection holds more authority.
– If a page links to fewer pages, its “vote” is more significant.
– Pages that are closer together (in terms of web clicks) impact each other more.
The weight a page P accumulates from another page M is calculated as:
w(PM) = e / t + r(M) / n(PM)
Where:
– e = damping factor (generally 0.15)
– t = total number of pages
– r(M) = rank of the linking page M
– n(PM) = number of outbound links from page M
Example:
If “Dogs, Dogs, Dogs” links to “The Running Dog”, and its rank is 0.537, and it links to