Class VoltageClusterer<V,​E>


  • public class VoltageClusterer<V,​E>
    extends java.lang.Object

    Clusters vertices of a Graph based on their ranks as calculated by VoltageScorer. 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 VoltageScorer
      • 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.

    See Also:
    "'Finding communities in linear time: a physics approach', Fang Wu and Bernardo Huberman, http://www.hpl.hp.com/research/idl/papers/linear/", VoltageScorer, KMeansClusterer
    • Constructor Summary

      Constructors 
      Constructor Description
      VoltageClusterer​(Graph<V,​E> g, int num_candidates)
      Creates an instance of a VoltageCluster with the specified parameters.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void addOneCandidateCluster​(java.util.LinkedList<java.util.Set<V>> candidates, java.util.Map<V,​double[]> voltage_ranks)
      alternative to addTwoCandidateClusters(): cluster vertices by voltages into 2 clusters.
      protected void addTwoCandidateClusters​(java.util.LinkedList<java.util.Set<V>> candidates, java.util.Map<V,​double[]> voltage_ranks)
      Do k-means with three intervals and pick the smaller two clusters (presumed to be on the ends); this is closer to the Wu-Huberman method.
      java.util.Collection<java.util.Set<V>> cluster​(int num_clusters)
      Clusters the vertices of g into num_clusters clusters, based on their connectivity.
      protected java.util.Collection<java.util.Set<V>> cluster_internal​(V origin, int num_clusters)
      Does the work of getCommunity and cluster.
      java.util.Collection<java.util.Set<V>> getCommunity​(V v)  
      protected java.util.Map<V,​double[]> getObjectCounts​(java.util.Collection<java.util.Set<V>> candidates, V seed)  
      protected java.util.List<V> getSeedCandidates​(java.util.Collection<java.util.Set<V>> candidates)
      Returns a list 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

      • num_candidates

        protected int num_candidates
      • rand

        protected java.util.Random rand
    • Constructor Detail

      • VoltageClusterer

        public VoltageClusterer​(Graph<V,​E> g,
                                int num_candidates)
        Creates an instance of a VoltageCluster with the specified parameters. These are mostly parameters that are passed directly to VoltageScorer and KMeansClusterer.
        Parameters:
        g - the graph whose vertices are to be clustered
        num_candidates - the number of candidate clusters to create
    • Method Detail

      • setRandomSeed

        protected void setRandomSeed​(int random_seed)
      • getCommunity

        public java.util.Collection<java.util.Set<V>> getCommunity​(V v)
        Parameters:
        v - the vertex whose community we wish to discover
        Returns:
        a community (cluster) centered around v.
      • cluster

        public java.util.Collection<java.util.Set<V>> cluster​(int num_clusters)
        Clusters the vertices of g into num_clusters clusters, based on their connectivity.
        Parameters:
        num_clusters - the number of clusters to identify
        Returns:
        a collection of clusters (sets of vertices)
      • cluster_internal

        protected java.util.Collection<java.util.Set<V>> cluster_internal​(V origin,
                                                                          int num_clusters)
        Does the work of getCommunity and cluster.
        Parameters:
        origin - the vertex around which clustering is to be done
        num_clusters - the (maximum) number of clusters to find
        Returns:
        a collection of clusters (sets of vertices)
      • addTwoCandidateClusters

        protected void addTwoCandidateClusters​(java.util.LinkedList<java.util.Set<V>> candidates,
                                               java.util.Map<V,​double[]> voltage_ranks)
        Do k-means with three intervals and pick the smaller two clusters (presumed to be on the ends); this is closer to the Wu-Huberman method.
        Parameters:
        candidates - the list of clusters to populate
        voltage_ranks - the voltage values for each vertex
      • addOneCandidateCluster

        protected void addOneCandidateCluster​(java.util.LinkedList<java.util.Set<V>> candidates,
                                              java.util.Map<V,​double[]> voltage_ranks)
        alternative to addTwoCandidateClusters(): cluster vertices by voltages into 2 clusters. We only consider the smaller of the two clusters returned by k-means to be a 'true' cluster candidate; the other is a garbage cluster.
        Parameters:
        candidates - the list of clusters to populate
        voltage_ranks - the voltage values for each vertex
      • getSeedCandidates

        protected java.util.List<V> getSeedCandidates​(java.util.Collection<java.util.Set<V>> candidates)
        Returns a list of cluster seeds, ranked in decreasing order of number of appearances in the specified collection of candidate clusters.
        Parameters:
        candidates - the set of candidate clusters
        Returns:
        a set of cluster seeds
      • getObjectCounts

        protected java.util.Map<V,​double[]> getObjectCounts​(java.util.Collection<java.util.Set<V>> candidates,
                                                                  V seed)