# Markov Cluster Algorithm

### Description

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

### Usage

1 2 |

### Arguments

`x` |
an adjacency or (n x n) matrix |

`addLoops` |
logical; if |

`expansion` |
numeric value > 1 for the expansion parameter |

`inflation` |
numeric value > 0 for the inflation power coefficient |

`allow1` |
logical; if |

`max.iter` |
an interger, the maximum number of iterations for the MCL |

`ESM` |
logical whether the equilibrium state matrix should be returned (default is |

### 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).

### Value

`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 |

### 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.

### Author(s)

Martin L. Jäger

### 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

### Examples

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | ```
### 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)
``` |