Class KStepMarkov<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.util.IterativeProcess
-
- edu.uci.ics.jung.algorithms.importance.AbstractRanker<V,E>
-
- edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker<V,E>
-
- edu.uci.ics.jung.algorithms.importance.KStepMarkov<V,E>
-
- All Implemented Interfaces:
IterativeContext
public class KStepMarkov<V,E> extends RelativeAuthorityRanker<V,E>
Algorithm variant ofPageRankWithPriors
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();
- See Also:
- "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
-
-
Field Summary
Fields Modifier and Type Field Description private static java.lang.String
CURRENT_RANK
private int
mNumSteps
(package private) java.util.HashMap<V,java.lang.Number>
mPreviousRankingsMap
static java.lang.String
RANK_SCORE
-
Fields inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
priorRankScoreMap
-
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
edgeRankScores, vertexRankScores
-
-
Constructor Summary
Constructors Constructor Description KStepMarkov(DirectedGraph<V,E> graph, java.util.Set<V> priors, int k, java.util.Map<E,java.lang.Number> edgeWeights)
Construct the algorihm instance and initializes the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected double
getCurrentRankScore(V v)
java.lang.String
getRankScoreKey()
The user datum key used to store the rank scores.protected void
incrementRankScore(V v, double rankValue)
protected void
initializeRankings()
protected void
setCurrentRankScore(V v, double rankValue)
void
step()
Evaluate the result of the current iteration.protected void
updateRankings()
-
Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
finalizeIterations, getPriorRankScore, getPriors, setPriorRankScore, setPriors
-
Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
assignDefaultEdgeTransitionWeights, getEdgeRankScore, getEdgeRankScore, getEdgeRankScores, getEdgeRankScores, getEdgeWeight, getEdgeWeights, getGraph, getRankings, getRankScores, getVertexCount, getVertexRankScore, getVertexRankScore, getVertexRankScores, getVertexRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, onFinalize, printRankings, removeEdgeRankScore, removeEdgeRankScore, removeVertexRankScore, removeVertexRankScore, reset, setEdgeRankScore, setEdgeRankScore, setEdgeWeight, setEdgeWeights, setNormalizeRankings, setRemoveRankScoresOnFinalize, setVertexRankScore, setVertexRankScore
-
Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision
-
-
-
-
Field Detail
-
RANK_SCORE
public static final java.lang.String RANK_SCORE
- See Also:
- Constant Field Values
-
CURRENT_RANK
private static final java.lang.String CURRENT_RANK
- See Also:
- Constant Field Values
-
mNumSteps
private int mNumSteps
-
mPreviousRankingsMap
java.util.HashMap<V,java.lang.Number> mPreviousRankingsMap
-
-
Constructor Detail
-
KStepMarkov
public KStepMarkov(DirectedGraph<V,E> graph, java.util.Set<V> priors, int k, java.util.Map<E,java.lang.Number> edgeWeights)
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 reasonableedgeWeights
- the weight for each edge
-
-
Method Detail
-
getRankScoreKey
public java.lang.String getRankScoreKey()
The user datum key used to store the rank scores.- Specified by:
getRankScoreKey
in classAbstractRanker<V,E>
- Returns:
- the key
-
incrementRankScore
protected void incrementRankScore(V v, double rankValue)
-
getCurrentRankScore
protected double getCurrentRankScore(V v)
-
setCurrentRankScore
protected void setCurrentRankScore(V v, double rankValue)
-
initializeRankings
protected void initializeRankings()
-
step
public void step()
Description copied from class:IterativeProcess
Evaluate the result of the current iteration.- Specified by:
step
in interfaceIterativeContext
- Specified by:
step
in classIterativeProcess
-
updateRankings
protected void updateRankings()
-
-