edu.uci.ics.jung.algorithms.scoring
Class HITSWithPriors<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>

All Implemented Interfaces:

VertexScorer<V,HITS.Scores>, IterativeContext

Direct Known Subclasses:

HITS

public class HITSWithPriors<V,E>
extends AbstractIterativeScorerWithPriors<V,E,HITS.Scores>

A generalization of HITS that permits non-uniformly-distributed random jumps. The 'vertex_priors' (that is, prior probabilities for each vertex) may be thought of as the fraction of the total 'potential' (hub or authority score) that is assigned to that vertex out of the portion that is assigned according to random jumps.

See Also:

"Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"

Field Summary

protected HITS.Scores

disappearing_potential The sum of the potential, at each step, associated with vertices with no outedges (authority) or no inedges (hub).

Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors

alpha, vertex_priors

Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer

edge_weights, graph, hyperedges_are_self_loops, max_delta, max_iterations, output_reversed, tolerance, total_iterations

Constructor Summary

HITSWithPriors(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights, org.apache.commons.collections15.Transformer<V,HITS.Scores> vertex_priors, double alpha)
Creates an instance for the specified graph, edge weights, vertex prior probabilities, and random jump probability (alpha).

HITSWithPriors(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<V,HITS.Scores> vertex_priors, double alpha)
Creates an instance for the specified graph, vertex priors, and random jump probability (alpha).

Method Summary

protected void	afterStep() Code which is executed after each step.
protected void	collectDisappearingPotential(V v) Collects the "disappearing potential" associated with vertices that have either no incoming edges, no outgoing edges, or both.
protected void	normalizeScores() Normalizes scores so that sum of their squares = 1.
protected double	update(V v) Updates the value for this vertex.

Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors

getAlpha, getVertexPrior, getVertexPriors, initialize

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

Methods inherited from interface edu.uci.ics.jung.algorithms.scoring.VertexScorer

getVertexScore

Field Detail

disappearing_potential

protected HITS.Scores disappearing_potential

The sum of the potential, at each step, associated with vertices with no outedges (authority) or no inedges (hub).

Constructor Detail

HITSWithPriors

public HITSWithPriors(Hypergraph<V,E> g,
                      org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
                      org.apache.commons.collections15.Transformer<V,HITS.Scores> vertex_priors,
                      double alpha)

Creates an instance for the specified graph, edge weights, vertex prior probabilities, and random jump probability (alpha).

Parameters:

g - the input graph

edge_weights - the edge weights

vertex_priors - the prior probability for each vertex

alpha - the probability of a random jump at each step

HITSWithPriors

public HITSWithPriors(Hypergraph<V,E> g,
                      org.apache.commons.collections15.Transformer<V,HITS.Scores> vertex_priors,
                      double alpha)

Creates an instance for the specified graph, vertex priors, and random jump probability (alpha). The edge weights default to 1.0.

Parameters:

g - the input graph

vertex_priors - the prior probability for each vertex

alpha - the probability of a random jump at each step

Method Detail

update

protected double update(V v)

Updates the value for this vertex.

Specified by:

update in class AbstractIterativeScorer<V,E,HITS.Scores>

Parameters:

v - the vertex whose value is to be updated

Returns:

afterStep

protected void afterStep()

Code which is executed after each step. In this case, deals with the 'disappearing potential', normalizes the scores, and then calls super.afterStep().

Overrides:

afterStep in class AbstractIterativeScorer<V,E,HITS.Scores>

See Also:

collectDisappearingPotential(Object)

normalizeScores

protected void normalizeScores()

Normalizes scores so that sum of their squares = 1. This method may be overridden so as to yield different normalizations.

collectDisappearingPotential

protected void collectDisappearingPotential(V v)

Collects the "disappearing potential" associated with vertices that have either no incoming edges, no outgoing edges, or both. Vertices that have no incoming edges do not directly contribute to the hub scores of other vertices; similarly, vertices that have no outgoing edges do not directly contribute to the authority scores of other vertices. These values are collected at each step and then distributed across all vertices as a part of the normalization process. (This process is not required for, and does not affect, the 'sum-of-squares'-style normalization.)

Overrides:

collectDisappearingPotential in class AbstractIterativeScorer<V,E,HITS.Scores>