y.algo
Class Groups

java.lang.Object
  y.algo.Groups

public class Groups
extends Object

This class provides methods for automatically partitioning nodes of a graph into groups.

Method Summary

static int	biconnectedComponentGrouping(Graph graph, NodeMap groupIDs) This method partitions the graph by analyzing its biconnected component structure.
static int	edgeBetweennessClustering(Graph graph, NodeMap clusterIDs, boolean directed, int minGroupCount, int maxGroupCount, DataProvider edgeCosts) Partitions the graph into groups using edge betweenness centrality (see Centrality.edgeBetweenness(Graph, EdgeMap, boolean, DataProvider).
static int	edgeBetweennessClustering(Graph graph, NodeMap clusterIDs, double qualityTimeRatio, int minGroupCount, int maxGroupCount, boolean refine) Partitions the graph into groups using Edge Betweenness Clustering proposed by Girvan and Newman.

Methods inherited from class java.lang.Object

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

Method Detail

edgeBetweennessClustering

public static int edgeBetweennessClustering(Graph graph,
                                            NodeMap clusterIDs,
                                            boolean directed,
                                            int minGroupCount,
                                            int maxGroupCount,
                                            DataProvider edgeCosts)

Partitions the graph into groups using edge betweenness centrality (see Centrality.edgeBetweenness(Graph, EdgeMap, boolean, DataProvider). In each iteration the edge with the highest betweenness centrality is removed from the graph. The method stops, if there are no more edges to remove. The clustering with the best quality reached during the process will be returned.

Parameters:

graph - the input graph.

clusterIDs - used as return value. This map gets a cluster ID of integer type for every node.

directed - whether or not to consider the edges of the graph as directed.

minGroupCount - the minimum number of groups to be returned.

maxGroupCount - the maximum number of groups to be returned. The smaller this value is chosen the faster the overall computation time. Note that the upper bound on the number of groups is graph.N(). Note, that the number of returned groups is never less than the number of connected components of the graph.

edgeCosts - if null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.

Returns:

the number of different groups found.

Complexity:

O(graph.E())*O(edgeBetweenness) (Note: is practical faster because edge betweenness is computed for subgraphs during the process and this algorithm terminates after maxGroupCount groups have been determined.)

Preconditions:

minGroupCount <= maxGroupCount

minGroupCount <= graph.N()

maxGroupCount > 0

edgeBetweennessClustering

public static int edgeBetweennessClustering(Graph graph,
                                            NodeMap clusterIDs,
                                            double qualityTimeRatio,
                                            int minGroupCount,
                                            int maxGroupCount,
                                            boolean refine)

Partitions the graph into groups using Edge Betweenness Clustering proposed by Girvan and Newman. In each iteration the edge with the highest betweenness centrality is removed from the graph. The method stops, if there are no more edges to remove or if the requested maximum number of groups is found. The clustering with the best quality reached during the process is returned.

The algorithm includes several heuristic speed-up techniques available through the quality/time ratio. For the highest quality setting, it is used almost unmodified. The fast betweenness approximation of Brandes und Pich (Centrality Estimation in Large Networks) is employed for values around 0.5. Typically, this results in a tiny decrease in quality but a large speed-up and is the recommended setting. To achieve the lowest running time, a local betweenness calculation is used (Gregory: Local Betweenness for Finding Communities in Networks).

Parameters:

graph - the input graph.

clusterIDs - used as return value. This map gets a cluster ID of integer type for every node.

qualityTimeRatio - a value between 0.0 (low quality, fast) and 1.0 (high quality, slow). The recommended value is 0.5.

minGroupCount - the minimum number of groups to be returned.

maxGroupCount - the maximum number of groups to be returned. The smaller this value is chosen the faster the overall computation time. Note, that the upper bound on the number of groups is graph.N() and that the number of returned groups is never less than the number of connected components of the graph.

refine - whether the algorithm refines or discards the current grouping.

Returns:

the number of different groups found

Complexity:

O(graph.E())*O(edgeBetweenness) (Note: is practical faster because edge betweenness is computed for subgraphs during the process and this algorithm terminates after maxGroupCount groups have been determined.)

Preconditions:

minGroupCount <= maxGroupCount

minGroupCount <= graph.N()

maxGroupCount > 0

biconnectedComponentGrouping

public static int biconnectedComponentGrouping(Graph graph,
                                               NodeMap groupIDs)

This method partitions the graph by analyzing its biconnected component structure. Nodes will be grouped in a way that the nodes within each group are biconnected. Nodes that belong to multiple biconnected components will be assigned to exactly one of these components.

Parameters:

graph - the input graph.

groupIDs - used as return value. This map gets a cluster ID of integer type for every node.

Returns:

the number of different groups found.

Complexity:

O(graph.E()+graph.N())