Pull to refresh

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 — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Вы не занимались проблемой кластеризации очень больших графов с использованием распределённых вычислений: Хадупа, Жирафа?
Нет, но планируем попробовать GraphX. Если доставать графы посещений доменов более низкого уровня, или вообще интернет-страниц, то без этого, мне кажется, не обойтись.
С большим удовольствием читаю ваши статьи. Спасибо за труд и, пожалуйста, пишите еще! )
Only those users with full accounts are able to leave comments. Log in, please.