Данные и ML · Экспертный — набор 1

Данные и ML · терминов: 3 · усвоено: 0

Экран 1 из 3Войдите, чтобы сохранять прогресс и получать баллы

Алгоритм Leiden · Leiden algorithm

Частота: ниже среднего · Сложность: 4/5 · растёт

Алгоритм 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)

Кластеризация графа цитирований научных статей для выделения тематических сообществ

#графы#кластеризация#community detection#igraph

Источники

https://github.com/Graphify-Labs/graphify https://en.wikipedia.org/wiki/Leiden_algorithm https://arxiv.org/abs/1810.08473 https://python.igraph.org/en/stable/api/igraph.Graph.html

Полная карточка в словаре — открыть в новой вкладке ↗