public class VoltageClusterer
extends java.lang.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.
VoltageRanker
,
KMeansClusterer
Modifier and Type | Field and Description |
---|---|
protected KMeansClusterer |
kmc |
protected int |
num_candidates |
protected cern.jet.random.engine.RandomEngine |
rand |
static java.lang.String |
VOLTAGE_KEY |
protected VoltageRanker |
vr |
protected UserDatumNumberVertexValue |
vv |
Constructor and Description |
---|
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.
|
Modifier and Type | Method and Description |
---|---|
void |
clear(ArchetypeGraph g)
Clears the voltage decoration values from the vertices of
g . |
protected java.util.Collection |
cluster_internal(ArchetypeGraph g,
ArchetypeVertex origin,
int num_clusters)
Does the work of
getCommunity and cluster . |
java.util.Collection |
cluster(ArchetypeGraph g,
int num_clusters)
Clusters the vertices of
g into
num_clusters clusters, based on their connectivity. |
java.util.Collection |
getCommunity(ArchetypeVertex v)
Returns a community (cluster) centered around
v . |
protected java.util.Map |
getObjectCounts(java.util.Collection candidates,
java.lang.Object seed) |
protected java.lang.Object |
getRandomElement(java.util.Collection c) |
protected java.lang.Object[] |
getSeedCandidates(java.util.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) |
public static final java.lang.String VOLTAGE_KEY
protected int num_candidates
protected KMeansClusterer kmc
protected UserDatumNumberVertexValue vv
protected VoltageRanker vr
protected cern.jet.random.engine.RandomEngine rand
public VoltageClusterer(int num_candidates, int rank_iterations, double rank_convergence, int cluster_iterations, double cluster_convergence)
num_candidates
- the number of candidate clusters to createrank_iterations
- the number of iterations to run VoltageRankercluster_iterations
- the number of iterations to run KMeansClusterercluster_convergence
- the convergence value for KMeansClustererprotected void setRandomSeed(int random_seed)
public java.util.Collection getCommunity(ArchetypeVertex v)
v
.v
- the vertex whose community we wish to discoverpublic java.util.Collection cluster(ArchetypeGraph g, int num_clusters)
g
into
num_clusters
clusters, based on their connectivity.g
- the graph whose vertices are to be clusterednum_clusters
- the number of clusters to identifypublic void clear(ArchetypeGraph g)
g
.protected java.util.Collection cluster_internal(ArchetypeGraph g, ArchetypeVertex origin, int num_clusters)
getCommunity
and cluster
.g
- the graph whose vertices we're clusteringorigin
- the center (if one exists) of the graph to clusternum_clusters
- protected java.lang.Object getRandomElement(java.util.Collection c)
protected java.lang.Object[] getSeedCandidates(java.util.Collection candidates)
candidates
- protected java.util.Map getObjectCounts(java.util.Collection candidates, java.lang.Object seed)