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"
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 java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
RANK_SCORE
public static final String RANK_SCORE
- See Also:
- Constant Field Values
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 analyzedpriors
- the set of root nodesk
- 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 reasonableedgeWeightKeyName
-
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()