com.sun.sgs.impl.service.nodemap.affinity
Class AffinityGroupGoodness

java.lang.Object
  com.sun.sgs.impl.service.nodemap.affinity.AffinityGroupGoodness

public final class AffinityGroupGoodness
extends Object

Utility methods for "goodness" measurements of found groups.

Method Summary

static double	calcJaccard(Collection<AffinityGroup> sample1, Collection<AffinityGroup> sample2) Calculates Jaccard's index for a pair of affinity group collections, which is a measurement of similarity of the groups found in the two collections.
static double	calcModularity(edu.uci.ics.jung.graph.Graph<LabelVertex,WeightedEdge> graph, Collection<AffinityGroup> groups) Given a graph and a set of partitions of it, calculate the modularity.

Methods inherited from class java.lang.Object

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

Method Detail

calcModularity

public static double calcModularity(edu.uci.ics.jung.graph.Graph<LabelVertex,WeightedEdge> graph,
                                    Collection<AffinityGroup> groups)

Given a graph and a set of partitions of it, calculate the modularity. Modularity is a quality measure for the goodness of a clustering algorithm, and is, essentially, the number of edges within communities subtracted by the expected number of such edges.

The modularity will be a number between 0.0 and 1.0, with a higher number being better.

See "Finding community structure in networks using eigenvectors of matrices" 2006 Mark Newman and "Finding community structure in very large networks" 2004 Clauset, Newman, Moore.

Note that modularity can only be calculated on a complete graph.

Parameters:

graph - the graph which was divided into communities

groups - the communities found in the graph

Returns:

the modularity of the groups found in the graph

calcJaccard

public static double calcJaccard(Collection<AffinityGroup> sample1,
                                 Collection<AffinityGroup> sample2)

Calculates Jaccard's index for a pair of affinity group collections, which is a measurement of similarity of the groups found in the two collections. The value will be between 0.0 and 1.0, with higher values indicating stronger similarity between two samples. See page 8 of "Near linear time algorithm to detect community structures in large-scale networks" 2007 Raghavan, Albert, Kumara.

Because Jaccard's index uses computed groups, rather than a graph, it can be useful when the graphs are distributed or incomplete.

Parameters:

sample1 - the first sample

sample2 - the second sample

Returns:

the Jaccard index, a value between 0.0 and 1.0, with higher values indicating more similarity