mcl: Markov Cluster Algorithm
In MCL: Markov Cluster Algorithm

Description Usage Arguments Details Value Note Author(s) References Examples

Perform the Markov Cluster Algorithm on an adjacency or (n x n) matrix.

1 2	mcl(x, addLoops = NULL, expansion = 2, inflation = 2, allow1 = FALSE, max.iter = 100, ESM = FALSE)

`x`	an adjacency or (n x n) matrix
`addLoops`	logical; if `TRUE`, self-loops with weight 1 are added to each vertex of `x` (see Details).
`expansion`	numeric value > 1 for the expansion parameter
`inflation`	numeric value > 0 for the inflation power coefficient
`allow1`	logical; if `TRUE`, vertices are allowed to form their own cluster. If `FALSE`, clusters of size 1 are interpreted as background noise and grouped in one cluster.
`max.iter`	an interger, the maximum number of iterations for the MCL
`ESM`	logical whether the equilibrium state matrix should be returned (default is `FALSE`)

The adjacency or correlation matrix x is clustered by the Markov Cluster algorithm. The algorihtm is controlled by the expansion parameter and the inflation power coefficient (for further details, see reference below). Adding self-loops is necessary, if either x contains at least one vertex of degree 0 or x represents a directed, non-bipartite graph adjacency matrix (i.e. the upper or lower matrix of x contains only zeros).

`K`	the number of clusters
`n.iterations`	the number of iterations
`Cluster`	a vector of integers indicating the cluster to which each vertex is allocated
`Equilibrium.state.matrix`	a matrix; rows contain clusters

If an error occurs, mcl returns the number of the last iteration. If an error occurs at iteration 1, there might be a problem with the matrix x. If an error occurs at iteration max.iter, x could not be transformed into an equilibrium state matrix.

Martin L. Jäger

van Dongen, S.M. (2000) Graph Clustering by Flow Simulation. Ph.D. thesis, Universtiy of Utrecht. Utrecht University Repository: http://dspace.library.uu.nl/handle/1874/848

### Generate adjacency matrix of undirected graph
adjacency <- matrix(c(0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,1,1,
                      0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,
                      0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,
                      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), 
                      byrow=TRUE, nrow=9)

### Plot graph (requires package igraph) 
# library(igraph)
# gu <- graph.adjacency( adjacency, mode="undirected" )
# plot( gu )

### Run MCL
mcl(x = adjacency, addLoops=TRUE, ESM = TRUE)

### Allow clusters of size 1
mcl(x = adjacency, addLoops = TRUE, allow1 = TRUE)

### Error: Small inflation coefficient prevents that an 
###        equilibrium state matrix is reached within 100 iterations
mcl(x = adjacency, addLoops=TRUE, inflation = 1.01, max.iter = 100)


### Generate adjacency matrix of directed graph
dgr <- matrix(0,nrow = 10,ncol = 10)
dgr[2:3,1] <- 1; dgr[3:4,2] <- 1; dgr[5:6,4] <- 1
dgr[6:7,5] <- 1; dgr[8:9,7] <- 1; dgr[10,8:9] <- 1

### Plot graph (requires package igraph) 
# library( igraph )
# gd <- graph.adjacency( dgr )
# plot( gd )

### Directed graphs require self-loops!
mcl(x = dgr, addLoops = TRUE)