Comparing HITS and PageRank: Web Mining Algorithms Analysis

1. Introduction

Ranking algorithms play a critical role in the functionality of search engines, significantly impacting the overall user experience. A substantial body of research has been dedicated to these algorithms, as they fundamentally influence the perceived quality of a search engine by its users. In the early years of the World Wide Web, when the web consisted of only a few hundred pages, manual ranking schemes, such as the one used by the Yahoo! search engine [5], were sufficient.

However, with the explosive growth of web content, it became impractical to manually rank millions of web pages.

This necessitated the development of automated ranking algorithms. This paper aims to provide an overview of the various ranking algorithms that have been developed to enhance the search experience for users across the World Wide Web.

1.1 Structure of the Report

The report is structured as follows:

1. Section 2 discusses the necessity and importance of ranking algorithms in modern search engines.
2. Section 3 presents a comprehensive survey of major ranking algorithms that have been developed.
   Get quality help now

   

   Dr. Karlyna PhD

   Verified writer

   Proficient in: Technology

   4.7 (235)

   “ Amazing writer! I am really satisfied with her work. An excellent price as well. ”

   

   +84 relevant experts are online

   Hire writer

3. Section 4 offers concluding remarks on the topic.

2. Need for Ranking Algorithms

The vast expanse of the World Wide Web consists of billions of web pages, making it highly probable that when a user initiates a search query, thousands of web pages will contain the queried word or phrase. It is clearly impractical for a user to manually examine all of these pages.

As a result, one of the primary objectives of a search engine is to swiftly provide the user with results that are most likely to be beneficial while minimizing response time.

When a search engine returns the results of a user's query, only a limited number of documents can be presented to the user. Therefore, it is of utmost importance that the most relevant documents are included in the search results and are prioritized for display. This critical task is accomplished through the use of a ranking function.

A well-designed ranking function that prioritizes documents according to their relevance to a user's query will significantly enhance the user's satisfaction with the search engine. It is this aspect of search engines that we aim to explore and discuss in this paper.

3. Overview of Major Ranking Algorithms

In this section, we will provide an overview of some major ranking algorithms.

3.1 Page Rank Algorithm

The PageRank algorithm, widely known as PageRank [3, 7], serves as the cornerstone of the immensely popular Google search engine. PageRank is founded on the Random Surfer model, which posits that a user randomly clicks on links within web pages and, when bored, switches to another page randomly. Under this model, the user exhibits no bias towards any specific page or link. PageRank (PR) represents the probability of a page being visited by such a user.

PageRank is primarily based on the link structure of the web, specifically analyzing the in-links and out-links of web pages to assign ranks. The algorithm operates on the premise that when one page links to another, it effectively casts a vote in favor of the linked page. Consequently, each in-link to a page contributes to its importance within this framework, a concept analogous to academic citations where a paper's significance increases with the number of citations or backlinks it receives.

PageRank operates recursively, with a page's PR dependent not only on the number of in-links but also on the PR of the pages linking to it. This means that a page not only gains importance through its in-links but also by receiving contributions from pages with high PR. A page distributes its PR value equally among all its out-links, and the contribution of its PR to outgoing links is inversely proportional to the number of out-links a page has. For example, if page A is linked to by pages B, C, and D, where B has 4 out-links, C has 1 out-link, and D has 2 out-links, then:

PR(A) = PR(B)/4 + PR(C) + PR(D)/2

The damping factor 'd' is introduced to account for the probability of a user switching to another random page. Typically, 'd' is set to 0.85 [3]. The PageRank algorithm aims to ensure that the sum of PageRanks of all web pages equals one, transforming PageRanks into a probability distribution over all considered web pages.

Even if a page lacks in-links, it still maintains a minimum PR value of (1 - d). However, the absence of out-links, referred to as a dangling link, poses a challenge as its PR cannot be distributed to other pages. Loop structures with only in-links and no out-links require special treatment, as described in [7]. Possible solutions include excluding pages without out-links from PR calculations and later reintegrating them after other pages have obtained their PR values or distributing the PR values of such pages among all other pages as if they were connected to all.

The PageRank algorithm effectively reflects the importance of highly-referenced pages in the web community. Additionally, pages with fewer in-links but from highly-ranked sources are also assigned high scores. For instance, if a page receives a reference from a highly popular website like Yahoo!, it is considered important and is awarded a high PR.

PageRanks for all pages are pre-computed offline, making the PageRank algorithm exceptionally fast and efficient. However, it is important to note that PageRank is not query-dependent and may return results of popular pages that are not necessarily relevant to the user's query [12]. Moreover, the link structure is susceptible to manipulation, potentially leading to undesired results. For example, if a popular site excessively references other sites for commercial purposes, these out-links may receive high rankings in PageRank, even if they are not relevant to the user's query. Counteracting such spamming of search results is an ongoing area of research.

3.2 Hypertext Induced Topic Search (HITS)

The concept of topic distillation, as introduced in [5], revolves around the notion of 'authorities' and 'hubs.' This algorithm addresses the 'abundance problem,' where a broad search topic yields an overwhelming number of web pages, not all of which are relevant to the query. HITS utilizes the web's link structure to identify web pages that can be considered the most 'authoritative' on a given broad search topic. Authoritativeness, in this context, signifies how relevant and important a web page is within the WWW community for a specific topic.

Under the HITS algorithm, a page is deemed an authority on a topic if it is referenced by many other pages that are relevant to that topic. Conversely, pages that link to numerous such relevant authorities are referred to as hubs. While HITS shares similarities with PageRank in considering references, its emphasis differs significantly. Instead of counting references from all web pages across the WWW, HITS focuses on references from pages relevant to the given topic. Importantly, HITS avoids content analysis and relies solely on the web's link structure.

The HITS algorithm operates in the following steps:

1. Initially, it uses the results obtained from a text-based search engine for the query term as the root set.
2. It then expands this root set by incorporating a predefined number of pages that link to this set and those linked to by this set. This collection, termed the base set, forms a focused subgraph of the WWW, relatively small, relevant, and rich in authorities.
3. Subsequently, the algorithm analyzes this base set to compute hubs and authorities. While in the base set, authorities can be identified by ordering the pages based on their in-degree, i.e., the number of pages linking to them. However, relying solely on in-degree as a measure of authoritativeness is insufficient, as it fails to distinguish between 'popular' and 'relevant' pages. A page is considered relevant if it pertains to the search topic, while popular pages may receive numerous references even if they are unrelated to the topic. To resolve this issue, hubs come into play. Hubs help differentiate between authoritative pages that are relevant to the search query and those that are merely popular. Hubs and authorities are identified iteratively, as described below.

Each page 'p' is associated with two nonnegative weights: one for authority ('xp') and one for hub ('yp'). These weights satisfy the conditions:

∑(xp)² = 1 and ∑(yp)² = 1 for all pages 'p' in the base set.

Due to the interdependence of authorities and hubs, a good hub points to many good authorities, and a good authority is pointed to by many good hubs. Therefore, the authority weight of a page is determined by the sum of the hub weights of pages linking to it, and conversely, the hub weight of a page is determined by the sum of the authority weights of the pages it links to. These operations are applied alternately and iteratively to identify hubs and authorities within the given set of pages, and the results are ranked according to their weights.

It's important to note that HITS is executed during query time, making it relatively slow and inefficient. Additionally, any pages not included in the initial root set cannot be part of the result, even if they are relevant to the user's query. Consequently, HITS is best suited for popular queries.

3.2.1 Advantages of Hypertext Induced Topic Search (HITS) Algorithm

• HITS excels at ranking pages based on the query string, delivering relevant authority and hub pages.
• Its ranking can be combined with other information retrieval-based rankings.
• HITS is sensitive to user queries compared to PageRank.
• It identifies important pages based on calculated authority and hub values.
• HITS is a versatile algorithm for determining authority and hubs, enhancing data retrieval.
• HITS establishes a web graph through searches on specific query strings.
• Results show that HITS effectively calculates authority nodes and hubness [8].

3.2.2 Drawbacks of Hypertext Induced Topic Search (HITS) Algorithm

• Query time evaluation is costly, posing a significant drawback since HITS is query-dependent.
• Assuming that web page designers honestly link to relevant authority pages can result in irrelevant authorities.
• Pages that link to many separate topics may receive high hub ranks, even if they are not relevant to a given query.
• HITS emphasizes mutual reinforcement between authority and hub webpages.
• Topic drift can occur when irrelevant pages are included in the root set, affecting the pages in the base set and diminishing the algorithm's ability to find highly ranked authorities and hubs for a specific query.
• HITS relies on traditional search engines to obtain relevant pages, expanding the set with in-links and out-links, and then attempts to find hubs and authorities [8].

3.3 Weighted Page Rank Algorithm

In the realm of web pages, popularity often translates to the number of linkages to and from other web pages. The Weighted Page Rank Algorithm, an extension of the traditional PageRank, takes this into account by assigning larger rank values to more important (popular) pages. Instead of dividing the rank value of a page evenly among its out-link pages, each out-link page receives a value proportional to its popularity, which is determined by its number of in-links and out-links. The popularity based on in-links and out-links is recorded as Win(v,u) and Wout(v,u), respectively.

Win(v,u) represents the weight of the link(v,u) and is calculated based on the number of in-links of page 'u' and the number of in-links of all reference pages of page 'v' using the formula:

Win(v,u) = Σ(Iu / (Iu + Ip)) for all pages 'p' in R(v)

Where:
- Iu: Number of in-links of page 'u'
- Ip: Number of in-links of page 'p'
- R(v): Reference page list of page 'v'

Similarly, Wout(v,u) represents the weight of the link(v,u) and is calculated based on the number of out-links of page 'u' and the number of out-links of all reference pages of page 'v' using the formula:

Wout(v,u) = Σ(Ou / (Ou + Op)) for all pages 'p' in R(v)

Where:
- Ou: Number of out-links of page 'u'
- Op: Number of out-links of page 'p'
- R(v): Reference page list of page 'v'

Consider the following example:

In this example, Page A has two reference pages: p1 and p2. The in-links and out-links of these two pages are Ip1 = 2, Ip2 = 1, Op1 = 2, and Op2 = 3. Therefore,

Win(A,p1) = Ip1 / (Ip1 + Ip2) = 2 / 3

And

Wout(A,p1) = Op1 / (Op1 + Op2) = 2 / 5

Considering the importance of pages, the original Page Rank formula is modified as follows:

PR(u) = (1 - d) + d * Σ (PR(v) * Win(v,u) * Wout(v,u)) for all pages 'v' in B(u)

3.4 Search Engine Marketing

Search Engine Marketing (SEM) is a comprehensive digital marketing strategy that aims to enhance a website's visibility in search engine results pages (SERPs) through paid advertising and optimization techniques. SEM encompasses various strategies, including Pay-Per-Click (PPC) advertising, display ads, and search engine optimization (SEO).

One of the primary goals of SEM is to increase website traffic by improving its ranking in search engine results. PPC advertising involves bidding on specific keywords to display ads at the top of search results. Advertisers pay a fee each time a user clicks on their ad, making it a cost-effective way to attract targeted traffic. Additionally, SEM professionals use SEO techniques to optimize a website's content, structure, and meta tags, ensuring it ranks higher in organic search results. By combining paid advertising and organic optimization, SEM aims to maximize a website's visibility and drive relevant traffic, ultimately boosting its online presence and conversions.

3.5 Search Engine Optimization

Search Engine Optimization (SEO) is a fundamental component of modern web development and digital marketing. It refers to a set of techniques and best practices aimed at improving a website's visibility and ranking in organic (unpaid) search engine results. SEO focuses on optimizing various elements of a website, both on-page and off-page, to enhance its search engine friendliness and relevance to user queries.

Key aspects of SEO include:

• Keyword Research: Identifying and targeting relevant keywords and phrases that users frequently search for in search engines.
• On-Page Optimization: Enhancing website content, meta tags, headings, and images to make them more search-engine-friendly.
• Technical SEO: Optimizing website speed, mobile-friendliness, and ensuring proper indexing by search engines.
• Content Quality: Creating high-quality, informative, and engaging content that resonates with users and addresses their needs.
• Backlink Building: Acquiring quality backlinks from authoritative websites to improve a website's credibility and authority.
• Local SEO: Optimizing a website for local searches to attract nearby customers or visitors.

The ultimate goal of SEO is to increase a website's organic traffic by ranking higher in search engine results, thus driving more relevant visitors. This not only improves a website's visibility but also enhances its credibility and trustworthiness among users. SEO is an ongoing process, as search engine algorithms continually evolve, and staying up-to-date with the latest practices is essential to maintaining and improving a website's ranking in SERPs.

Both SEM and SEO are crucial strategies for improving a website's online presence, attracting targeted traffic, and achieving marketing goals. The choice between them depends on the specific objectives, budget, and timeline of a digital marketing campaign.

4. Comparison of HITS and PageRank

Criteria	HITS	Page Rank
Basic Criteria	Link analysis algorithm based on random surfer model.	Link analysis algorithm based on web structure mining.
Main Technique followed	Web Structure Mining, Web Content Mining	Web Structure Mining
Efficiency	Computation at query time, not feasible for handling large numbers of daily queries.	Computation done at crawl time, resulting in greater efficiency for handling query requests.
Mutual Reinforcement	Emphasizes mutual reinforcement between authority and hub webpages.	Does not explicitly attempt to capture the distinction between hubs and authorities.

5. Ranking Ontologies

Ranking ontologies are essential in the field of information retrieval and web mining. They provide a structured framework for organizing and prioritizing information based on specific criteria, facilitating the efficient retrieval of relevant data. Ontologies, in this context, represent a formal representation of knowledge or concepts within a domain, complete with relationships and properties.

When it comes to ranking ontologies, their primary role is to define how information should be ranked or ordered to meet the needs of users or applications. These ontologies encompass various elements, including:

• Concepts: The fundamental entities or terms within a domain that need to be ranked or categorized.
• Relationships: The connections or associations between concepts, which help determine the structure of the ranking ontology.
• Properties: Attributes or characteristics associated with concepts or relationships, providing additional context for ranking.
• Ranking Criteria: The specific rules or algorithms used to assess and assign ranks to concepts or information based on user preferences or relevance.

Ranking ontologies find applications in various domains, including web search engines, e-commerce platforms, recommendation systems, and information retrieval systems. They play a critical role in enhancing the user experience by ensuring that the most relevant information is presented at the top of search results or recommendations.

For instance, in a web search engine, a ranking ontology can define how web pages are ranked based on factors such as keyword relevance, user engagement metrics, and authoritative sources. In an e-commerce platform, it can determine the order in which products are displayed in search results, considering factors like price, customer reviews, and availability.

The design and implementation of ranking ontologies require careful consideration of the specific domain and user requirements. They must adapt to changing user preferences and evolving content, which necessitates continuous refinement and updates. Furthermore, the incorporation of machine learning techniques can enhance the accuracy and adaptability of ranking ontologies, allowing them to learn from user behavior and feedback.

In conclusion, ranking ontologies are a vital component of modern information retrieval systems. They provide a structured framework for organizing and prioritizing information, ensuring that users receive the most relevant and valuable content. As technology continues to advance, the development and optimization of ranking ontologies will remain a crucial area of research and application in the field of web mining and information retrieval.

6. Conclusion

Web mining has become an integral part of user experience, as users invest a significant amount of time in search queries to extract relevant information from the web. In this study, we compared two prominent link analysis algorithms: HITS and PageRank, which employ different models to calculate web page ranks.

The PageRank algorithm plays a crucial role in facilitating easier navigation for users. It considers factors such as the number of users visiting web pages and analyzes the page rank of web pages for search engine purposes. On the other hand, HITS is a link analysis algorithm based on the random surfer model, emphasizing mutual reinforcement between authority and hub webpages.

In conclusion, both algorithms serve distinct purposes in web mining and ranking. While PageRank is known for its efficiency, especially for handling a large volume of daily queries, HITS has found applications in various web sites through its extensions. The choice between these algorithms depends on the specific requirements and objectives of a given web mining task.