Package edu.uci.ics.jung.algorithms.importance

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 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:

"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

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

Methods inherited from class java.lang.Object

clone, equals, finalize, 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

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 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

edgeWeights - 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 class AbstractRanker<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 interface IterativeContext

Specified by:

step in class IterativeProcess

updateRankings

protected void updateRankings()