Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

    java.lang.Object
      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:

first, generate a set of candidate clusters as follows:

pick (widely separated) vertex pair, run VoltageRanker
group the vertices in two clusters according to their voltages
store resulting candidate clusters

second, generate k-1 clusters as follows:

pick a vertex v as a cluster 'seed'
(Wu/Huberman: most frequent vertex in candidate clusters)
calculate co-occurrence over all candidate clusters of v with each other vertex
separate co-occurrence counts into high/low; high vertices constitute a cluster
remove v's vertices from candidate clusters; continue

finally, remaining unassigned vertices are assigned to the kth ("garbage") cluster.

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)

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD