edu.uci.ics.jung.algorithms.scoring
Class HITS<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,S>
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,HITS.Scores>
edu.uci.ics.jung.algorithms.scoring.HITSWithPriors<V,E>
edu.uci.ics.jung.algorithms.scoring.HITS<V,E>
- Type Parameters:
V
- the vertex typeE
- the edge type
- All Implemented Interfaces:
- VertexScorer<V,HITS.Scores>, IterativeContext
public class HITS<V,E>
- extends HITSWithPriors<V,E>
Assigns hub and authority scores to each vertex depending on the topology of
the network. The essential idea is that a vertex is a hub to the extent
that it links to authoritative vertices, and is an authority to the extent
that it links to 'hub' vertices.
The classic HITS algorithm essentially proceeds as follows:
assign equal initial hub and authority values to each vertex
repeat
for each vertex w:
w.hub = sum over successors x of x.authority
w.authority = sum over predecessors v of v.hub
normalize hub and authority scores so that the sum of the squares of each = 1
until scores converge
HITS is somewhat different from random walk/eigenvector-based algorithms
such as PageRank in that:
- there are two mutually recursive scores being calculated, rather than
a single value
- the edge weights are effectively all 1, i.e., they can't be interpreted
as transition probabilities. This means that the more inlinks and outlinks
that a vertex has, the better, since adding an inlink (or outlink) does
not dilute the influence of the other inlinks (or outlinks) as in
random walk-based algorithms.
- the scores cannot be interpreted as posterior probabilities (due to the different
normalization)
This implementation has the classic behavior by default. However, it has
been generalized somewhat so that it can act in a more "PageRank-like" fashion:
- this implementation has an optional 'random jump probability' parameter analogous
to the 'alpha' parameter used by PageRank. Varying this value between 0 and 1
allows the user to vary between the classic HITS behavior and one in which the
scores are smoothed to a uniform distribution.
The default value for this parameter is 0 (no random jumps possible).
- the edge weights can be set to anything the user likes, and in
particular they can be set up (e.g. using
UniformDegreeWeight
)
so that the weights of the relevant edges incident to a vertex sum to 1.
- The vertex score normalization has been factored into its own method
so that it can be overridden by a subclass. Thus, for example,
since the vertices' values are set to sum to 1 initially, if the weights of the
relevant edges incident to a vertex sum to 1, then the vertices' values
will continue to sum to 1 if the "sum-of-squares" normalization code
is overridden to a no-op. (Other normalization methods may also be employed.)
- See Also:
- "'Authoritative sources in a hyperlinked environment' by Jon Kleinberg, 1997"
Nested Class Summary |
static class |
HITS.Scores
Maintains hub and authority score information for a vertex. |
Constructor Summary |
HITS(Graph<V,E> g)
Creates an instance for the specified graph. |
HITS(Graph<V,E> g,
double alpha)
Creates an instance for the specified graph and alpha (random jump probability)
parameter. |
HITS(Graph<V,E> g,
org.apache.commons.collections15.Transformer<E,Double> edge_weights,
double alpha)
Creates an instance for the specified graph, edge weights, and alpha
(random jump probability) parameter. |
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer |
acceptDisconnectedGraph, done, evaluate, getAdjustedIncidentCount, getCurrentValue, getEdgeWeight, getEdgeWeights, getIterations, getMaxIterations, getOutputValue, getTolerance, getVertexScore, isDisconnectedGraphOK, setCurrentValue, setEdgeWeights, setHyperedgesAreSelfLoops, setMaxIterations, setOutputValue, setTolerance, step, swapOutputForCurrent, updateMaxDelta |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
HITS
public HITS(Graph<V,E> g,
org.apache.commons.collections15.Transformer<E,Double> edge_weights,
double alpha)
- Creates an instance for the specified graph, edge weights, and alpha
(random jump probability) parameter.
- Parameters:
g
- the input graphedge_weights
- the weights to use for each edgealpha
- the probability of a hub giving some authority to all vertices,
and of an authority increasing the score of all hubs (not just those connected
via links)
HITS
public HITS(Graph<V,E> g,
double alpha)
- Creates an instance for the specified graph and alpha (random jump probability)
parameter. The edge weights are all set to 1.
- Parameters:
g
- the input graphalpha
- the probability of a hub giving some authority to all vertices,
and of an authority increasing the score of all hubs (not just those connected
via links)
HITS
public HITS(Graph<V,E> g)
- Creates an instance for the specified graph. The edge weights are all set to 1
and alpha is set to 0.
- Parameters:
g
- the input graph
Copyright © 2009. All Rights Reserved.