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

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 Details

  • Constructor Details

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

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