org.apache.giraph.examples

Class RandomWalkComputation<E extends org.apache.hadoop.io.Writable>

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<E>

Type Parameters:

E - edge type

All Implemented Interfaces:

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

Direct Known Subclasses:

PageRankComputation, RandomWalkWithRestartComputation

public abstract class RandomWalkComputation<E extends org.apache.hadoop.io.Writable>
extends BasicComputation<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E,org.apache.hadoop.io.DoubleWritable>

Base class for executing a random walk on a graph

Constructor Summary

Constructors

Constructor and Description
RandomWalkComputation()

Method Summary

Modifier and Type	Method and Description
void	compute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E> vertex, Iterable<org.apache.hadoop.io.DoubleWritable> messages) Must be defined by user to do computation on a single Vertex.
protected double	getDanglingProbability() Returns the cumulative probability from dangling vertices.
protected double	getPreviousCumulativeProbability() Returns the cumulative probability from dangling vertices.
protected double	initialProbability() Compute an initial probability value for the vertex.
protected abstract double	recompute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E> vertex, Iterable<org.apache.hadoop.io.DoubleWritable> messages, double teleportationProbability) Perform a single step of a random walk computation.
protected double	teleportationProbability() Reads the teleportation probability from the configuration
protected abstract double	transitionProbability(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E> vertex, double stateProbability, Edge<org.apache.hadoop.io.LongWritable,E> edge) Compute the probability of transitioning to a neighbor vertex

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

RandomWalkComputation

public RandomWalkComputation()

Method Detail

initialProbability

protected double initialProbability()

Compute an initial probability value for the vertex. Per default, we start with a uniform distribution.

Returns:

The initial probability value.

transitionProbability

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

Compute the probability of transitioning to a neighbor vertex

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 abstract double recompute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E> vertex,
                                    Iterable<org.apache.hadoop.io.DoubleWritable> messages,
                                    double teleportationProbability)

Perform a single step of a random walk computation.

Parameters:

vertex - Vertex

messages - Messages received in the previous step.

teleportationProbability - Probability of teleporting to another vertex.

Returns:

The new probability value.

getDanglingProbability

protected double getDanglingProbability()

Returns the cumulative probability from dangling vertices.

Returns:

The cumulative probability from dangling vertices.

getPreviousCumulativeProbability

protected double getPreviousCumulativeProbability()

Returns the cumulative probability from dangling vertices.

Returns:

The cumulative probability from dangling vertices.

compute

public void compute(Vertex<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E> vertex,
                    Iterable<org.apache.hadoop.io.DoubleWritable> messages)
             throws IOException

Description copied from class: AbstractComputation

Must be defined by user to do computation on a single Vertex.

Specified by:

compute in interface Computation<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E extends org.apache.hadoop.io.Writable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>

Specified by:

compute in class AbstractComputation<org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.DoubleWritable,E extends org.apache.hadoop.io.Writable,org.apache.hadoop.io.DoubleWritable,org.apache.hadoop.io.DoubleWritable>

Parameters:

vertex - Vertex

messages - Messages that were sent to this vertex in the previous superstep. Each message is only guaranteed to have a life expectancy as long as next() is not called.

Throws:

IOException

teleportationProbability

protected double teleportationProbability()

Reads the teleportation probability from the configuration

Returns:

teleportation probability