# Markov Cluster Algorithm Perform the Markov Cluster Algorithm on an adjacency or (n x n) matrix. UTF-8 ```r mcl(x, addLoops = NULL, expansion = 2, inflation = 2, allow1 = FALSE, max.iter = 100, ESM = FALSE) ``` ## Arguments - `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`) ## Details 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). ## Returns - **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 ## References 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 ## Author(s) Martin L. Jäger ## Note 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. ## Examples ```r ### 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) ```

mcl function