Алгоритм для выявления сообществ в больших сетях

[flashnik]

Псевдолинейный алгоритм, зависящий от угадываемого параметра-числа сообществ :(

[akuznetsov]

А так все алгоритмы кластеризации типа K-means и Expectation-Maximization устроены. Так что в это ничего страшного нет.

[flashnik]

Ну как бэ…
Если посмотреть на работы последних лет, то одно из направлений работ по указанным Вами алгоритмам — это как подобрать/варьировать это число без существенной трудоемкой перестройки найденного при данном значении параметра решения.

Если смотреть на их статью, то «Assume that we start with a weighted network of N nodes. First, we assign a different community to each node of the network. So, in the initial partition there are as many communities as there are nodes.»
N человек-> N нод-> на первом этапе N сообществ => N^2 сложность первой итерации. И все, приплыли…

[flashnik]

Пардон, совсем невнимательно прочитал.
Нода относится только к сообществу ее соседей, поэтому сложность линейна по числу линков.
Так что по сути это просто аггломеративная кластеризация/построение дендрограммы с таким особым функционалом, определяющим сливающиеся кластеры.

[anvaka]

Мне понравился SLPA алогритм (https://sites.google.com/site/communitydetectionslpa/ ), для которого не нужно указывать число сообществ. И более того он эффективно находит пересекающиеся множества (обычно челове состоит в нескольких группах одновременно). Думаю, его модель можно хорошо масштабировать, т.к. все вычисление можно свести к двум программам, выполняющихся на узлах графа. Одна программа говорит случайное слово случайному соседу, вторая программа слушает все входящие слова от соседей и запоминает их. По итогам нескольких итераций каждый узел может посмотреть у себя в памяти какие слова приходили, и выбрать самые популярные. Группа узлов с одинаковыми словами и будет сообществом. Гениально :).

Вот мой пример реализации, если вдруг кому интересно будет: github.com/anvaka/VivaGraphJS/blob/master/src/Algorithms/Community/slpa.js

(ато код в статье авторов мне показался немножко страшненьким)…

[Karbas]

Эвристика такая эвристика. Никакого нового взгляда на то, как же жить с графами, из этой статьи вы не получите.

[eRaider]

Что-то мне это напоминает Ахо/Хадиетниеми и всякие штуки с графами. Конкретно — поиск максимально полного подграфа графа.

[beetleinweb]

Мне сейчас как раз нужен хороший визуализатор графов. Но то, что я вижу на рисунке — мочалка. Мне не нужна рисовалка мочалок, мочалку я и сам могу нарисовать. Может не так быстро, как самая быстрая рисовалка мочалок в мире, но результат-то один, пофигу за какое время.

А что такое хороший визуализатор графов? Мечта:

Как видно из рис. 1, в центральной области расположены известные, связанные между собой документы. В левой части есть документы, которые безответно ссылаются на документы из центральной части. В правой части рисунка находятся документы, на которые ссылаются документы из центральной области, но сами эти документы ни на кого не ссылаются. Кроме того, есть несколько «островов», документы которых связаны только между собой и никак не соединены с информационными «материками».

Вот такую кластеризацию я хочу видеть. Неоднородности, структуру, тенденции и феномены. И пусть хоть месяц рисует.

[stab]

К сожалению задачка NP-сложная, рисовать будет годами, да и формализовать постановку сложно. Данные многомерные, измерений по количеству вершин, и не факт что есть какая-то красивая «проекция» на плоскость. Поэтому чаще задачу переформулируют как «нарисовать прикольный граф», и тут уже начинаются эвристики и прочее :)

[beetleinweb]

Мочалка — неприколько (если это только не логотип :) ).

Я не против эвристики, я даже не против статистики. Разбили на группы свыше 100 человек — отлично. Давайте ещё и связи между группами суммируем и отфильтруем. Если их меньше 10 (или меньше 10% от числа юзеров в группе) — будем считать что это не связь, а так, случайность и шум, не стоит внимания — стираем.

Так глядишь и проявятся некие шаблоны, и отклонения от оных. Уже не однородная мочалка будет, а нечто, что можно попытаться осмыслить и как-то использовать. А граф-мочалку только одним способом можно использовать — измерять в попугаях, у кого больше и волосатее :)

Раздражает ещё совершенно одинаковое отображение связей (обычно). Вот количество юзеров в группе тут явно размером окружности отражёно. Так почему количество связей между группами не отразить толщиной и яркостью линий? Отражено расстоянием? Хм. Сильно сомневаюсь. Наверняка для расстояний что-нибудь в терминах физики используется, типа притяжения и отталкивания узлов.

[vladislavkorobov]

Gephi и Tulip пробуйте
tulip.labri.fr/TulipDrupal/
gephi.org/

[beetleinweb]

Спасибо, премного благодарен. Gephi, похоже, то что нужно. Есть фильтрация, есть метрики, есть динамика… много чего есть. И всё это crossplatform, open source and free. Круто.

[vladislavkorobov]

Автор стати, напишите, пожалуйста, упрощенно (как для ребенка) как делается первая стадия.
А то ничего не понятно.

[texamus]

Как раз год назад выкладывал на Хабре заметку об анализе социального графа в Твиттере при помощи этого алгоритма:
habrahabr.ru/blogs/twitter/81225/