Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.importance
Class KStepMarkov

    java.lang.Object
      edu.uci.ics.jung.algorithms.IterativeProcess
          edu.uci.ics.jung.algorithms.importance.AbstractRanker
              edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
                  edu.uci.ics.jung.algorithms.importance.KStepMarkov

public class KStepMarkov
extends RelativeAuthorityRanker

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

Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
`DEFAULT_EDGE_WEIGHT_KEY`

Constructor Summary
`KStepMarkov(DirectedGraph graph, Set priors, int k, String edgeWeightKeyName)` Construct the algorihm instance and initializes the algorithm.

Method Summary
`protected double` | `evaluateIteration()` Evaluate the result of the current interation.
`protected double` | `getCurrentRankScore(Element v)`
`String` | `getRankScoreKey()` The user datum key used to store the rank scores.
`protected void` | `incrementRankScore(Element v, double rankValue)`
`protected void` | `initializeRankings()`
`protected void` | `onFinalize(Element udc)`
`protected void` | `setCurrentRankScore(Element v, double rankValue)`
`protected void` | `updateRankings()`

Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
`finalizeIterations, getPriorRankScore, getPriorRankScoreKey, getPriors, setPriorRankScore, setPriors`

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
`assignDefaultEdgeTransitionWeights, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScore, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, printRankings, reinitialize, setEdgeWeight, setNormalizeRankings, setRankScore, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey`

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess
`evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations`

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 graph,
                       Set priors,
                       int k,
                       String edgeWeightKeyName)

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

Method Detail

### getRankScoreKey

    public String getRankScoreKey()

  The user datum key used to store the rank scores.

  Specified by:
    `getRankScoreKey` in class `AbstractRanker`
  Returns:
    the key

### incrementRankScore

    protected void incrementRankScore(Element v,
                                      double rankValue)

### getCurrentRankScore

    protected double getCurrentRankScore(Element v)

### setCurrentRankScore

    protected void setCurrentRankScore(Element v,
                                       double rankValue)

### initializeRankings

    protected void initializeRankings()

### evaluateIteration

    protected double evaluateIteration()

  Description copied from class: `IterativeProcess`
  Evaluate the result of the current interation.

  Specified by:
    `evaluateIteration` in class `IterativeProcess`
  Returns:
    the estimated precision of the result.

### onFinalize

    protected void onFinalize(Element udc)

  Overrides:
    `onFinalize` in class `AbstractRanker`

### updateRankings

    protected void updateRankings()

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD