Package org.nlpub.watset.graph

Class MarkovClustering<V,E>

java.lang.Object

org.nlpub.watset.graph.MarkovClustering<V,E>

Type Parameters:

V - the type of nodes in the graph

E - the type of edges in the graph

All Implemented Interfaces:

org.jgrapht.alg.interfaces.ClusteringAlgorithm<V>

public class MarkovClustering<V,E>
extends Object
implements org.jgrapht.alg.interfaces.ClusteringAlgorithm<V>

Naïve implementation of the Markov Clustering (MCL) algorithm.

This implementation assumes processing of relatively small graphs due to the lack of pruning optimizations.

See Also:

• van Dongen (2000)
• van Dongen (2008)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	MarkovClustering.Builder<V,E>	Builder for MarkovClustering.
protected static class	MarkovClustering.Implementation<V,E>	Actual implementation of Markov Clustering.

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ClusteringAlgorithm

org.jgrapht.alg.interfaces.ClusteringAlgorithm.Clustering<V extends Object>, org.jgrapht.alg.interfaces.ClusteringAlgorithm.ClusteringImpl<V extends Object>

Field Summary

Fields

Modifier and Type	Field	Description
protected org.jgrapht.alg.interfaces.ClusteringAlgorithm.Clustering<V>	clustering	The cached clustering result.
protected final int	e	The expansion parameter.
protected final org.jgrapht.Graph<V,E>	graph	The graph.
protected final int	iterations	The maximal number of iterations.
protected final double	r	The inflation parameter.

Constructor Summary

Constructors

Constructor	Description
MarkovClustering(org.jgrapht.Graph<V,E> graph, int e, double r, int iterations)	Create an instance of the Markov Clustering algorithm.

Method Summary

Modifier and Type	Method	Description
static <V, E> MarkovClustering.Builder<V,E>	builder()	Create a builder.
org.jgrapht.alg.interfaces.ClusteringAlgorithm.Clustering<V>	getClustering()

Methods inherited from class java.lang.Object

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

Field Details

graph

protected final org.jgrapht.Graph<V,E> graph

The graph.

e

protected final int e

The expansion parameter.

r

protected final double r

The inflation parameter.

iterations

protected final int iterations

The maximal number of iterations.

clustering

protected org.jgrapht.alg.interfaces.ClusteringAlgorithm.Clustering<V> clustering

The cached clustering result.

Constructor Details

MarkovClustering

public MarkovClustering(org.jgrapht.Graph<V,E> graph,
 int e,
 double r,
 int iterations)

Create an instance of the Markov Clustering algorithm.

Parameters:

graph - the graph

e - the expansion parameter

r - the inflation parameter

iterations - the maximal number of iterations

Method Details

builder

public static <V,
E> MarkovClustering.Builder<V,E> builder()

Create a builder.

Type Parameters:

V - the type of nodes in the graph

E - the type of edges in the graph

Returns:

a builder

getClustering

public org.jgrapht.alg.interfaces.ClusteringAlgorithm.Clustering<V> getClustering()

Specified by:

getClustering in interface org.jgrapht.alg.interfaces.ClusteringAlgorithm<V>