Я ищу эффективный алгоритм для поиска кластеров на большом графе (он имеет около 5000 вершин и 10000 ребер).
До сих пор я использую алгоритм Гирвана-Ньюмана, реализованный в Java-библиотеке JUNG, но он довольно медленный, когда я пытаюсь удалить много ребер.
Можете ли вы предложить мне лучшую альтернативу для больших графиков?
algorithms
graph
cluster
mariosangiorgio
источник
источник
Ответы:
Я лично предлагаю марковскую кластеризацию . Я использовал это несколько раз в прошлом с хорошими результатами.
Распространение сродства - еще один жизнеспособный вариант, но он кажется менее последовательным, чем кластеризация Маркова.
Существуют различные другие варианты, но эти два хороши из коробки и хорошо подходят для конкретной проблемы кластеризации графов (которую можно рассматривать как разреженные матрицы). Мера расстояния, которую вы используете, также является соображением. Ваша жизнь будет проще, если вы используете правильную метрику.
Я нашел эту статью, когда искал критерии производительности, это хороший обзор предмета.
источник
Иерархическая кластеризация
Это было рекомендовано мне другом. Согласно Википедии :
Марковский кластер
Это то, что я использую в вашей ситуации. Это очень полезный алгоритм. Я нашел ссылку на хороший PDF об Алгоритме. Это отличный алгоритм и, из-за отсутствия лучшего термина, чрезвычайно «мощный». Попробуйте и посмотрите.
источник
Для вашей проблемы здесь, я думаю, вы должны подумать о способе сопоставления вершин-ребер с набором координат для каждой вершины. Я не уверен, есть ли лучший способ сделать это. Но, я думаю, вы могли бы начать с представления каждой вершины как измерения, а затем значение ребра для конкретной вершины станет значением, с которым вам нужно работать для этого конкретного измерения. После этого вы можете сделать простую дистанцию Евклида и работать с этим.
источник