Class 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"
    • Constructor Detail

      • KStepMarkov

        public KStepMarkov​(edu.uci.ics.jung.graph.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()
      • updateRankings

        protected void updateRankings()