public class KStepMarkov extends RelativeAuthorityRanker
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();
Modifier and Type | Field and Description |
---|---|
static java.lang.String |
RANK_SCORE |
PRIOR_KEY
DEFAULT_EDGE_WEIGHT_KEY
Constructor and Description |
---|
KStepMarkov(DirectedGraph graph,
java.util.Set priors,
int k,
java.lang.String edgeWeightKeyName)
Construct the algorihm instance and initializes the algorithm.
|
Modifier and Type | Method and Description |
---|---|
protected double |
evaluateIteration()
Evaluate the result of the current interation.
|
protected double |
getCurrentRankScore(Element v) |
java.lang.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() |
finalizeIterations, getPriorRankScore, getPriorRankScoreKey, getPriors, setPriorRankScore, setPriors
assignDefaultEdgeTransitionWeights, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScore, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, printRankings, reinitialize, setEdgeWeight, setNormalizeRankings, setRankScore, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey
evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations
public static final java.lang.String RANK_SCORE
public KStepMarkov(DirectedGraph graph, java.util.Set priors, int k, java.lang.String edgeWeightKeyName)
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
- public java.lang.String getRankScoreKey()
getRankScoreKey
in class AbstractRanker
protected void incrementRankScore(Element v, double rankValue)
protected double getCurrentRankScore(Element v)
protected void setCurrentRankScore(Element v, double rankValue)
protected void initializeRankings()
protected double evaluateIteration()
IterativeProcess
evaluateIteration
in class IterativeProcess
protected void onFinalize(Element udc)
onFinalize
in class AbstractRanker
protected void updateRankings()