MCL (Markov Cluster Algorithm)

Markov Cluster Algorithm works by simulating a stochastic (Markov) flow in a weighted graph, where each node is a data point, and the edge weights are defined by the adjacency matrix. ... When the algorithm converges, it produces the new edge weights that define the new connected components of the graph (i.e. the clusters).

Clustering.mcl — Function.

mcl(adj::AbstractMatrix; [kwargs...])

Perform MCL (Markov Cluster Algorithm) clustering using $n×n$ adjacency (points similarity) matrix adj.

Returns MCLResult object.

Algorithm Options

add_loops::Bool (enabled by default): whether the edges of weight 1.0 from the node to itself should be appended to the graph
expansion::Number (defaults to 2): MCL expansion constant
inflation::Number (defaults to 2): MCL inflation constant
save_final_matrix::Bool (disabled by default): whether to save the final equilibrium state in the mcl_adj field of the result; could provide useful diagnostic if the method doesn't converge
prune_tol::Number: pruning threshold
display::Symbol (defaults to :none): :none for no output or :verbose for diagnostic messages
max_iter, tol: see common options

References

Stijn van Dongen, "Graph clustering by flow simulation", 2001

Original MCL implementation.

source

Clustering.MCLResult — Type.

The output of mcl function.

Fields

mcl_adj::AbstractMatrix: the final MCL adjacency matrix (equilibrium state matrix if the algorithm converged), empty if save_final_matrix option is disabled
assignments::Vector{Int}: indices of the points clusters. assignments[i] is the index of the cluster for the $i$-th point ($0$ if unassigned)
counts::Vector{Int}: the $k$-length vector of cluster sizes
nunassigned::Int: the number of standalone points not assigned to any cluster
iterations::Int: the number of elapsed iterations
rel_Δ::Float64: the final relative Δ
converged::Bool: whether the method converged

source