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
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();
- See Also:
-
Field Summary
FieldsFields 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
ConstructorsConstructorDescriptionKStepMarkov
(DirectedGraph<V, E> graph, Set<V> priors, int k, Map<E, Number> edgeWeights) Construct the algorihm instance and initializes the algorithm. -
Method Summary
Modifier and TypeMethodDescriptionprotected double
The user datum key used to store the rank scores.protected void
incrementRankScore
(V v, double rankValue) protected void
protected void
setCurrentRankScore
(V v, double rankValue) void
step()
Evaluate the result of the current iteration.protected void
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 Details
-
RANK_SCORE
- See Also:
-
CURRENT_RANK
- See Also:
-
mNumSteps
private int mNumSteps -
mPreviousRankingsMap
-
-
Constructor Details
-
KStepMarkov
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 Details
-
getRankScoreKey
The user datum key used to store the rank scores.- Specified by:
getRankScoreKey
in classAbstractRanker<V,
E> - Returns:
- the key
-
incrementRankScore
-
getCurrentRankScore
-
setCurrentRankScore
-
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()
-