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 and Description
static java.lang.String	RANK_SCORE

Constructor Summary

Constructors

Constructor and 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 and Description
java.lang.String	getRankScoreKey() The user datum key used to store the rank scores.
void	step() Evaluate the result of the current iteration.

Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker

setPriorRankScore

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker

getEdgeRankScore, getEdgeRankScore, getEdgeRankScores, getEdgeRankScores, getEdgeWeights, getRankings, getRankScores, getVertexRankScore, getVertexRankScore, getVertexRankScores, getVertexRankScores, isRankingEdges, isRankingNodes, printRankings, reset, setEdgeWeights, setNormalizeRankings, setRemoveRankScoresOnFinalize

Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess

done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision

Methods inherited from class java.lang.Object

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

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

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