com.soteradefense.dga.hbse

Class HBSEMasterCompute

java.lang.Object

org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable

org.apache.giraph.master.MasterCompute

org.apache.giraph.master.DefaultMasterCompute

com.soteradefense.dga.hbse.HBSEMasterCompute

All Implemented Interfaces:

AggregatorUsage, ImmutableClassesGiraphConfigurable, MasterAggregatorUsage, Writable

public class HBSEMasterCompute
extends DefaultMasterCompute

Coordinates Global state for the SBVertex to calculate shortest paths, accumulates pair dependency information, and monitor high betweenness set stability.

Required configuration settings:

• fs.defaultFS OR fs.default.name: If not set in the environment you can set them as a custom arguments. typically this will not need to be set.
• betweenness.output.dir: Directory in HDFS used to write the high betweenness set.
• betweenness.set.stability: Integer value, algorithm completes with the high betweenness set changes by less than this value, checked after each cycle.
• betweenness.set.stability.counter: Integer value, number of times the stability threshold must be reached.
• betweenness.set.maxSize: Size the result set desired.
• pivot.batch.size: Number of pivots to use in each batch
• pivot.batch.size.initial: Number of pivots to use in the first batch (defaults to pivot.batch.size)
• vertex.count: The number of vertices to be loaded
• betweenness.shortest.path.phases: Number of shortest path phases to run for every 1 dependency accumulation phase.

WARNING: id values for all vertices must be in 0,1,2,...N where N=vertex.count-1

For background information on the approximation method see: See "W. Chong, Efficent 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"

Field Summary

Fields

Modifier and Type	Field and Description
static String	BETWEENNESS_OUTPUT_DIR Configuration Identifier for the directory to output the highbetweenness set.
static String	BETWEENNESS_SET_MAX_SIZE Configuration Identifier for the maximum number of nodes in the betweenness set.
static String	BETWEENNESS_SET_STABILITY Configuration Identifier for the set stability cut off point (margin of error).
static String	BETWEENNESS_SET_STABILITY_COUNTER Configuration Identifier for the set stability counter cut off point (margin of error).
static String	BETWEENNESS_SHORTEST_PATH_PHASES Configuration Identifier for the number of shortest path phases to run through.
static String	FINAL_SET_CSV This is the filename for the final highbetweenness set
static String	FS_DEFAULT_FS Configuration Identifier for the default file system.
static String	FS_DEFAULT_NAME Configuration Identifier for the default name.
static String	HIGH_BC_SET_AGG Aggregator Identifier for the saved highbetweenness set.
static String	INITIAL_PIVOT_PERCENT Aggregator Identifier that stores the percentage of initial pivots to choose per batch.
static String	PIVOT_AGG Aggregator Sum for the total number of pivots selected.
static String	PIVOT_BATCH_RANDOM_SEED Configuration Identifier for the random seed value when choosing new pivot points.
static String	PIVOT_BATCH_SIZE Configuration Identifier for the pivot point batch size as a percent integer.
static String	PIVOT_BATCH_SIZE_INITIAL Configuration Identifier for the initial pivot point batch size as a percent integer.
static String	PIVOT_PERCENT Aggregator Identifier that stores the percentage of pivots to choose per batch.
static String	STATE_AGG Aggregator Identifier that gets the state of the computation.
static String	STATS_CSV The filename where the stats are written
static String	UPDATE_COUNT_AGG Aggregator Identifier for the number of nodes changed in the highbetweenness list comparison.
static String	VERTEX_COUNT Configuration Identifier for the number of vertices to perform the operation on.

Constructor Summary

Constructors

Constructor and Description
HBSEMasterCompute()

Method Summary

Methods

Modifier and Type	Method and Description
void	compute() Coordinates the computation phases of SBVertex by monitoring for the completion of each state and moving to the next state.
void	initialize() Read options from configuration file and set up aggregators (global communication)

Methods inherited from class org.apache.giraph.master.DefaultMasterCompute

readFields, write

Methods inherited from class org.apache.giraph.master.MasterCompute

getAggregatedValue, getComputation, getContext, getMessageCombiner, getSuperstep, getTotalNumEdges, getTotalNumVertices, haltComputation, isHalted, registerAggregator, registerPersistentAggregator, setAggregatedValue, setComputation, setIncomingMessage, setMessageCombiner, setOutgoingMessage

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

Field Detail

STATE_AGG

public static final String STATE_AGG

Aggregator Identifier that gets the state of the computation.

See Also:

Constant Field Values

PIVOT_AGG

public static final String PIVOT_AGG

Aggregator Sum for the total number of pivots selected.

See Also:

Constant Field Values

UPDATE_COUNT_AGG

public static final String UPDATE_COUNT_AGG

Aggregator Identifier for the number of nodes changed in the highbetweenness list comparison.

See Also:

Constant Field Values

HIGH_BC_SET_AGG

public static final String HIGH_BC_SET_AGG

Aggregator Identifier for the saved highbetweenness set.

See Also:

Constant Field Values

BETWEENNESS_OUTPUT_DIR

public static final String BETWEENNESS_OUTPUT_DIR

Configuration Identifier for the directory to output the highbetweenness set.

See Also:

Constant Field Values

BETWEENNESS_SHORTEST_PATH_PHASES

public static final String BETWEENNESS_SHORTEST_PATH_PHASES

Configuration Identifier for the number of shortest path phases to run through.

See Also:

Constant Field Values

BETWEENNESS_SET_STABILITY

public static final String BETWEENNESS_SET_STABILITY

Configuration Identifier for the set stability cut off point (margin of error).

See Also:

Constant Field Values

BETWEENNESS_SET_STABILITY_COUNTER

public static final String BETWEENNESS_SET_STABILITY_COUNTER

Configuration Identifier for the set stability counter cut off point (margin of error).

See Also:

Constant Field Values

BETWEENNESS_SET_MAX_SIZE

public static final String BETWEENNESS_SET_MAX_SIZE

Configuration Identifier for the maximum number of nodes in the betweenness set.

See Also:

Constant Field Values

PIVOT_BATCH_SIZE

public static final String PIVOT_BATCH_SIZE

Configuration Identifier for the pivot point batch size as a percent integer.

See Also:

Constant Field Values

PIVOT_BATCH_SIZE_INITIAL

public static final String PIVOT_BATCH_SIZE_INITIAL

Configuration Identifier for the initial pivot point batch size as a percent integer.

See Also:

Constant Field Values

PIVOT_BATCH_RANDOM_SEED

public static final String PIVOT_BATCH_RANDOM_SEED

Configuration Identifier for the random seed value when choosing new pivot points.

See Also:

Constant Field Values

VERTEX_COUNT

public static final String VERTEX_COUNT

Configuration Identifier for the number of vertices to perform the operation on.

See Also:

Constant Field Values

FS_DEFAULT_FS

public static final String FS_DEFAULT_FS

Configuration Identifier for the default file system.

See Also:

Constant Field Values

FS_DEFAULT_NAME

public static final String FS_DEFAULT_NAME

Configuration Identifier for the default name.

See Also:

Constant Field Values

FINAL_SET_CSV

public static final String FINAL_SET_CSV

This is the filename for the final highbetweenness set

See Also:

Constant Field Values

STATS_CSV

public static final String STATS_CSV

The filename where the stats are written

See Also:

Constant Field Values

PIVOT_PERCENT

public static final String PIVOT_PERCENT

Aggregator Identifier that stores the percentage of pivots to choose per batch.

See Also:

Constant Field Values

INITIAL_PIVOT_PERCENT

public static final String INITIAL_PIVOT_PERCENT

Aggregator Identifier that stores the percentage of initial pivots to choose per batch.

See Also:

Constant Field Values

Constructor Detail

HBSEMasterCompute

public HBSEMasterCompute()

Method Detail

initialize

public void initialize()
                throws InstantiationException,
                       IllegalAccessException

Read options from configuration file and set up aggregators (global communication)

Overrides:

initialize in class DefaultMasterCompute

Throws:

InstantiationException - if it is unable to register an aggregator with a specific class.

IllegalAccessException - if it is unable to access the class passed in as an aggregator.

compute

public void compute()

Coordinates the computation phases of SBVertex by monitoring for the completion of each state and moving to the next state.

1. selects pivots
2. monitors for completion of shortest paths
3. starts pair dependency phase
4. monitors for completion of pair dependency
5. checks high betweenness set stability
6. if set is stable save set and exit else select new pivots and start new shortest path phase

Overrides:

compute in class DefaultMasterCompute