com.sun.sgs.impl.service.nodemap.affinity.single
Class SingleLabelPropagation

java.lang.Object
  com.sun.sgs.impl.service.nodemap.affinity.BasicState
      com.sun.sgs.impl.service.nodemap.affinity.AbstractLPA
          com.sun.sgs.impl.service.nodemap.affinity.single.SingleLabelPropagation

All Implemented Interfaces:

AffinityGroupFinder, LPAAffinityGroupFinder

public class SingleLabelPropagation
extends AbstractLPA
implements LPAAffinityGroupFinder

A single-node implementation of the algorithm presented in "Near linear time algorithm to detect community structures in large-scale networks" Raghavan, Albert and Kumara 2007.

Nested Class Summary

Nested classes/interfaces inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

BasicState.State

Field Summary

Fields inherited from class com.sun.sgs.impl.service.nodemap.affinity.AbstractLPA

DEFAULT_NUM_THREADS, executor, graph, iterations, localNodeId, logger, NUM_THREADS_PROPERTY, numThreads, PROP_NAME, ran, vertices

Fields inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

state

Constructor Summary

SingleLabelPropagation(AffinityGraphBuilder builder, ProfileCollector col, Properties properties)
Constructs a new instance of the label propagation algorithm.

SingleLabelPropagation(AffinityGraphBuilder builder, ProfileCollector col, Properties properties, AffinityGroupFinderStats stats)
Constructs a new instance of the label propagation algorithm.

Method Summary

void	disable() Disables the finder.
protected void	doOtherInitialization() Perform any algorithm specific initialization for an algorithm run.
protected long	doOtherNeighbors(LabelVertex vertex, Map<Integer,Long> labelMap, StringBuilder logSB) Update the label map with any other neighbors known to a particular algorithm.
void	enable() Enables the finder.
NavigableSet<RelocatingAffinityGroup>	findAffinityGroups() Finds affinity groups across all nodes in the Darkstar cluster.
void	shutdown() Shuts down the finder.

Methods inherited from class com.sun.sgs.impl.service.nodemap.affinity.AbstractLPA

gatherGroups, initializeLPARun, setMostFrequentLabel

Methods inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

checkForDisabledOrShutdownState, checkForShutdownState, setDisabledState, setEnabledState, setShutdownState

Methods inherited from class java.lang.Object

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

Constructor Detail

SingleLabelPropagation

public SingleLabelPropagation(AffinityGraphBuilder builder,
                              ProfileCollector col,
                              Properties properties)
                       throws Exception

Constructs a new instance of the label propagation algorithm.

Parameters:

builder - the graph producer

col - the profile collector

properties - the properties for configuring this service

Throws:

IllegalArgumentException - if numThreads is less than 1

Exception - if any other error occurs

SingleLabelPropagation

public SingleLabelPropagation(AffinityGraphBuilder builder,
                              ProfileCollector col,
                              Properties properties,
                              AffinityGroupFinderStats stats)
                       throws Exception

Constructs a new instance of the label propagation algorithm.

Parameters:

builder - the graph producer

col - the profile collector

properties - the properties for configuring this service

stats - pre-constructed JMX Mbean or null if one should be constructed

Throws:

IllegalArgumentException - if numThreads is less than 1

Exception - if any other error occurs

Method Detail

doOtherInitialization

protected void doOtherInitialization()

Perform any algorithm specific initialization for an algorithm run.

Specified by:

doOtherInitialization in class AbstractLPA

doOtherNeighbors

protected long doOtherNeighbors(LabelVertex vertex,
                                Map<Integer,Long> labelMap,
                                StringBuilder logSB)

Update the label map with any other neighbors known to a particular algorithm.

Specified by:

doOtherNeighbors in class AbstractLPA

Parameters:

vertex - the vertex whose neighbors labels will be examined

labelMap - a map of labels to counts of neighbors using that label

logSB - a StringBuilder for gathering log info about neighbors

Returns:

the highest number of times a particular label is used among the other neighbors, or -1L if there are no other neighbors.

disable

public void disable()

Disables the finder.

Specified by:

disable in interface AffinityGroupFinder

enable

public void enable()

Enables the finder.

Specified by:

enable in interface AffinityGroupFinder

shutdown

public void shutdown()

Shuts down the finder.

Specified by:

shutdown in interface AffinityGroupFinder

findAffinityGroups

public NavigableSet<RelocatingAffinityGroup> findAffinityGroups()
                                                         throws AffinityGroupFinderFailedException

Finds affinity groups across all nodes in the Darkstar cluster. If no groups are found, an empty set is returned. If an error is encountered during a run, an AffinityGroupFinderFailedException is thrown. Errors include nodes not responding to server requests.

Find the communities, using a graph obtained from the graph builder provided at construction time. The communities are found using the label propagation algorithm.

This algorithm will not modify the graph by adding or removing vertices or edges, but it will modify the labels in the vertices.

This implementation is for graphs on a single node only, and is useful for testing algorithm optimizations. Finding affinity groups on a single node is, in general, not useful (the affinity groups are used for load balancing, and no load balancing is required on a single node).

Specified by:

findAffinityGroups in interface LPAAffinityGroupFinder

Returns:

the affinity groups

Throws:

AffinityGroupFinderFailedException - if there is an error