Class KStepMarkov<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,S>
-
- edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,java.lang.Double>
-
- edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
-
- edu.uci.ics.jung.algorithms.scoring.KStepMarkov<V,E>
-
- All Implemented Interfaces:
VertexScorer<V,java.lang.Double>
,IterativeContext
public class KStepMarkov<V,E> extends PageRankWithPriors<V,E>
A special case ofPageRankWithPriors
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
inalgorithms.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 callingevaluate()
: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 inalgorithms.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
Constructors Constructor Description 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, com.google.common.base.Function<E,? extends java.lang.Number> edge_weights, com.google.common.base.Function<V,java.lang.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, com.google.common.base.Function<V,java.lang.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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
setCumulative(boolean cumulative)
Specifies whether this instance should assign a score to each vertex based on the sum over all steps of the probability for each step.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, com.google.common.base.Function<E,? extends java.lang.Number> edge_weights, com.google.common.base.Function<V,java.lang.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 graphedge_weights
- the edge weights (transition probabilities)vertex_priors
- the initial probability distribution (score assignment)steps
- the number of times thatstep()
will be called byevaluate
-
KStepMarkov
public KStepMarkov(Hypergraph<V,E> graph, com.google.common.base.Function<V,java.lang.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 graphvertex_priors
- the initial probability distribution (score assignment)steps
- the number of times thatstep()
will be called byevaluate
-
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 graphsteps
- the number of times thatstep()
will be called byevaluate
-
-
Method Detail
-
setCumulative
public void setCumulative(boolean cumulative)
Specifies whether this instance should assign a score to each vertex based on the sum over all steps of the probability for each step. See the class-level documentation for details.- Parameters:
cumulative
- true if this instance should assign a cumulative score to each vertex
-
update
public double update(V v)
Updates the value for this vertex. Called bystep()
.- Overrides:
update
in classPageRankWithPriors<V,E>
- Parameters:
v
- the vertex whose value is to be updated- Returns:
- the updated value
-
-