HITS Algorithm

This algorithm was first described by Jon Kleinberg in his work “Authoritative Sources in a Hyperlinked Environment” (1998). The idea behind the HITS (Hyperlink Induced Topic Distillation) algorithm is that the authorities and hubs mutually reinforce each other. Authority weight of a page is calculated as a sum of hub weights pointing to it, and weight of a hub – as a sum of weights of authorities pointed to by it. In other words a hub is as good as the authorities linked by it, and vice versa.

The notation of the algorithm is as follows. Let S be a set of pages for which hub and authority weights are being calculated, n – the number of pages in the set. Then H is a subset of S containing pages acting as hubs, and A is a subset of S containing authorities. Since each page can be an authority and a hub, A and H overlap. For every page i in its hub role F(i) is the number of outgoing links. For every page i in its authority role B(i) is the number of incoming links. The n-dimensional vector of authority weights is denoted as a, and vector of hub weight – as h. Then hub and authority weights are calculated by the following formula:

The process is iterative. First all the weights receive value of 1. Then hubs and authority weights are calculated and the vectors are normalized. This stage is repeated until vectors a and h converge.

The algorithm however has a number of flaws. For example the nature of mutual reinforcement creates the following situation. Consider a hub that points to many authorities (hub B on the picture below), and a number of hubs pointing to a single authority (authority A on the picture). If the number of authorities pointed to by B is larger then the number of hubs pointing to A, then the HITS algorithm will allocate all the weight to the authorities in the right part of the picture and the authority A will get a weight near zero.

The reason is that hub B will initially get a very high score and propagate it to the authorities it links to. In the same time hubs on the left side will get very low score, and consequently A will get low weight too, although obviously it deserves more.

Cited Resources

• Kleinberg, J. May 1997, ‘Authoritative sources in a hyperlinked environment’. Technical Report RJ 10076, IBM,. Available at http://citeseer.ist.psu.edu/article/kleinberg98authoritative.html