HITS algorithm

When Hubs and Authorities can be divided into network theory node outstanding divided by their linking. Put simply Hubs and Authorities are nodes that are connected to many other nodes - for example, well-known personalities in social networks and link directories on the World Wide Web.

Calculation

The concept of hubs and Authorities supplies similar to the PageRank algorithm, a concept for automatic evaluation of web pages based on their link with which a ranking method can be entered. It was proposed in 1999 by Jon Kleinberg and is under the name of hypertext -induced topic selection ( HITS ) is known.

Each side two categories is rated:

Hubs are pages that point to many valuable content documents.
Authorities are pages whose content is considered particularly good.

The algorithm assumes that good Hubs have hyperlinks to many Authorities and Authorities are accessible from many of the stroke.

To evaluate each side is composed of a base set of pages associated with a stroke weight and a weight Authority. The basic amount is generated from the search query. These are pages that are relevant to the keywords to a certain number of pages that are linked from the basic set or pointing to the basic amount extended. After that, the weights are updated until convergence is determine as follows:

Here, the link matrix in which, if the page has a link to the page, and if this is not the case. is the transposed matrix of, ie. Thus:

The Hub value of a page is derived from the sum of all values Authority of pages that are linked from.
The Authority value of a page is derived from the sum of all hub values of pages. Upon link

By mutual insertion of the definitions we obtain the dependencies:

Here converge and against one of the eigenvectors of the largest eigenvalue of respectively.

And are usually normalizations on the unit circle. In addition, each symmetric and positive semi-definite or. It follows that both matrices are diagonalizable and thus have an orthonormal basis. The repeated multiplication converges thus to the largest eigenvector.