cluster_markov {GeneTonic} | R Documentation

## Markov Clustering (MCL) for community detection

### Description

This function implements the Markov Clustering (MCL) algorithm for finding community structure, in an analogous way to other existing algorithms in `igraph`.

### Usage

    cluster_markov(
      g,
      add_self_loops = TRUE,
      loop_value = 1,
      mcl_expansion = 2,
      mcl_inflation = 2,
      allow_singletons = TRUE,
      max_iter = 100,
      return_node_names = TRUE,
      return_esm = FALSE
    )

### Arguments

`g` | The input graph object
`add_self_loops` | Logical, whether to add self-loops to the matrix by setting the diagonal to `loop_value`
`loop_value` | Numeric, the value to use for self-loops
`mcl_expansion` | Numeric, cluster expansion factor for the Markov clustering iteration - defaults to 2
`mcl_inflation` | Numeric, cluster inflation factor for the Markov clustering iteration - defaults to 2
`allow_singletons` | Logical; if `TRUE`, single isolated vertices are allowed to form their own cluster. If set to `FALSE`, all clusters of size = 1 are grouped in one cluster (to be interpreted as background noise).
`max_iter` | Numeric value for the maximum number of iterations for the Markov clustering
`return_node_names` | Logical, if the graph is named and set to `TRUE`, returns the node names.
`return_esm` | Logical, controlling whether the equilibrium state matrix should be returned

### Details

This implementation has been driven by the nice explanations provided in

- https://sites.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf

- https://medium.com/analytics-vidhya/demystifying-markov-clustering-aeb6cdabbfc7

- https://github.com/GuyAllard/markov_clustering (python implementation)

More info on the MCL: https://micans.org/mcl/index.html, and https://micans.org/mcl/sec_description1.html

### Value

This function returns a `communities` object, containing the numbers of the assigned membership (in the slot `membership`). Please see the `igraph::communities()` manual page for additional details

### References

van Dongen, S.M., Graph clustering by flow simulation (2000) PhD thesis, Utrecht University Repository - https://dspace.library.uu.nl/handle/1874/848

Enright AJ, van Dongen SM, Ouzounis CA, An efficient algorithm for large-scale detection of protein families (2002) Nucleic Acids Research, Volume 30, Issue 7, 1 April 2002, Pages 1575–1584, https://doi.org/10.1093/nar/30.7.1575

### Examples

    library("igraph")
    g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
    g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
    cluster_markov(g)
    V(g)$color <- cluster_markov(g)$membership
    plot(g)

[Package GeneTonic version 1.6.4 Index]