nl.cwts.networkanalysis

Class LocalMergingAlgorithm

java.lang.Object

nl.cwts.networkanalysis.CPMClusteringAlgorithm

nl.cwts.networkanalysis.LocalMergingAlgorithm

All Implemented Interfaces:

java.lang.Cloneable, ClusteringAlgorithm, QualityClusteringAlgorithm

public class LocalMergingAlgorithm
extends CPMClusteringAlgorithm

Local merging algorithm.

The local merging algorithm starts from a singleton partition. It performs a single iteration over the nodes in a network. Each node belonging to a singleton cluster is considered for merging with another cluster. This cluster is chosen randomly from all clusters that do not result in a decrease in the quality function. The larger the increase in the quality function, the more likely a cluster is to be chosen. The strength of this effect is determined by the randomness parameter. The higher the value of the randomness parameter, the stronger the randomness in the choice of a cluster. The lower the value of the randomness parameter, the more likely the cluster resulting in the largest increase in the quality function is to be chosen. A node is merged with a cluster only if both are sufficiently well connected to the rest of the network.

The local merging algorithm is used in the cluster refinement phase of the LeidenAlgorithm.

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_RANDOMNESS Default randomness parameter.
protected java.util.Random	random Random number generator.
protected double	randomness Randomness parameter.

Fields inherited from class nl.cwts.networkanalysis.CPMClusteringAlgorithm

DEFAULT_RESOLUTION, resolution

Constructor Summary

Constructors

Constructor and Description
LocalMergingAlgorithm() Constructs a local merging algorithm.
LocalMergingAlgorithm(double resolution, double randomness, java.util.Random random) Constructs a local merging algorithm for a specified resolution parameter and randomness parameter.
LocalMergingAlgorithm(java.util.Random random) Constructs a local merging algorithm.

Method Summary

Modifier and Type	Method and Description
Clustering	findClustering(Network network) Finds a clustering of the nodes in a network using the local merging algorithm.
double	getRandomness() Returns the randomness parameter.
void	setRandomness(double randomness) Sets the randomness parameter.

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

DEFAULT_RANDOMNESS

public static final double DEFAULT_RANDOMNESS

Default randomness parameter.

See Also:

Constant Field Values

randomness

protected double randomness

Randomness parameter.

random

protected java.util.Random random

Random number generator.

Constructor Detail

LocalMergingAlgorithm

public LocalMergingAlgorithm()

Constructs a local merging algorithm.

LocalMergingAlgorithm

public LocalMergingAlgorithm(java.util.Random random)

Constructs a local merging algorithm.

Parameters:

random - Random number generator

LocalMergingAlgorithm

public LocalMergingAlgorithm(double resolution,
                             double randomness,
                             java.util.Random random)

Constructs a local merging algorithm for a specified resolution parameter and randomness parameter.

Parameters:

resolution - Resolution parameter

randomness - Randomness parameter

random - Random number generator

Method Detail

getRandomness

public double getRandomness()

Returns the randomness parameter.

Returns:

Randomness

setRandomness

public void setRandomness(double randomness)

Sets the randomness parameter.

Parameters:

randomness - Randomness

findClustering

public Clustering findClustering(Network network)

Finds a clustering of the nodes in a network using the local merging algorithm.

The local merging algorithm starts from a singleton partition. It performs a single iteration over the nodes in a network. Each node belonging to a singleton cluster is considered for merging with another cluster. This cluster is chosen randomly from all clusters that do not result in a decrease in the quality function. The larger the increase in the quality function, the more likely a cluster is to be chosen. The strength of this effect is determined by the randomness parameter. The higher the value of the randomness parameter, the stronger the randomness in the choice of a cluster. The lower the value of the randomness parameter, the more likely the cluster resulting in the largest increase in the quality function is to be chosen. A node is merged with a cluster only if both are sufficiently well connected to the rest of the network.

Parameters:

network - Network

Returns:

Clustering