com.soteradefense.dga.hbse

Class HBSEComputation

java.lang.Object

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

org.apache.giraph.graph.AbstractComputation<Text,VertexData,Text,PathData,PathData>

com.soteradefense.dga.hbse.HBSEComputation

All Implemented Interfaces:

AggregatorUsage, ImmutableClassesGiraphConfigurable<Text,VertexData,Text>, TypesHolder<Text,VertexData,Text,PathData,PathData>, Computation<Text,VertexData,Text,PathData,PathData>, WorkerAggregatorUsage

public class HBSEComputation
extends AbstractComputation<Text,VertexData,Text,PathData,PathData>

Calculates Shortest paths, and accumulates pair dependency information.

Use with SBMasterCompute to find an approximated set of vertices with highest betweenness centrality.

For background information on the approximation method see: See "W. Chong, Efficient Extraction of High-Betweenness Vertices"

For background information on the method of accumulation of pair dependencies and shortest path data see: See "U. Brandes, A Faster Algorithm for Betweenness Centrality"

Constructor Summary

Constructors

Constructor and Description
HBSEComputation()

Method Summary

Methods

Modifier and Type	Method and Description
void	compute(Vertex<Text,VertexData,Text> vertex, Iterable<PathData> messages) Works in two major stages which are repeated and coordinated by the setting of a global state (set by the master compute class) Stage 1: Discover shortest paths, and shortest path counts for each source vertex in a globally set pivot batch to each node in the graph. Stage 2: Accumulate pair dependencies.
HighBetweennessList	getNewHighBetweennessList(String id, double value) Get a new HighBetweennessList object, configured with the betweenness.set.maxSize option from the job conf.
void	initialize(GraphState graphState, WorkerClientRequestProcessor<Text,VertexData,Text> workerClientRequestProcessor, GraphTaskManager<Text,VertexData,Text> graphTaskManager, WorkerAggregatorUsage workerAggregatorUsage, WorkerContext workerContext)

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

addEdgeRequest, addVertexRequest, addVertexRequest, aggregate, getAggregatedValue, getContext, getSuperstep, getTotalNumEdges, getTotalNumVertices, getWorkerContext, postSuperstep, preSuperstep, removeEdgesRequest, removeVertexRequest, sendMessage, sendMessageToAllEdges, sendMessageToMultipleEdges

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, setConf

Constructor Detail

HBSEComputation

public HBSEComputation()

Method Detail

initialize

public void initialize(GraphState graphState,
              WorkerClientRequestProcessor<Text,VertexData,Text> workerClientRequestProcessor,
              GraphTaskManager<Text,VertexData,Text> graphTaskManager,
              WorkerAggregatorUsage workerAggregatorUsage,
              WorkerContext workerContext)

Specified by:

initialize in interface Computation<Text,VertexData,Text,PathData,PathData>

Overrides:

initialize in class AbstractComputation<Text,VertexData,Text,PathData,PathData>

compute

public void compute(Vertex<Text,VertexData,Text> vertex,
           Iterable<PathData> messages)
             throws IOException

Works in two major stages which are repeated and coordinated by the setting of a global state (set by the master compute class)

• Stage 1: Discover shortest paths, and shortest path counts for each source vertex in a globally set pivot batch to each node in the graph.
• Stage 2: Accumulate pair dependencies.

Specified by:

compute in interface Computation<Text,VertexData,Text,PathData,PathData>

Specified by:

compute in class AbstractComputation<Text,VertexData,Text,PathData,PathData>

Throws:

IOException

getNewHighBetweennessList

public HighBetweennessList getNewHighBetweennessList(String id,
                                            double value)

Get a new HighBetweennessList object, configured with the betweenness.set.maxSize option from the job conf. If not set size will default to 1.

Parameters:

id - Vertex Id

value - Betweenness Value

Returns:

an empty HighBetweennessList object.