edu.uci.ics.jung.algorithms.scoring
Class KStepMarkov<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,S>
      extended by edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,Double>
          extended by edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
              extended by edu.uci.ics.jung.algorithms.scoring.KStepMarkov<V,E>
All Implemented Interfaces:
VertexScorer<V,Double>, IterativeContext

public class KStepMarkov<V,E>
extends PageRankWithPriors<V,E>

A special case of PageRankWithPriors in which the final scores represent a probability distribution over position assuming a random (Markovian) walk of exactly k steps, based on the initial distribution specified by the priors.

NOTE: The version of KStepMarkov in algorithms.importance (and in JUNG 1.x) is believed to be incorrect: rather than returning a score which represents a probability distribution over position assuming a k-step random walk, it returns a score which represents the sum over all steps of the probability for each step. If you want that behavior, set the 'cumulative' flag as follows before calling evaluate():

     KStepMarkov ksm = new KStepMarkov(...);
     ksm.setCumulative(true);
     ksm.evaluate();
 
By default, the 'cumulative' flag is set to false. NOTE: THIS CLASS IS NOT YET COMPLETE. USE AT YOUR OWN RISK. (The original behavior is captured by the version still available in algorithms.importance.)

See Also:
"Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003", PageRank, PageRankWithPriors

Field Summary
 
Fields inherited from class edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors
disappearing_potential
 
Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors
alpha, vertex_priors
 
Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer
edge_weights, graph, hyperedges_are_self_loops, max_delta, max_iterations, output_reversed, tolerance, total_iterations
 
Constructor Summary
KStepMarkov(Hypergraph<V,E> graph, int steps)
          Creates an instance based on the specified graph and number of steps to take.
KStepMarkov(Hypergraph<V,E> graph, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights, org.apache.commons.collections15.Transformer<V,Double> vertex_priors, int steps)
          Creates an instance based on the specified graph, edge weights, vertex priors (initial scores), and number of steps to take.
KStepMarkov(Hypergraph<V,E> graph, org.apache.commons.collections15.Transformer<V,Double> vertex_priors, int steps)
          Creates an instance based on the specified graph, vertex priors (initial scores), and number of steps to take.
 
Method Summary
 void setCumulative(boolean cumulative)
          Specifies whether this instance should assign a score to each vertex based on the
 double update(V v)
          Updates the value for this vertex.
 
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors
afterStep, collectDisappearingPotential
 
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors
getAlpha, getVertexPrior, getVertexPriors, initialize
 
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer
acceptDisconnectedGraph, done, evaluate, getAdjustedIncidentCount, getCurrentValue, getEdgeWeight, getEdgeWeights, getIterations, getMaxIterations, getOutputValue, getTolerance, getVertexScore, isDisconnectedGraphOK, setCurrentValue, setEdgeWeights, setHyperedgesAreSelfLoops, setMaxIterations, setOutputValue, setTolerance, step, swapOutputForCurrent, updateMaxDelta
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface edu.uci.ics.jung.algorithms.scoring.VertexScorer
getVertexScore
 

Constructor Detail

KStepMarkov

public KStepMarkov(Hypergraph<V,E> graph,
                   org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
                   org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
                   int steps)
Creates an instance based on the specified graph, edge weights, vertex priors (initial scores), and number of steps to take.

Parameters:
graph - the input graph
edge_weights - the edge weights (transition probabilities)
vertex_priors - the initial probability distribution (score assignment)
steps - the number of times that step() will be called by evaluate

KStepMarkov

public KStepMarkov(Hypergraph<V,E> graph,
                   org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
                   int steps)
Creates an instance based on the specified graph, vertex priors (initial scores), and number of steps to take. The edge weights (transition probabilities) are set to default values (a uniform distribution over all outgoing edges).

Parameters:
graph - the input graph
vertex_priors - the initial probability distribution (score assignment)
steps - the number of times that step() will be called by evaluate

KStepMarkov

public KStepMarkov(Hypergraph<V,E> graph,
                   int steps)
Creates an instance based on the specified graph and number of steps to take. The edge weights (transition probabilities) and vertex initial scores (prior probabilities) are set to default values (a uniform distribution over all outgoing edges, and a uniform distribution over all vertices, respectively).

Parameters:
graph - the input graph
steps - the number of times that step() will be called by evaluate
Method Detail

setCumulative

public void setCumulative(boolean cumulative)
Specifies whether this instance should assign a score to each vertex based on the

Parameters:
cumulative -

update

public double update(V v)
Updates the value for this vertex. Called by step().

Overrides:
update in class PageRankWithPriors<V,E>
Parameters:
v - the vertex whose value is to be updated
Returns:


Copyright © 2009. All Rights Reserved.