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();
 

Author:

Scott White, Tom Nelson - adapter to jung2

See Also:

"Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"

Field Summary

static 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

KStepMarkov(DirectedGraph<V,E> graph, Set<V> priors, int k, Map<E,Number> edgeWeights)
Construct the algorihm instance and initializes the algorithm.

Method Summary

protected double	getCurrentRankScore(V v)
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 String RANK_SCORE

See Also:

Constant Field Values

Constructor Detail

KStepMarkov

public KStepMarkov(DirectedGraph<V,E> graph,
                   Set<V> priors,
                   int k,
                   Map<E,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 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()