edu.uci.ics.jung.algorithms.cluster
Class VoltageClusterer

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.cluster.VoltageClusterer

public class VoltageClusterer
extends Object

Clusters vertices of a Graph based on their ranks as calculated by VoltageRanker. This algorithm is based on, but not identical with, the method described in the paper below. The primary difference is that Wu and Huberman assume a priori that the clusters are of approximately the same size, and therefore use a more complex method than k-means (which is used here) for determining cluster membership based on co-occurrence data.

The algorithm proceeds as follows:

NOTE: Depending on how the co-occurrence data splits the data into clusters, the number of clusters returned by this algorithm may be less than the number of clusters requested. The number of clusters will never be more than the number requested, however.

Author:
Joshua O'Madadhain
See Also:
'Finding communities in linear time: a physics approach', Fang Wu and Bernardo Huberman, VoltageRanker, KMeansClusterer

Field Summary
protected  KMeansClusterer kmc
           
protected  int num_candidates
           
protected  RandomEngine rand
           
static String VOLTAGE_KEY
           
protected  VoltageRanker vr
           
protected  UserDatumNumberVertexValue vv
           
 
Constructor Summary
VoltageClusterer(int num_candidates, int rank_iterations, double rank_convergence, int cluster_iterations, double cluster_convergence)
          Creates an instance of a VoltageCluster with the specified parameters.
 
Method Summary
 void clear(ArchetypeGraph g)
          Clears the voltage decoration values from the vertices of g.
protected  Collection cluster_internal(ArchetypeGraph g, ArchetypeVertex origin, int num_clusters)
          Does the work of getCommunity and cluster.
 Collection cluster(ArchetypeGraph g, int num_clusters)
          Clusters the vertices of g into num_clusters clusters, based on their connectivity.
 Collection getCommunity(ArchetypeVertex v)
          Returns a community (cluster) centered around v.
protected  Map getObjectCounts(Collection candidates, Object seed)
           
protected  Object getRandomElement(Collection c)
           
protected  Object[] getSeedCandidates(Collection candidates)
          Returns an array of cluster seeds, ranked in decreasing order of number of appearances in the specified collection of candidate clusters.
protected  void setRandomSeed(int random_seed)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

VOLTAGE_KEY

public static final String VOLTAGE_KEY
See Also:
Constant Field Values

num_candidates

protected int num_candidates

kmc

protected KMeansClusterer kmc

vv

protected UserDatumNumberVertexValue vv

vr

protected VoltageRanker vr

rand

protected RandomEngine rand
Constructor Detail

VoltageClusterer

public VoltageClusterer(int num_candidates,
                        int rank_iterations,
                        double rank_convergence,
                        int cluster_iterations,
                        double cluster_convergence)
Creates an instance of a VoltageCluster with the specified parameters. These are mostly parameters that are passed directly to VoltageRanker and KMeansClusterer.

Parameters:
num_candidates - the number of candidate clusters to create
rank_iterations - the number of iterations to run VoltageRanker
cluster_iterations - the number of iterations to run KMeansClusterer
cluster_convergence - the convergence value for KMeansClusterer
Method Detail

setRandomSeed

protected void setRandomSeed(int random_seed)

getCommunity

public Collection getCommunity(ArchetypeVertex v)
Returns a community (cluster) centered around v.

Parameters:
v - the vertex whose community we wish to discover

cluster

public Collection cluster(ArchetypeGraph g,
                          int num_clusters)
Clusters the vertices of g into num_clusters clusters, based on their connectivity.

Parameters:
g - the graph whose vertices are to be clustered
num_clusters - the number of clusters to identify

clear

public void clear(ArchetypeGraph g)
Clears the voltage decoration values from the vertices of g.


cluster_internal

protected Collection cluster_internal(ArchetypeGraph g,
                                      ArchetypeVertex origin,
                                      int num_clusters)
Does the work of getCommunity and cluster.

Parameters:
g - the graph whose vertices we're clustering
origin - the center (if one exists) of the graph to cluster
num_clusters -

getRandomElement

protected Object getRandomElement(Collection c)

getSeedCandidates

protected Object[] getSeedCandidates(Collection candidates)
Returns an array of cluster seeds, ranked in decreasing order of number of appearances in the specified collection of candidate clusters.

Parameters:
candidates -

getObjectCounts

protected Map getObjectCounts(Collection candidates,
                              Object seed)