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

java.lang.Object
  edu.uci.ics.jung.algorithms.IterativeProcess
      edu.uci.ics.jung.algorithms.importance.AbstractRanker
          edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
              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 java.lang.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, java.util.Set priors, int k, java.lang.String edgeWeightKeyName)
Construct the algorihm instance and initializes the algorithm.

Method Summary

java.lang.String

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

Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker

setPriorRankScore

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker

getEdgeWeightKeyName, getRankings, getRankScore, getRankScores, isRankingNodes, printRankings, setNormalizeRankings, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess

evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, setDesiredPrecision, setMaximumIterations

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

RANK_SCORE

public static final java.lang.String RANK_SCORE

See Also:

Constant Field Values

Constructor Detail

KStepMarkov

public KStepMarkov(DirectedGraph graph,
                   java.util.Set priors,
                   int k,
                   java.lang.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 java.lang.String getRankScoreKey()

The user datum key used to store the rank scores.

Specified by:

getRankScoreKey in class AbstractRanker

Returns:

the key