edu.uci.ics.jung.algorithms.importance
Class HITSWithPriors

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker
          extended by edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
              extended by edu.uci.ics.jung.algorithms.importance.HITSWithPriors

public class HITSWithPriors
extends RelativeAuthorityRanker

Algorithm that extends the HITS algorithm by incorporating root nodes (priors). Whereas in HITS the importance of a node is implicitly computed relative to all nodes in the graph, now importance is computed relative to the specified root nodes.

A simple example of usage is:

 HITSWithPriors ranker = new HITSWithPriors(someGraph,0.3,rootSet);
 ranker.evaluate();
 ranker.printRankings();
 

Running time: O(|V|*I) where |V| is the number of vertices and I is the number of iterations until convergence

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

Field Summary
protected static String AUTHORITY_KEY
           
protected static String HUB_KEY
           
 
Fields inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
PRIOR_KEY
 
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
DEFAULT_EDGE_WEIGHT_KEY
 
Constructor Summary
HITSWithPriors(Graph graph, boolean useAuthorityForRanking, double bias, Set priors, String edgeWeightKey)
          More specialized constructor where the type of importance can be specified.
HITSWithPriors(Graph graph, double bias, Set priors)
          Constructs an instance of the ranker where the type of importance that is associated with the rank score is the node's importance as an authority.
 
Method Summary
protected  double evaluateIteration()
          Evaluate the result of the current interation.
protected  void finalizeIterations()
          Cleans up all of the prior rank scores on finalize.
protected  double getInEdgeWeight(Edge e)
           
protected  double getPreviousAuthorityScore(Element v)
           
protected  double getPreviousHubScore(Element v)
           
 double getRankScore(Element v)
          Given a node, returns the corresponding rank score.
protected  double getRankScore(Element v, String key)
          Given a node and a key, returns the corresponding rank score.
 String getRankScoreKey()
          the user datum key used to store the rank scores
protected  void initialize(Graph g, String edgeWeightKeyName)
           
protected  void setInEdgeWeight(Edge e, double weight)
           
protected  void setRankScore(Element v, double rankValue)
           
protected  void setRankScore(Element v, double rankValue, String key)
           
 void setUseAuthorityForRanking(boolean useAuthorityForRanking)
          If evaluate() has not already been called, the user can override the type of importance.
protected  void updateAuthorityRankings()
           
protected  void updateHubRankings()
           
protected  void updatePreviousScores()
           
 
Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
getPriorRankScore, getPriorRankScoreKey, getPriors, setPriorRankScore, setPriors
 
Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
assignDefaultEdgeTransitionWeights, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, onFinalize, printRankings, reinitialize, setEdgeWeight, setNormalizeRankings, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey
 
Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess
evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

AUTHORITY_KEY

protected static final String AUTHORITY_KEY
See Also:
Constant Field Values

HUB_KEY

protected static final String HUB_KEY
See Also:
Constant Field Values
Constructor Detail

HITSWithPriors

public HITSWithPriors(Graph graph,
                      double bias,
                      Set priors)
Constructs an instance of the ranker where the type of importance that is associated with the rank score is the node's importance as an authority.

Parameters:
graph - the graph whose nodes are to be ranked
bias - the weight that should be placed on the root nodes (between 0 and 1)
priors - the set of root nodes

HITSWithPriors

public HITSWithPriors(Graph graph,
                      boolean useAuthorityForRanking,
                      double bias,
                      Set priors,
                      String edgeWeightKey)
More specialized constructor where the type of importance can be specified.

Parameters:
graph - the graph whose nodes are to be ranked
useAuthorityForRanking -
bias - the weight that should be placed on the root nodes (between 0 and 1)
priors - the set of root nodes
Method Detail

initialize

protected void initialize(Graph g,
                          String edgeWeightKeyName)

finalizeIterations

protected void finalizeIterations()
Description copied from class: RelativeAuthorityRanker
Cleans up all of the prior rank scores on finalize.

Overrides:
finalizeIterations in class RelativeAuthorityRanker

getInEdgeWeight

protected double getInEdgeWeight(Edge e)

setInEdgeWeight

protected void setInEdgeWeight(Edge e,
                               double weight)

getRankScoreKey

public String getRankScoreKey()
the user datum key used to store the rank scores

Specified by:
getRankScoreKey in class AbstractRanker
Returns:
the key

getRankScore

public double getRankScore(Element v)
Given a node, returns the corresponding rank score. This implementation of getRankScore assumes the decoration representing the rank score is of type MutableDouble.

Overrides:
getRankScore in class AbstractRanker
Returns:
the rank score for this node

getRankScore

protected double getRankScore(Element v,
                              String key)
Given a node and a key, returns the corresponding rank score. Assumes the decoration representing the rank score is of type MutableDouble.

Parameters:
v - the node in question
key - the user datum key that indexes the rank score value
Returns:
the rank score for this node

getPreviousAuthorityScore

protected double getPreviousAuthorityScore(Element v)

getPreviousHubScore

protected double getPreviousHubScore(Element v)

setRankScore

protected void setRankScore(Element v,
                            double rankValue,
                            String key)

setRankScore

protected void setRankScore(Element v,
                            double rankValue)
Overrides:
setRankScore in class AbstractRanker

evaluateIteration

protected double evaluateIteration()
Description copied from class: IterativeProcess
Evaluate the result of the current interation.

Specified by:
evaluateIteration in class IterativeProcess
Returns:
the estimated precision of the result.

setUseAuthorityForRanking

public void setUseAuthorityForRanking(boolean useAuthorityForRanking)
If evaluate() has not already been called, the user can override the type of importance. (hub or authority) that should be associated with the rank score.

Parameters:
useAuthorityForRanking - if true, authority is used; if false, hub is used

updateAuthorityRankings

protected void updateAuthorityRankings()

updateHubRankings

protected void updateHubRankings()

updatePreviousScores

protected void updatePreviousScores()