Leiden (алгоритм Лейдена) · Leiden algorithm
Алгоритм выделения сообществ (кластеров) в графах, который исправляет недостатки Louvain и гарантирует связность найденных кластеров.
Подробно
Leiden — итеративный алгоритм кластеризации графов, предложенный В. Траагом, Л. Валтманом и Н. ван Экком (2019) как развитие алгоритма Louvain. Он выполняет три фазы: локальную оптимизацию модулярности (или функции качества CPM/RB), укрупнение графа и этап уточнения (refinement), на котором кластеры дробятся на хорошо связные подмножества. За счёт фазы refinement алгоритм гарантирует, что каждый найденный кластер внутренне связен, и работает быстрее Louvain, что важно на графах с миллионами рёбер. Основные области применения — анализ социальных и биологических сетей, а в биоинформатике — кластеризация клеток в single-cell RNA-seq (Scanpy, Seurat) и построение карт типов клеток. Реализации доступны в библиотеках leidenalg/igraph (Python, R) и встроены в пайплайны Scanpy.
Примеры употребления
- import leidenalg, igraph; part = leidenalg.find_partition(g, leidenalg.RBConfigurationVertexPartition, resolution_parameter=1.0)
- sc.tl.leiden(adata, resolution=1.0, key_added="leiden") # кластеризация клеток в Scanpy
- На 2 млн рёбер Leiden даёт связные кластеры без «разорванных» сообществ, которые иногда выдаёт Louvain.
- Подбери resolution так, чтобы получить 8–12 кластеров, и построй UMAP с раскраской по leiden.