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

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.KStepMarkov

public class KStepMarkov
extends RelativeAuthorityRanker

Algorithm variant of PageRankWithPriors that computes the importance of a node based upon taking fixed-length random walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes the relative probability that the markov chain will spend at any particular node, given that it start in the root set and ends after k steps.

A simple example of usage is:

 KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
 ranker.evaluate();
 ranker.printRankings();
 

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

Field Summary
static String RANK_SCORE
           
 
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
KStepMarkov(DirectedGraph graph, Set priors, int k, String edgeWeightKeyName)
          Construct the algorihm instance and initializes the algorithm.
 
Method Summary
protected  double evaluateIteration()
          Evaluate the result of the current interation.
protected  double getCurrentRankScore(Element v)
           
 String getRankScoreKey()
          The user datum key used to store the rank scores.
protected  void incrementRankScore(Element v, double rankValue)
           
protected  void initializeRankings()
           
protected  void onFinalize(Element udc)
           
protected  void setCurrentRankScore(Element v, double rankValue)
           
protected  void updateRankings()
           
 
Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
finalizeIterations, getPriorRankScore, getPriorRankScoreKey, getPriors, setPriorRankScore, setPriors
 
Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
assignDefaultEdgeTransitionWeights, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScore, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, printRankings, reinitialize, setEdgeWeight, setNormalizeRankings, setRankScore, 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

RANK_SCORE

public static final String RANK_SCORE
See Also:
Constant Field Values
Constructor Detail

KStepMarkov

public KStepMarkov(DirectedGraph graph,
                   Set priors,
                   int k,
                   String edgeWeightKeyName)
Construct the algorihm instance and initializes the algorithm.

Parameters:
graph - the graph to be analyzed
priors - the set of root nodes
k - positive integer parameter which controls the relative tradeoff between a distribution "biased" towards R and the steady-state distribution which is independent of where the Markov-process started. Generally values between 4-8 are reasonable
edgeWeightKeyName -
Method Detail

getRankScoreKey

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

Specified by:
getRankScoreKey in class AbstractRanker
Returns:
the key

incrementRankScore

protected void incrementRankScore(Element v,
                                  double rankValue)

getCurrentRankScore

protected double getCurrentRankScore(Element v)

setCurrentRankScore

protected void setCurrentRankScore(Element v,
                                   double rankValue)

initializeRankings

protected void initializeRankings()

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.

onFinalize

protected void onFinalize(Element udc)
Overrides:
onFinalize in class AbstractRanker

updateRankings

protected void updateRankings()