nl.cwts.networkanalysis

Class FastLocalMovingAlgorithm

java.lang.Object

nl.cwts.networkanalysis.CPMClusteringAlgorithm

nl.cwts.networkanalysis.IncrementalCPMClusteringAlgorithm

nl.cwts.networkanalysis.IterativeCPMClusteringAlgorithm

nl.cwts.networkanalysis.FastLocalMovingAlgorithm

All Implemented Interfaces:

java.lang.Cloneable, ClusteringAlgorithm, IncrementalClusteringAlgorithm, QualityClusteringAlgorithm

public class FastLocalMovingAlgorithm
extends IterativeCPMClusteringAlgorithm

Fast local moving algorithm.

The fast local moving algorithm first adds all nodes in a network to a queue. It then removes a node from the queue. The node is moved to the cluster that results in the largest increase in the quality function. If the current cluster assignment of the node is already optimal, the node is not moved. If the node is moved to a different cluster, the neighbors of the node that do not belong to the node's new cluster and that are not yet in the queue are added to the queue. The algorithm continues removing nodes from the queue until the queue is empty.

The fast local moving algorithm provides a fast variant of the StandardLocalMovingAlgorithm.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Random	random Random number generator.

Fields inherited from class nl.cwts.networkanalysis.IterativeCPMClusteringAlgorithm

DEFAULT_N_ITERATIONS, nIterations

Fields inherited from class nl.cwts.networkanalysis.CPMClusteringAlgorithm

DEFAULT_RESOLUTION, resolution

Constructor Summary

Constructors

Constructor and Description
FastLocalMovingAlgorithm() Constructs a fast local moving algorithm.
FastLocalMovingAlgorithm(double resolution, int nIterations, java.util.Random random) Constructs a fast local moving algorithm for a specified resolution parameter and number of iterations.
FastLocalMovingAlgorithm(java.util.Random random) Constructs a fast local moving algorithm.

Method Summary

Modifier and Type	Method and Description
protected boolean	improveClusteringOneIteration(Network network, Clustering clustering) Improves a clustering by performing one iteration of the fast local moving algorithm.

Methods inherited from class nl.cwts.networkanalysis.IterativeCPMClusteringAlgorithm

getNIterations, improveClustering, setNIterations

Methods inherited from class nl.cwts.networkanalysis.IncrementalCPMClusteringAlgorithm

findClustering

Methods inherited from class nl.cwts.networkanalysis.CPMClusteringAlgorithm

calcQuality, clone, getResolution, removeCluster, removeSmallClustersBasedOnNNodes, removeSmallClustersBasedOnWeight, setResolution

Methods inherited from class java.lang.Object

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

Field Detail

random

protected java.util.Random random

Random number generator.

Constructor Detail

FastLocalMovingAlgorithm

public FastLocalMovingAlgorithm()

Constructs a fast local moving algorithm.

FastLocalMovingAlgorithm

public FastLocalMovingAlgorithm(java.util.Random random)

Constructs a fast local moving algorithm.

Parameters:

random - Random number generator

FastLocalMovingAlgorithm

public FastLocalMovingAlgorithm(double resolution,
                                int nIterations,
                                java.util.Random random)

Constructs a fast local moving algorithm for a specified resolution parameter and number of iterations.

Parameters:

resolution - Resolution parameter

nIterations - Number of iterations

random - Random number generator

Method Detail

improveClusteringOneIteration

protected boolean improveClusteringOneIteration(Network network,
                                                Clustering clustering)

Improves a clustering by performing one iteration of the fast local moving algorithm.

The fast local moving algorithm first adds all nodes in a network to a queue. It then removes a node from the queue. The node is moved to the cluster that results in the largest increase in the quality function. If the current cluster assignment of the node is already optimal, the node is not moved. If the node is moved to a different cluster, the neighbors of the node that do not belong to the node's new cluster and that are not yet in the queue are added to the queue. The algorithm continues removing nodes from the queue until the queue is empty.

Specified by:

improveClusteringOneIteration in class IterativeCPMClusteringAlgorithm

Parameters:

network - Network

clustering - Clustering

Returns:

Boolean indicating whether the clustering has been improved