nl.cwts.networkanalysis

Class CPMClusteringAlgorithm

java.lang.Object

nl.cwts.networkanalysis.CPMClusteringAlgorithm

All Implemented Interfaces:

java.lang.Cloneable, ClusteringAlgorithm, QualityClusteringAlgorithm

Direct Known Subclasses:

IncrementalCPMClusteringAlgorithm, LocalMergingAlgorithm

public abstract class CPMClusteringAlgorithm
extends java.lang.Object
implements java.lang.Cloneable, QualityClusteringAlgorithm

Abstract base class for clustering algorithms that use the CPM quality function.

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_RESOLUTION Default resolution parameter.
protected double	resolution Resolution parameter.

Constructor Summary

Constructors

Constructor and Description
CPMClusteringAlgorithm() Constructs a CPM clustering algorithm.
CPMClusteringAlgorithm(double resolution) Constructs a CPM clustering algorithm with a specified resolution parameter.

Method Summary

Modifier and Type	Method and Description
double	calcQuality(Network network, Clustering clustering) Calculates the quality of a clustering using the CPM quality function.
CPMClusteringAlgorithm	clone() Clones the algorithm.
double	getResolution() Returns the resolution parameter.
int	removeCluster(Network network, Clustering clustering, int cluster) Removes a cluster from a clustering by merging the cluster with another cluster.
boolean	removeSmallClustersBasedOnNNodes(Network network, Clustering clustering, int minNNodesPerCluster) Removes small clusters from a clustering.
boolean	removeSmallClustersBasedOnWeight(Network network, Clustering clustering, double minClusterWeight) Removes small clusters from a clustering.
void	setResolution(double resolution) Sets the resolution parameter.

Methods inherited from class java.lang.Object

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

Methods inherited from interface nl.cwts.networkanalysis.ClusteringAlgorithm

findClustering

Field Detail

DEFAULT_RESOLUTION

public static final double DEFAULT_RESOLUTION

Default resolution parameter.

See Also:

Constant Field Values

resolution

protected double resolution

Resolution parameter.

Constructor Detail

CPMClusteringAlgorithm

public CPMClusteringAlgorithm()

Constructs a CPM clustering algorithm.

CPMClusteringAlgorithm

public CPMClusteringAlgorithm(double resolution)

Constructs a CPM clustering algorithm with a specified resolution parameter.

Parameters:

resolution - Resolution parameter

Method Detail

clone

public CPMClusteringAlgorithm clone()

Clones the algorithm.

Overrides:

clone in class java.lang.Object

Returns:

Cloned algorithm

getResolution

public double getResolution()

Returns the resolution parameter.

Returns:

Resolution parameter

setResolution

public void setResolution(double resolution)

Sets the resolution parameter.

Parameters:

resolution - Resolution parameter

calcQuality

public double calcQuality(Network network,
                          Clustering clustering)

Calculates the quality of a clustering using the CPM quality function.

The CPM quality function is given by

1 / (2 * m) * sum(d(c[i], c[j]) * (a[i][j] - resolution * n[i] * n[j])),

where a[i][j] is the weight of the edge between nodes i and j, n[i] is the weight of node i, m is the total edge weight, and resolution is the resolution parameter. The function d(c[i], c[j]) equals 1 if nodes i and j belong to the same cluster and 0 otherwise. The sum is taken over all pairs of nodes i and j.

Modularity can be expressed in terms of CPM by setting n[i] equal to the total weight of the edges between node i and its neighbors and by rescaling the resolution parameter by 2 * m.

Specified by:

calcQuality in interface QualityClusteringAlgorithm

Parameters:

network - Network

clustering - Clustering

Returns:

Quality of the clustering

removeCluster

public int removeCluster(Network network,
                         Clustering clustering,
                         int cluster)

Removes a cluster from a clustering by merging the cluster with another cluster. If a cluster has no connections with other clusters, it cannot be removed.

Parameters:

network - Network

clustering - Clustering

cluster - Cluster to be removed

Returns:

Cluster with which the cluster to be removed has been merged, or -1 if the cluster could not be removed

removeSmallClustersBasedOnNNodes

public boolean removeSmallClustersBasedOnNNodes(Network network,
                                                Clustering clustering,
                                                int minNNodesPerCluster)

Removes small clusters from a clustering. Clusters are merged until each cluster contains at least a certain minimum number of nodes.

Parameters:

network - Network

clustering - Clustering

minNNodesPerCluster - Minimum number of nodes per cluster

Returns:

Boolean indicating whether any clusters have been removed

removeSmallClustersBasedOnWeight

public boolean removeSmallClustersBasedOnWeight(Network network,
                                                Clustering clustering,
                                                double minClusterWeight)

Removes small clusters from a clustering. Clusters are merged until each cluster has at least a certain minimum total node weight.

The total node weight of a cluster equals the sum of the weights of the nodes belonging to the cluster.

Parameters:

network - Network

clustering - Clustering

minClusterWeight - Minimum total node weight of a cluster

Returns:

Boolean indicating whether any clusters have been removed