HITS

Overview

The HITS (Hyperlink-Induced Topic Search) algorithm was developed by L.M. Kleinberg in 1999 with the purpose of improving the quality of search methods on the World Wide Web (WWW). HITS makes use of the mutual reinforcing relationship between authorities and hubs to evaluate and rank a set of linked entities.

• L.M. Kleinberg, Authoritative Sources in a Hyperlinked Environment (1999)

Concepts

Authority and Hub

In WWW, hyperlinks represent some latent human judgment: the creator of page p, by including a link to page q, has in some measure conferred authority on q. Instructively, a node with large in-degree is viewed as an authority.

If a node points to considerable number of authoritative nodes, it is referred to as a hub.

As illustrated in the graph below, red nodes are good authorities, green nodes are good hubs.

Hubs and authorities exhibit what could be called a mutually reinforcing relationship: a good hub points to many good authorities; a good authority is pointed to by many good hubs.

Compute Authorities and Hubs

HITS algorithm operates on the whole graph iteratively to compute the authority weight (denoted as x) and hub weight (denoted as y) for each node through the link structure. Nodes with larger x-values and y-values are viewed as better authorities and hubs respectively.

In a directed graph G = (V, E), all nodes are initialized with x = 1 and y = 1. In each iteration, for each node p ∈ V, update its x and y values as follows:

Here is an example:

At the end of one iteration, normalize all x values and all y values to meet the invariant below:

The algorithm continues until the change of all x values and y values converges to within some tolerance, or the maximum iteration rounds is met. In the experiments of the original author, the convergence is quite rapid, 20 iterations are normally sufficient.

Considerations

• In HITS algorithm, self-loops are ignored.
• Authority weight of nodes with no in-links is 0, hub weight of nodes with out-links is 0.

Syntax

• Command: algo(hits_centrality)
• Parameters:

Examples

The example graph is as follows:

File Writeback

UQL
algo(hits_centrality).params({}).write({
  file: {
    filename: 'rank'
  }
})

Results: File rank

File
H,0.000000,0.000000
G,0.213196,0.190701
F,0.426420,0.000000
E,0.000000,0.476726
D,0.000000,0.572083
C,0.000000,0.476726
B,0.213196,0.381382
A,0.852796,0.190701

Property Writeback

UQL
algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).write({
  db: {
    authority: 'auth',
    hub: 'hub'
  }
})

Results: Authority weight for each node is written to a new property named auth, hub weight for each node is written to a new property named hub

Direct Return

UQL
algo(hits_centrality).params() as rank
return rank

Results: rank

Stream Return

UQL
algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).stream() as rank
find().nodes({_uuid == rank._uuid}) as nodes
order by rank.hub desc
return table(nodes._id, rank.hub)

Results: table(nodes._id, rank.hub)