Class KStepMarkov<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,Double>
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,Double>
edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
edu.uci.ics.jung.algorithms.scoring.KStepMarkov<V,E>
- All Implemented Interfaces:
VertexScorer<V,
,Double> IterativeContext
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:
-
Field Summary
FieldsFields 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
ConstructorsConstructorDescriptionKStepMarkov
(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 Number> edge_weights, com.google.common.base.Function<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, com.google.common.base.Function<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
Modifier and TypeMethodDescriptionprivate void
initialize
(int steps) 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
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
-
Field Details
-
cumulative
private boolean cumulative
-
-
Constructor Details
-
KStepMarkov
public KStepMarkov(Hypergraph<V, E> graph, com.google.common.base.Function<E, ? extends Number> edge_weights, com.google.common.base.Function<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 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, 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
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 Details
-
initialize
private void initialize(int steps) -
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
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
-