Comments 4
Ссылки на разную литературу по нахождению сообществ (скопировал из комментария к предыдущей части). Может быть, кто-то заинтересуется.
Статьи:
Louvain — иерархическая кластеризация на основе модулярности. Несмотря на недостатки (resolution limit модулярности), один из самых широкоизвестных методов за счет быстроты.
MCL + MLR-MCL — Марковская кластеризация, имитация случайного блуждания на графе + ее иерархический и более быстрый вариант + оптимальное прореживание ребер и другая предобработка.
SCD — алгоритм на основе подсчета замкнутых треугольников внутри и между сообществами, очень качественный и быстрый.
Spinner — на основе label propagation, с подробным описанием как его реализовать распределенно.
Infomap (серия публикаций) — на основе оптимального кодирования узлов графа, чтобы случайное блуждание на нем представлялось наиболее компактно.
RG — «рандомизированная жадная» эвристика для максимизации модулярности (но может быть использована, в принципе, для чего угодно)
Blockmodeling — байесовский подход (довольно зубодробительная статья и все ее последователи тоже).
Стабильные ядра — одно из исследований, как улучшать качество кластеров, если сеть все время эволюционирует.
Ансамблевый подход к кластеризации, на основе тех же стабильных ядер.
Книги:
Data clustering: algorithms and applications (могу прислать электронную версию) — здесь есть одна большая глава про кластеризацию графов, в ней описаны классические методы (Kernigan-Lin, Girwan-Newman, спектральная кластеризация). Про них можно еще посмотреть на курсере, википедии или в других местах.
Mining Massive Datasets — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Статьи:
Louvain — иерархическая кластеризация на основе модулярности. Несмотря на недостатки (resolution limit модулярности), один из самых широкоизвестных методов за счет быстроты.
MCL + MLR-MCL — Марковская кластеризация, имитация случайного блуждания на графе + ее иерархический и более быстрый вариант + оптимальное прореживание ребер и другая предобработка.
SCD — алгоритм на основе подсчета замкнутых треугольников внутри и между сообществами, очень качественный и быстрый.
Spinner — на основе label propagation, с подробным описанием как его реализовать распределенно.
Infomap (серия публикаций) — на основе оптимального кодирования узлов графа, чтобы случайное блуждание на нем представлялось наиболее компактно.
RG — «рандомизированная жадная» эвристика для максимизации модулярности (но может быть использована, в принципе, для чего угодно)
Blockmodeling — байесовский подход (довольно зубодробительная статья и все ее последователи тоже).
Стабильные ядра — одно из исследований, как улучшать качество кластеров, если сеть все время эволюционирует.
Ансамблевый подход к кластеризации, на основе тех же стабильных ядер.
Книги:
Data clustering: algorithms and applications (могу прислать электронную версию) — здесь есть одна большая глава про кластеризацию графов, в ней описаны классические методы (Kernigan-Lin, Girwan-Newman, спектральная кластеризация). Про них можно еще посмотреть на курсере, википедии или в других местах.
Mining Massive Datasets — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Вы не занимались проблемой кластеризации очень больших графов с использованием распределённых вычислений: Хадупа, Жирафа?
С большим удовольствием читаю ваши статьи. Спасибо за труд и, пожалуйста, пишите еще! )
Sign up to leave a comment.
Кластеризация графов и поиск сообществ. Часть 2: k-medoids и модификации