Exploring HITS and PageRank Algorithms in Search Engines

Introduction

In today's modern era, information is readily available at our fingertips with just a simple click. Have you ever wondered how one can sift through the vast ocean of data on the internet and retrieve precise information in a matter of seconds? The answer lies in the intricate world of search engines, such as Google, Yahoo, Bing, and many more. But what principles underlie their remarkable functionality? The answer is LINEAR ALGEBRA.

Linear algebra plays a pivotal role in the operation of search engines.

In this project, we will delve into the topic: "How Search Engines Work?" Web search engines like Google, which we use daily, employ link analysis to enhance their search results. The foundation of the web's hyperlink structure is rooted in MATRIX THEORY. It is the utilization of link analysis and the framework of linear algebra that has revolutionized web search. Two renowned algorithms, HITS and PageRank, both developed in 1998, have had a profound impact on the field of search engines, dramatically improving their performance.

Prior to 1998, the functionality of search engines was subpar. Due to the sheer number of web pages, a simple query would yield an extensive list of relevant pages, often numbering in the thousands. Users were required to meticulously sift through this list to identify the most relevant pages. Furthermore, the order in which the pages were presented offered little assistance because of the prevalent spamming practices. Spammers would employ tactics such as excessive use of meta-tags, falsely claiming their pages contained popular search terms that were not actually present.

Additionally, they would employ invisible text with white font on a white background to manipulate search engine rankings.

Basic Definitions

What is a Hyperlink?

A hyperlink is a connection from one hypertext document (a text containing links to other documents) to another document or location, activated by clicking on a highlighted word or image. To provide a clearer understanding, consider the following examples:

• Example 1: http://www.facebook.com
• Example 2: http://www.google.com
• Example 3: https://en.wikipedia.org/wiki/HITS_algorithm (This link was referenced in building this project)

What is an Algorithm?

In our daily lives, we unconsciously operate with numerous algorithms. An algorithm can be defined as a series of steps to perform a specific task. For example, to prepare tea in the kitchen, one must follow the following steps:

1. Take tea leaves
2. Boil water
3. Add sugar and tea leaves (then wait 3-4 minutes)
4. Add milk

Similarly, in the realm of computers, an algorithm is a set of instructions designed to execute a specific task. To elicit a response from a computer, we must provide it with clear and executable steps. For instance, to open a calculator, you would instruct the computer as follows:

1. Open Start
2. Click on Accessories
3. Choose Calculator

It is evident that to accomplish any task, precise and methodical steps must be defined and followed. These defined steps are what constitute an algorithm. Therefore, we are constantly surrounded by algorithms in various aspects of our lives.

Algorithms in Use

In the present day, numerous algorithms are in active use, such as HITS, PageRank, TrustRank, and more. These algorithms find their primary application in search engines, aiding in data processing, mathematical calculations, and various other mathematical operations.

An algorithm, in essence, is a systematic method or procedure for solving problems. It is a common misconception that computer algorithms are exclusively written in machine language. However, algorithms can be expressed in natural languages as well. Moreover, a single problem can often be tackled using multiple algorithms. For example, to determine the rank of a matrix, various approaches like row-echelon form, reduced row-echelon form, column method, and more are employed. Similarly, finding the inverse of a matrix involves techniques such as Cayley-Hamilton theorem and Gauss-Jordan method. When multiple methods exist, they are prioritized based on their execution time. An algorithm with a shorter execution time takes precedence. For instance, when multiplying two matrices, methods like row by row multiplication, column by column multiplication, and the Strassen Method are available. In our case, the Strassen Method algorithm is the most efficient, as it requires the least time for execution. This demonstrates that algorithms are independent of any particular programming language.

HITS Algorithm

The HITS (Hyperlink-Induced Topic Search) algorithm, developed by Jon Kleinberg during his postdoctoral studies at IBM Almaden, and now affiliated with Cornell University, aims to enhance the ranking of websites. Commonly referred to as Hubs and Authorities, it stands as one of the most prominent algorithms utilized by major search engines. The HITS algorithm derives its foundation from a pattern observed by Kleinberg among web pages. Some pages function as hubs, featuring numerous outbound links, while others serve as authorities in specific subjects, attracting numerous inbound links. Kleinberg noted a correlation between high-quality hubs pointing to high-quality authorities and vice versa. This led him to assign both a hub score (hi) and an authority score (ai) to each page (i).

Formally, for each page (i), Kleinberg defined the hub score at iteration (k), hi(k), and the authority score, ai(k), as follows:

Here, e(ij) represents a hyperlink from page (i) to page (j), and E is the set of hyperlinks. To initiate the computation of scores for each page, uniform scores are assigned initially, where hi(1) = 1/n and ai(1) = 1/n, with (n) representing the number of pages in a designated neighborhood set for the query list. The neighborhood set comprises all pages in the query list and those linked to or from the query pages. Depending on the query, the neighborhood set can range from a hundred to a thousand pages, enabling latent semantic associations to be established. The hub and authority scores are iteratively refined until they converge to stable values.

Utilizing linear algebra, the summation equations can be expressed in matrix form. Let (h) and (a) be column vectors holding the hub and authority scores, respectively. Let (L) represent the adjacency matrix for the neighborhood set, where (Lij = 1) if page (i) links to page (j), and (0) otherwise. This implies:

While the above equations encompass the fundamental linear algebraic principles of the HITS method, several additional complexities must be considered. Key concerns include convergence, existence, uniqueness, and numerical computation of these scores.

HITS is a widely adopted algorithm in search engines for effectively retrieving specific data from extensive data sources, such as the Internet. In this context, a "Hub" represents a page with numerous outbound links, while an "Authority" is a page linked to by many hubs.

Problem

Let's delve into a problem to better comprehend the utilization of matrices within the HITS Algorithm.

Problem Statement:

Given Matrix A:

	N1	N2	N3	N4
N1	0	1	1	0
N2	1	0	1	0
N3	1	1	0	0
N4	0	0	0	1

Our objective is to identify the best hub and authority scores of Matrix A using the HITS Algorithm for k = 2, where k represents the number of iterations.

Solution:

Let's begin by representing the nodes in Matrix A:

Nodes (Column Wise)	N1	N2	N3	N4
Nodes (Row Wise)	N1	N2	N3	N4

Here, N1, N2, N3, and N4 represent the nodes, which in the context of this problem, refer to webpages. We will convert this matrix into a graph representation, where '0' signifies no connection (not linked), and '1' signifies a connection (linked).

For the given matrix, each arrow in the diagram represents a link from the head node to the tail node. For example, N1 → N3 implies that N1 contains a link to N3. It's important to note that N represents a node (webpage).

Now, let's define two crucial concepts: outdegree and indegree.

Outdegree: The outdegree of a node is the number of links going out from that node to other nodes.

Indegree: The indegree of a node is the number of links pointing to that node from other nodes.

Now, we can compile the following table:

Nodes	Out-Degree	In-Degree
N1	3	1
N2	2	1
N3	3	0
N4	1	1

According to the definition, outdegree is considered as the hub, and indegree is considered as the authority. However, we are interested in determining the ranking of the nodes. Therefore, we will first establish separate priority lists for hubs and authorities.

HUB Priority: N1 > N2 > N4 > N3

AUTHORITY Priority: N3 > N1 = N2 = N4

Now, to resolve the duality between N1 being the top priority for hubs and N3 for authorities, we will apply the HITS Algorithm. For this purpose, we introduce two vectors, U and V, where:

U: Hub weight vector

V: Authority weight vector

Their relationship can be expressed as follows:

U = A * V

V = A^T * U (where A^T represents the transpose of matrix A)

We must calculate the transpose of A (A^T), and to begin the process, we will assume either U or V to compute the value of the other. Let's assume U = [1, 1, 1, 1] and find the value of V.

V = A^T * U

This gives us the authority scores for all nodes.

Next, we need to find the value of U:

U = A * V

This provides us with the hub scores for all nodes.

Finally, we obtain the values of U and V which enable the search engine to determine the optimal results for its searches. It's important to note that this analysis was conducted for k = 1, representing a single iteration. Similar analyses can be carried out for additional iterations, which may yield rankings different from those obtained using the outdegree and indegree methods. Higher scores indicate a higher priority for displaying a page (node) at the top of the list, ultimately improving search engine performance.

PageRank Algorithm

The PageRank Algorithm is among the most widely used algorithms in search engines. It was developed by Larry Page and Sergey Brin during their graduate studies. This algorithm comprises a set of rules and instructions designed to help users find their desired search queries on the vast internet. Unlike conventional methods that rely on word frequency matching, PageRank operates on the premise that a website's importance is determined by the number of links it receives from other websites. It assesses both the number of outbound links (Outlink) and inbound links (Inlink) for each website, as opposed to the concept of Hubs and Authorities. PageRank assigns a PageRank score to every webpage based on specific criteria.

PageRank was a seminal development in the field of web search, becoming one of the earliest link analysis programs and the first of its kind at Google. Sergey Brin and Larry Page, then computer science graduate students at Stanford University, conceived Google and PageRank. They employed a recursive approach similar to that of Kleinberg's, premised on the idea that "A page is important if it is pointed to by other important pages." In other words, the importance of a page, represented by its PageRank score, is determined by the cumulative PageRanks of all pages linking to it. Consequently, when a significant page links to multiple destinations, its weight (PageRank) should be distributed proportionally among them. For instance, if YAHOO! points to your page, you benefit from this endorsement, but you shouldn't receive the full weight of YAHOO! since it links to numerous other pages. If YAHOO! links to 999 other pages in addition to yours, you should only receive credit for 1/1000th of YAHOO!'s PageRank.

Following this rationale, Brin and Page formulated a recursive definition for PageRank:

Where:

• ri(k) is the PageRank of page i at iteration k
• Ii is the set of pages pointing to page i
• ∣Oj∣ is the number of outlinks from page j

PageRank commences with an initial uniform rank for all pages, i.e., ri(0) = 1/n, and iteratively refines these scores, where n represents the total number of web pages.

Similar to HITS, we can express this process using matrix notation. Let the row vector π(k)T represent the PageRank vector at the kth iteration. Therefore, the summation equation for PageRank can be succinctly written as:

Here, H is a row-normalized hyperlink matrix, i.e., hij = 1/│Oij│ if there is a link from page i to page j, and 0 otherwise. However, this iterative process encounters convergence issues, as it can cycle or have a limit that depends on the initial vector.

To address these concerns, Brin and Page refined the PageRank concept by introducing an irreducible aperiodic Markov chain characterized by a primitive transition probability matrix. Irreducibility ensures the existence of a unique stationary distribution vector πT, which becomes the PageRank vector. The Power method, combined with a primitive stochastic iteration matrix, always converges to πT independently of the starting vector. The rate of asymptotic convergence is determined by the magnitude of the subdominant eigenvalue λ2 of the transition matrix.

Google converts the hyperlink structure of the web into a primitive stochastic matrix. If there are n pages on the web, the matrix H, whose element hij represents the probability of transitioning from page i to page j in one click, is employed. The basic model assumes h 0 with pTe = 1 and can be used instead of the uniform vector eT/n.

However, merely creating a stochastic matrix is insufficient to ensure the existence of a unique stationary distribution vector required for a well-defined PageRank. Irreducibility must be added to the mix since the web's link structure is reducible (the web graph is not strongly connected). Therefore, an adjustment to make the matrix S irreducible is necessary. This leads to the introduction of the Google matrix, defined as:

Where:

• 0 ≤ α ≤ 1
• E = eeT/n (where e represents a column vector of all ones)

Google later replaced the uniform vector eT/n with a more general probability vector vT (where E = evT) to allow flexibility for adjustments to PageRanks and personalization.

Since G is a convex combination of the two stochastic matrices S and E, it is both stochastic and irreducible. Moreover, every node is now directly connected to every other node (although the probability of transition may be very small in some cases), making G > 0. As a result, G is a primitive matrix, guaranteeing that the power method, π(k+1)T = π(k)TG, will converge to a unique stationary distribution πT independently of the starting vector. This forms the mathematical foundation of Google's PageRank vector.

PageRank plays a crucial role in modern web search engines, helping to rank web pages based on their importance and relevance.

Conclusion

In this lab report, we have explored two fundamental search engine algorithms, namely the HITS (Hyperlink-Induced Topic Search) algorithm and the PageRank algorithm. These algorithms have revolutionized the way search engines rank and retrieve web pages, enabling users to find relevant information efficiently in the vast expanse of the internet.

HITS Algorithm

The HITS algorithm, also known as Hubs and Authorities, is a link analysis algorithm that rates web pages based on their roles as either hubs or authorities within a network of hyperlinks. Jon Kleinberg's development of the HITS algorithm aimed to address the challenge of refining search engine results by identifying authoritative sources and central hubs of information.

Through a series of iterations and matrix calculations, we saw how HITS assigns hub scores and authority scores to web pages, providing a means to prioritize pages based on their contributions to the web's hyperlink structure. By understanding HITS, we gain insight into how search engines identify important web pages and improve search results.

PageRank Algorithm

The PageRank algorithm, conceived by Larry Page and Sergey Brin during their graduate studies, introduced a groundbreaking approach to web page ranking. PageRank evaluates the importance of web pages based on the number and quality of links they receive from other pages. It departs from traditional keyword-based ranking systems by emphasizing the concept that a page is valuable if it is linked to by other authoritative pages.

We delved into the mathematical foundations of PageRank, which involve the creation of matrices, such as the Hyperlink Matrix (H), Stochastic Matrix (S), Uniform Probability Matrix (E), and the Google Matrix (G). These matrices allow us to compute PageRank scores iteratively, ensuring that highly linked and reputable pages receive higher rankings in search results.

Significance of Search Engine Algorithms

Search engine algorithms, like HITS and PageRank, play a vital role in our digital lives. They enable us to navigate the internet effectively, find information rapidly, and connect with valuable resources. Understanding the inner workings of these algorithms empowers us to create and optimize web content for search engine visibility.

In conclusion, search engines have evolved significantly over the years, thanks to innovative algorithms that continue to enhance the user's search experience. As technology advances, we can anticipate further refinements and developments in search engine algorithms, making the internet an even more accessible and informative space for all users.