CRAN status CRAN downloads

leidenAlg

Implements the Leiden algorithm via an R interface

Summary

The Leiden algorithm is an iterative community detection algorithm on networks—the algorithm is designed to converge to a partition in which all subsets of all communities are locally optimally assigned, yielding communities guaranteed to be connected.

The algorithm was written to improve upon defects of the Louvain algorithm. Consequently, the Leiden algorithm is faster, scales well, and can be run on graphs of millions of nodes (as long as they can fit in memory).

The basic steps are: * (1) local moving of nodes to quickly find partitions * (2) refinement of partitions * (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. Steps are iterated until convergence.

For details on the algorithm, see “From Louvain to Leiden: guaranteeing well-connected communities” Traag, Waltman, van Eck. Sci Rep 9, 5233 (2019). https://doi.org/10.1038/s41598-019-41695-z

For the original implementation in C++ with python bindings, see: https://github.com/vtraag/leidenalg

Installation

To install the stable version from CRAN, use:

install.packages('leidenAlg')

To install the latest version, use:

install.packages('devtools')
devtools::install_github('kharchenkolab/leidenAlg', build_vignettes = TRUE)

Note that this package depends on igraph, which requires various libraries to install correctly e.g. libxml2. Please see the installation instructions at that page for more details, along with the README here.

Debian-based users of Linux can install the required packages via:

sudo apt-get update
sudo apt-get install libxml2-dev libgmp-dev libglpk-dev

For users of Red Hat distributions, use the following command to install the required packages:

sudo yum update
sudo yum install libxml2-devel gmp-devel glpk-devel

For Mac OS, the commands with the Homebrew package manager are as follows:

brew update
brew install libxml2 glpk gmp

Note: For Mac OS users, there is a guide for troubleshooting here if issues arise.

Functions

Citation

If you find leidenAlg useful for your publication, please cite:

Peter Kharchenko, Viktor Petukhov and Evan Biederstedt (2021).
leidenAlg: Implements the Leiden Algorithm via an R Interface. R
package version 1.0.2. https://github.com/kharchenkolab/leidenAlg