Lecture
The HITS algorithm (Hyperlink Induced Topic Search), proposed in 1999 by Jon Kleinberg, makes it possible to find web pages matching a user's query based on the information encoded in hyperlinks
.
The HITS metric is often used to answer broad-topic queries and to find communities of documents (Tightly-Knit Community) on the web. The idea behind the algorithm is based on the assumption that hyperlinks encode a significant amount of latent authority pages .
Authority document (authority page, authority) — a document matching the user's query that carries greater weight among documents on the given topic, that is, a larger number of documents link to this document .
Hub document (hub page, hub) — a document that contains many links to authority documents.
A page that many other pages link to should be a good «authority». In turn, a page that points to many others should be a good «hub». Based on this, the HITS algorithm computes two scores for each web page: an authority score and a hub score. That is, for each page, its significance as an «authority» and as a «hub» is computed recursively .
Expanding the root set of relevant pages into the base set
The first step in the HITS algorithm is obtaining the most relevant pages for the search query. This set is called the root set and can be obtained by taking the n most popular pages returned by a text search algorithm. The base set is formed by expanding the root set with all the web pages that are linked to it and with some of the pages that link to it. The web pages in the base set, and all the hyperlinks between these pages, form a focused subgraph. HITS computations are performed only on this subgraph.
The authority and hub scores are defined in terms of each other through mutual recursion. A page's authority score is computed as the sum of the hub scores of the pages that point to it. A page's hub score is computed as the sum of the authority scores of the pages it points to.
The algorithm performs a series of iterations, each consisting of two main steps:
The authority score and hub score for a vertex are calculated using the following algorithm:
To begin ranking, 
, 
and 
. Let us consider two types of updates: the authority update rule and the hub update rule. To compute the authority/hub scores, repeated iterations of the authority update and hub update rules are applied. A k-step application of the algorithm means applying the authority update rule k times, followed by the hub update rule.
The main operations of the HITS algorithm: the authority update rule and the hub update rule
, we obtain 
= 
where n — is the total number of pages linked to p, and i — is a page linked to p. Thus, the authority score of a page is computed as the sum of the hub scores of the pages that point to it.
, we obtain 
= 
where n — is the total number of pages that p points to, and i — is a page that p points to. Thus, the hub score of a page is computed as the sum of the authority scores of the pages it links to.
Based on these values, the importance of web pages is calculated for a specific query and then shown to the user. The HITS ranking module computes the rank of a web page offline, after the pages have been crawled and stored in a local database.
The final scores of the vertices are determined after an infinite repetition of the algorithm. Direct, sequential application of the hub update and authority update rules leads to diverging values, which need to be normalized by a matrix after each iteration. In this way, the values obtained through this process eventually converge.
The HITS algorithm has several important differences from the PageRank algorithm.
Despite the differences between HITS and PageRank, what these algorithms have in common is that the authority (weight) of a node depends on the weight of other nodes, and the level of a «hub» depends on how authoritative the nodes it links to are.
The computation of the authority of individual documents is now widely used in applications such as determining the crawl order of documents on the web by a search engine robot, ranking search results, building topical overviews, and so on.
Nowadays, techniques for artificially boosting the ranks of individual web documents or groups of websites by establishing hyperlinks unrelated to their content have become widespread. These techniques, an untrustworthy variety of search engine optimization (SEO) methods known as «black hat» SEO, rely on adapting to the existing web document ranking algorithms used by the most popular search engines.
These technologies, in turn, create the need for constantly improving search engine ranking algorithms, and for focusing on the substantive content of web documents when determining their ranks.
Extensive research has evaluated the HITS algorithm and shown that, while the algorithm works well for most queries, it fails for some others. There are several reasons :
It is impractical to draw a clear distinction between «hubs» and «authorities», since many hub pages are also authority pages.
The dominant placement of certain thematically closely related documents as a result of the HITS algorithm's work. In some cases, these documents may be irrelevant to the given query. It has been documented that in one case, when the search term was «Jaguar», the HITS algorithm converged on a football team called the Jaguars.
To address this problem, the PHITS algorithm was proposed as an extension of the standard HITS algorithm. Within this algorithm, it is assumed that: 
— is the set of citing documents, 
— is the set of links, 
— is the set of classes (factors). It is also assumed that the event 
occurs with probability 
. The conditional probabilities 
and 
are used to describe the dependencies between the presence of a link 
, a latent factor 
and a document .
The likelihood function being evaluated is:
,
The goal of the PHITS algorithm is to choose 
, , so as to maximize 
.
After that:
– ranks of "authorities";
– ranks of "hubs".
To compute the ranks, one must specify the number of factors in the set , and then will characterize the quality of a page as an «authority» in the context of the topic. A drawback of the method is that the iterative process most often stops not at the absolute, but at a local maximum of the likelihood function 
. At the same time, in situations where the set of found web pages has no clear topical dominance for the query, PHITS outperforms the HITS algorithm.
Some of the links are generated by a computer, but the HITS algorithm still gives them equal weight.
Some queries may return irrelevant documents in a high position in the ranking, which leads to erroneous results from the HITS algorithm.
Comments