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 a considerable number of authoritative nodes, it is referred to as a hub.

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

Hubs and authorities exhibit 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 iterates until the changes in all x and y values converge within a specific tolerance, or until the maximum number of iterations is reached. 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.
• Nodes with no in-links are assigned an authority weight of 0, while nodes with no out-links are assigned a hub weight of 0.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (H:default {_id: "H"}),
       (A)-[:default]->(F),
       (B)-[:default]->(A),
       (C)-[:default]->(A),
       (C)-[:default]->(B),
       (D)-[:default]->(A),
       (D)-[:default]->(F),
       (E)-[:default]->(A),
       (E)-[:default]->(G),
       (F)-[:default]->(H),
       (G)-[:default]->(F);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: hits_centrality

File Writeback

UQL
algo(hits_centrality).params({
  return_id_uuid: "id",
  projection: "my_hdc_graph"
}).write({
  file: {
    filename: "ranks"
  }
})

Result:

File: ranks
_id,authority,hub
D,0,0.572083
F,0.42642,1.43197e-11
H,3.20199e-11,0
B,0.213196,0.381382
A,0.852796,0.190701
E,0,0.476726
C,0,0.476726
G,0.213196,0.190701

DB Writeback

Writes the authority and hub values from the results to the specified node property. The property types are both double.

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

Full Return

UQL
exec{
  algo(hits_centrality).params({
    return_id_uuid: "id"
  }) as r
  return r
} on my_hdc_graph

Result:

Stream Return

UQL
exec{
  algo(hits_centrality).params({
    return_id_uuid: "id",
    max_loop_num: 20,
    tolerance: 0.0001
  }).stream() as r
  return r._id, r.hub order by r.hub
} on my_hdc_graph

Result: