cluster_markov: Markov Clustering (MCL) for community detection

View source: R/gs_cluster.R

cluster_markovR 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)

federicomarini/GeneTonic documentation built on March 27, 2024, 4:19 p.m.