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

GQL
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)

Parameters

Run Mode

Returns:

HITS for all nodes:

GQL
CALL algo.hits({
  maxIterations: 50,
  tolerance: 0.001,
  order: "desc"
}) YIELD nodeId, hubScore, authScore

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.hits.stream({
  order: "desc"
}) YIELD nodeId, hubScore
RETURN nodeId, hubScore
ORDER BY hubScore DESC

Result:

Stats Mode

Returns:

GQL
CALL algo.hits.stats() YIELD nodeCount, minHubScore, maxHubScore, minAuthScore, maxAuthScore

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.hits.write({}, {
  db: {
    property: {hubScore: "hub", authScore: "auth"}
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs