Что такое хороший алгоритм перекрывающихся групп?

Question

Я знаком с различными алгоритмами кластеризации (k-средних и т.д.), но для моего конкретного случая использования (социальные сети) мне нужен алгоритм, который обнаруживает перекрывающиеся группы. Этот алгоритм аккуратно разделяет моих друзей из Facebook на моих школьных друзей, моих друзей по колледжу, мою семью и моих друзей по работе.

Алгоритм, который я использовал выше (VoltageClusterer от JUNG), разделяет узлы на отдельные кластеры. Но мне нужен алгоритм, который может назначать узлы нескольким кластерам (например, мой друг может быть и моим школьным другом, и другом по колледжу).

Как мне это сделать? Было бы неплохо, если бы этот алгоритм работал и для взвешенных графов, а не только для невзвешенных.

Answer 1

У Palla et al. Есть хороший документ Nature по обнаружению перекрывающихся сообществ: http://www.nature.com/nature/journal/v435/n7043/full/nature03607.html Они демонстрируют его успех в различных типах сетей, от социального взаимодействия до взаимодействия с белком.

Алгоритм называется перколяцией k-клики. Это реализовано в их программе C-finder: http://www.cfinder.org/

Answer 2

Вы можете попробовать нечеткий c-means, который очень похож на старый резервный, k-means, но допускает перекрывающиеся кластеры. Существует разумное введение (включая небольшую демонстрацию) по адресу:

Учебное пособие по алгоритмам кластеризации: нечеткие c-средние

Answer 3

Отвечая на мой собственный вопрос, я нашел приличную статью: http://www.springerlink.com/content/y44484587755k478/

Любые другие документы / подходы будут полезны.