com.raphtory.algorithms.generic.HITS

HITS

HITS(iterateSteps: Int = 100, truncate: Boolean = false, tol: Double = 0.00001)

Calculate the hub and authority scores of each vertex in the graph.

The HITS algorithm is similar to pagerank but imagines 2 types of nodes: good hubs which have outgoing edges linking to lots of good authorities, and good authorities which have incoming edges from lots of good hubs. https://en.wikipedia.org/wiki/HITS_algorithm

Parameters

iterateSteps: Int = 100

Maximum number of iterations for the algorithm to run. truncate: Boolean = false

If set to true, the scores at the end are truncated to 8 dp. s tol: Double = 0.00001

Each vertex will vote to halt when it changes by less than tol in that iteration.

States

hitshub: Long

The current hub score of a vertex. hitsauth: Long

The current authority score of a vertex

Returns

vertex name

hubs score

authorities score

name: String

husbauth: Long

hitsauth: Long

Implementation

The algorithm works by each vertex calculating its hub score by the sum of the authorities scores from its out neighbours, and its authorities score by the sum of the hubs score from its in neighbours, sending out its new scores, and iterating.

  1. Initially we create accumulators, set the hub scores to an initial value (1.0), and message each vertex’s hub score to its out neighbours.

  2. Each vertex calculates it’s initial authorities score from the sum of the hub scores it receives, and messages its hub score to its out neighbours, and its authorities score to its in neighbours.

  3. On each iteration each vertex calculates its hub score from the sum of the authorities scores it receives, its authorities score from the sum of the hub values it receives, and normalises these values: dividing by the maximum of all the hubs and authorities scores from the last iteration.

  4. It then messages its new hub score to its out neighbours, and its authorities score to its neighbours.

  5. This repeats until the scores stay approximately constant, in which case the scores are normalised one more time.