Эффективный алгоритм кластеризации графа

20

Я ищу эффективный алгоритм для поиска кластеров на большом графе (он имеет около 5000 вершин и 10000 ребер).

До сих пор я использую алгоритм Гирвана-Ньюмана, реализованный в Java-библиотеке JUNG, но он довольно медленный, когда я пытаюсь удалить много ребер.

Можете ли вы предложить мне лучшую альтернативу для больших графиков?

mariosangiorgio
источник
Вы смотрели на К-средних?
Одед
Можете ли вы дать мне некоторую ссылку, чтобы узнать, как использовать его на графике?
Мариосангиорджо
Я переключился на JUNG-реализацию VoltageClusterer, и это определенно быстро. jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/…
mariosangiorgio
1
Разве это не больше подходит для < cs.stackexchange.com >, так как это больше касается компьютерных наук, чем программиста?
Oeufcoque Penteano

Ответы:

13

Я лично предлагаю марковскую кластеризацию . Я использовал это несколько раз в прошлом с хорошими результатами.

Распространение сродства - еще один жизнеспособный вариант, но он кажется менее последовательным, чем кластеризация Маркова.

Существуют различные другие варианты, но эти два хороши из коробки и хорошо подходят для конкретной проблемы кластеризации графов (которую можно рассматривать как разреженные матрицы). Мера расстояния, которую вы используете, также является соображением. Ваша жизнь будет проще, если вы используете правильную метрику.

Я нашел эту статью, когда искал критерии производительности, это хороший обзор предмета.

Натан Райс
источник
Спасибо, я посмотрю на все предложенные вами алгоритмы.
mariosangiorgio
Исправление: эти алгоритмы нужны в качестве входных весов, которые отражают сходство, а не расстояние. Метрическое свойство (неравенство треугольника) в него не входит. Это может быть полезно для преобразования весов, чтобы они попадали в естественный диапазон, например, для (Pearson) корреляций, как описано здесь ( micans.org/mcl/man/clmprotocols.html#array ), и для значений BLAST E, как описано здесь ( micans.org/mcl/man/clmprotocols.html#blast ).
micans
10

Иерархическая кластеризация

Это было рекомендовано мне другом. Согласно Википедии :

В этом методе определяется мера сходства, определяющая количественно некоторый (обычно топологический) тип сходства между парами узлов. Обычно используемые меры включают в себя косинусное сходство, индекс Жакара и расстояние Хемминга между строками матрицы смежности. Затем один группирует аналогичные узлы в сообщества в соответствии с этой мерой. Существует несколько общих схем для выполнения группировки, две из которых являются простейшей кластеризацией с одной связью, в которой две группы считаются отдельными сообществами, если и только если все пары узлов в разных группах имеют сходство ниже заданного порога, и полная кластеризация связи , в котором все узлы в каждой группе имеют сходство, превышающее пороговое значение.

Марковский кластер

Это то, что я использую в вашей ситуации. Это очень полезный алгоритм. Я нашел ссылку на хороший PDF об Алгоритме. Это отличный алгоритм и, из-за отсутствия лучшего термина, чрезвычайно «мощный». Попробуйте и посмотрите.

динамический
источник
5

Для вашей проблемы здесь, я думаю, вы должны подумать о способе сопоставления вершин-ребер с набором координат для каждой вершины. Я не уверен, есть ли лучший способ сделать это. Но, я думаю, вы могли бы начать с представления каждой вершины как измерения, а затем значение ребра для конкретной вершины станет значением, с которым вам нужно работать для этого конкретного измерения. После этого вы можете сделать простую дистанцию ​​Евклида и работать с этим.

viki.omega9
источник
1
Немного почитав, я нашел это здесь и думаю, вам стоит взглянуть.
viki.omega9