Алгоритм Leiden · Leiden algorithm
Алгоритм Leiden — метод выделения сообществ (кластеров) в графах, развитие алгоритма Louvain, гарантирующий внутреннюю связность найденных сообществ.
Подробно
Алгоритм Leiden предложен в 2019 году (Traag, Waltman, van Eck) как улучшение алгоритма Louvain для задачи community detection. Он итеративно оптимизирует функцию качества разбиения (модулярность или CPM): сначала выполняет локальные перемещения узлов между сообществами, затем укрупняет граф и при необходимости уточняет границы сообществ на этапе refinement. Ключевое отличие от Louvain — гарантия того, что каждое найденное сообщество внутренне связно, при сопоставимой или лучшей скорости и качестве разбиения. Применяется в анализе социальных сетей, биоинформатике, рекомендательных системах, кластеризации графов знаний и пайплайнах graph ML. Основные реализации — функция community_leiden в igraph и библиотека leidenalg.
Примеры употребления
- pip install igraph leidenalg
- import igraph as ig; g = ig.Graph.Famous('Zachary'); part = g.community_leiden(objective_function='modularity')
- part = g.community_leiden(objective_function='CPM', resolution=0.05, n_iterations=2)
- Кластеризация графа цитирований научных статей для выделения тематических сообществ