edu.ucla.sspace.clustering

Class LinkClustering

java.lang.Object

edu.ucla.sspace.clustering.LinkClustering

All Implemented Interfaces:

Clustering, Serializable

public class LinkClustering
extends Object
implements Clustering, Serializable

An implmentation of the link clustering described in Ahn, Bagrow, and Lehman (2010). This algorithm is a multi-class clustering algorithm that instead of clustering the nodes in a graph according to their similarity with eacher, clusters the links connecting the nodes to reveal communities that connect the nodes. For full information on the algorithm see,

• Yong-Yeol Ahn, James P. Bagrow and Sune Lehmann. Link communities reveal multiscale complexity in networks. Nature 466, 761–764 (05 August 2010). Available online here.

This algorithm automatically determines the number of clusters based on a partition density function. Accordingly, the clustering methods take no parameters. Calling the cluster method with a fixed number of elements will still cluster the rows, but will ignore the requester number of clusters.

Note that this class is not thread-safe. Each call to clustering will cache local information about the clustering result to facilitate the getSolution(int) and getSolutionDensity(int) functions. This class provides one configurable property:

Property: "edu.ucla.sspace.clustering.LinkClustering.keepSimilarityMatrixInMemory"
Default: true

If true, this property specifies the edge similarity matrix used by HierarchicalAgglomerativeClustering should be computed once and then kept in memory, which is the default behavior. If false, this causes the similarity of two edges to be recomputed on-the-fly whenever it is requester. By computing these values on-the-fly, the performance will be slowed down, depending on the complexity of the edge similarity function. However, this on-the-fly setting allows for clustering large graphs whose edge similarity matrix would not regularly fit into memory. It is advised that users not tune this parameter unless it is known that the similarity matrix will not fit in memory.

Author:

David Jurgens

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	LinkClustering.Edge A utility data structure for representing a directed edge between two ordinally labeled nodes.

Field Summary

Fields

Modifier and Type	Field and Description
static String	KEEP_SIMILARITY_MATRIX_IN_MEMORY_PROPERTY The property to specify if the edge similarity matrix should be kept in memory during clustering, or if its values should be computed on the fly.
static String	PROPERTY_PREFIX A prefix for specifying properties.

Constructor Summary

Constructors

Constructor and Description
LinkClustering() Instantiates a new LinkClustering instance.

Method Summary

Methods

Modifier and Type	Method and Description
Assignments	cluster(Matrix matrix, int numClusters, Properties props) Ignores the specified number of clusters and returns the clustering solution according to the partition density.
Assignments	cluster(Matrix matrix, Properties props) Clusters the set of rows in the given Matrix without a specified number of clusters (optional operation).
protected double	getEdgeSimilarity(SparseMatrix sm, LinkClustering.Edge e1, LinkClustering.Edge e2) Computes the similarity of the two edges as the Jaccard index of the neighbors of two impost nodes.
Assignments	getSolution(int solutionNum) Returns the clustering solution after the specified number of merge steps.
double	getSolutionDensity(int solutionNum) Returns the partition density of the clustering solution.
int	numberOfSolutions() Returns the number of clustering solutions found by this instances for the prior clustering run.

Methods inherited from class java.lang.Object

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

Field Detail

PROPERTY_PREFIX

public static final String PROPERTY_PREFIX

A prefix for specifying properties.

See Also:

Constant Field Values

KEEP_SIMILARITY_MATRIX_IN_MEMORY_PROPERTY

public static final String KEEP_SIMILARITY_MATRIX_IN_MEMORY_PROPERTY

The property to specify if the edge similarity matrix should be kept in memory during clustering, or if its values should be computed on the fly.

See Also:

Constant Field Values

Constructor Detail

LinkClustering

public LinkClustering()

Instantiates a new LinkClustering instance.

Method Detail

cluster

public Assignments cluster(Matrix matrix,
                  int numClusters,
                  Properties props)

Ignores the specified number of clusters and returns the clustering solution according to the partition density.

Specified by:

cluster in interface Clustering

Parameters:

numClusters - this parameter is ignored.

matrix - the Matrix whose row data points are to be clustered

props - the properties to use for any parameters each clustering algorithm may need

Returns:

an array of Assignment instances that indicate zero or more clusters to which each row belongs.

Throws:

IllegalArgumentException - if matrix is not square, or is not an instance of SparseMatrix

cluster

public Assignments cluster(Matrix matrix,
                  Properties props)

Clusters the set of rows in the given Matrix without a specified number of clusters (optional operation). The set of cluster assignments are returned for each row in the matrix.

Specified by:

cluster in interface Clustering

Parameters:

matrix - the Matrix whose row data points are to be clustered

props - the properties to use for any parameters each clustering algorithm may need

Returns:

an array of Assignment instances that indicate zero or more clusters to which each row belongs.

Throws:

IllegalArgumentException - if matrix is not square, or is not an instance of SparseMatrix

getEdgeSimilarity

protected double getEdgeSimilarity(SparseMatrix sm,
                       LinkClustering.Edge e1,
                       LinkClustering.Edge e2)

Computes the similarity of the two edges as the Jaccard index of the neighbors of two impost nodes. The impost nodes are the two nodes the edges do not have in common. Subclasses may override this method to define a new method for computing edge similarity.

Implementation Note: Subclasses that wish to override this behavior should be aware that this method is likely to be called by multiple threads and therefor should make provisions to be thread safe. In addition, this method may be called more than once per edge pair if the similarity matrix is being computed on-the-fly.

Parameters:

sm - a matrix containing the connections between edges. A non-zero value in location (i,j) indicates a node i is connected to node j by an edge.

e1 - an edge to be compared with e2

e2 - an edge to be compared with e1

Returns:

the similarity of the edges.a

getSolutionDensity

public double getSolutionDensity(int solutionNum)

Returns the partition density of the clustering solution.

getSolution

public Assignments getSolution(int solutionNum)

Returns the clustering solution after the specified number of merge steps.

Parameters:

solutionNum - the number of merge steps to take prior to returning the clustering solution.

Throws:

IllegalArgumentException - if solutionNum is less than 0 or is greater than or equal to numberOfSolutions().

IllegalStateException - if this instance has not yet finished a clustering solution.

numberOfSolutions

public int numberOfSolutions()

Returns the number of clustering solutions found by this instances for the prior clustering run.