org.apache.giraph.examples

Class RandomWalkWithRestartComputation

java.lang.Object

org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable<I,V,E>

org.apache.giraph.worker.WorkerAggregatorDelegator<I,V,E>

org.apache.giraph.graph.AbstractComputation<I,V,E,M,M>

org.apache.giraph.graph.BasicComputation<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E,org.apache.hadoop.io.DoubleWritable>

org.apache.giraph.examples.RandomWalkComputation<org.apache.hadoop.io.DoubleWritable>

org.apache.giraph.examples.RandomWalkWithRestartComputation

All Implemented Interfaces:

AggregatorUsage, GiraphConfigurationSettable<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>, ImmutableClassesGiraphConfigurable<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>, TypesHolder<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>, Computation<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>, WorkerAggregatorUsage, WorkerBroadcastUsage, WorkerGlobalCommUsage, WorkerIndexUsage<org.apache.hadoop.io.LongWritable>, WorkerReduceUsage

public class RandomWalkWithRestartComputation
extends RandomWalkComputation<org.apache.hadoop.io.DoubleWritable>

Executes "RandomWalkWithRestart", a random walk on the graph which is biased towards a source vertex. The resulting probabilities of staying at a given vertex can be interpreted as a measure of proximity to the source vertex.

Constructor Summary

Constructors

Constructor and Description
RandomWalkWithRestartComputation()

Method Summary

Modifier and Type	Method and Description
protected double	recompute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable> vertex, Iterable<org.apache.hadoop.io.DoubleWritable> transitionProbabilities, double teleportationProbability) Perform a single step of a random walk computation.
protected double	transitionProbability(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable> vertex, double stateProbability, Edge<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable> edge) Compute the probability of transitioning to a neighbor vertex

Methods inherited from class org.apache.giraph.examples.RandomWalkComputation

compute, getDanglingProbability, getPreviousCumulativeProbability, initialProbability, teleportationProbability

Methods inherited from class org.apache.giraph.graph.AbstractComputation

addEdgeRequest, addVertexRequest, addVertexRequest, getContext, getMyWorkerIndex, getSuperstep, getTotalNumEdges, getTotalNumVertices, getWorkerContext, getWorkerCount, getWorkerForVertex, initialize, postSuperstep, preSuperstep, removeEdgesRequest, removeVertexRequest, sendMessage, sendMessageToAllEdges, sendMessageToMultipleEdges

Methods inherited from class org.apache.giraph.worker.WorkerAggregatorDelegator

aggregate, getAggregatedValue, getBroadcast, reduce, reduceMerge, setWorkerGlobalCommUsage

Methods inherited from class org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable

getConf, setConf

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.giraph.conf.ImmutableClassesGiraphConfigurable

getConf

Methods inherited from interface org.apache.giraph.conf.GiraphConfigurationSettable

setConf

Methods inherited from interface org.apache.giraph.worker.WorkerBroadcastUsage

getBroadcast

Methods inherited from interface org.apache.giraph.worker.WorkerReduceUsage

reduce, reduceMerge

Methods inherited from interface org.apache.giraph.worker.WorkerAggregatorUsage

aggregate

Methods inherited from interface org.apache.giraph.aggregators.AggregatorUsage

getAggregatedValue

Constructor Detail

RandomWalkWithRestartComputation

public RandomWalkWithRestartComputation()

Method Detail

transitionProbability

protected double transitionProbability(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable> vertex,
                                       double stateProbability,
                                       Edge<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable> edge)

Description copied from class: RandomWalkComputation

Compute the probability of transitioning to a neighbor vertex

Specified by:

transitionProbability in class RandomWalkComputation<org.apache.hadoop.io.DoubleWritable>

Parameters:

vertex - Vertex

stateProbability - current steady state probability of the vertex

edge - edge to neighbor

Returns:

the probability of transitioning to a neighbor vertex

recompute

protected double recompute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable> vertex,
                           Iterable<org.apache.hadoop.io.DoubleWritable> transitionProbabilities,
                           double teleportationProbability)

Description copied from class: RandomWalkComputation

Perform a single step of a random walk computation.

Specified by:

recompute in class RandomWalkComputation<org.apache.hadoop.io.DoubleWritable>

Parameters:

vertex - Vertex

transitionProbabilities - Messages received in the previous step.

teleportationProbability - Probability of teleporting to another vertex.

Returns:

The new probability value.