Алгоритмы обнаружения сообщества с использованием NetworkX

Question

У меня есть сеть, которая является графической сетью, и это сеть Email-Eu, которая доступна в здесь .

Этот набор данных имеет фактический набор данных, представляющий собой граф из 1005 узлов с ребрами, которые образуют этот гигантский граф. Он также имеет основные метки истинности для узлов и соответствующих сообществ (отделов). Каждый из этих узлов принадлежит одному из каждых 42 отделов.

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

Итак, сначала мне нужно найти первые 42 отдела (сообщества), а затем найти узлы в самом большом из них.

Я начал с алгоритма Гирвана-Ньюмана, чтобы найти сообщества. Прелесть Girvan-Newman в том, что его легко реализовать, потому что каждый раз, когда мне нужно найти грань с наивысшим промежуточным положением, и убрать ее, пока не найду 42 отдела (сообщества), которые я хочу.

Я изо всех сил пытаюсь найти другие алгоритмы обнаружения сообществ, которые дают мне возможность указать, на сколько сообществ / разделов мне нужно разбить свой график.

Есть ли какая-либо функция / метод обнаружения сообщества, которую я могу использовать, что дает мне возможность указать, сколько сообществ мне нужно обнаружить из моего графика? Любые идеи очень ценятся.

Я использую Python и NetworkX.

Answer 1

(очень) частичный ответ (и решение) на ваш вопрос заключается в использовании алгоритма Fluid Communities , реализованного Networkx как asyn_fluidc.

Обратите внимание, чтоон работает на связанных, неориентированных, невзвешенных графах, поэтому, если у вашего графа есть n связанных компонентов, вы должны запустить его n раз.На самом деле это может быть серьезной проблемой, поскольку у вас должны быть какие-то предварительные знания о каждом компоненте, чтобы выбрать соответствующий k.

В любом случае, стоит попробовать.

Answer 2

Вы можете попробовать pysbm .Он основан на networkx и реализует различные варианты стохастических блочных моделей и методов вывода.

Если вы планируете переключиться с networkx на другой пакет графов на основе Python, вы можете рассмотреть graph-tool , где вы сможете использовать стохастическую блочную модель для задача кластеризации .Другой заслуживающий внимания пакет - igraph , возможно, стоит взглянуть на Как кластеризовать граф с помощью python igraph .

Подходы, доступные непосредственно в networkx, довольно старомодны.Если вы стремитесь к современным методам кластеризации, вы можете рассмотреть спектральную кластеризацию или Infomap.Выбор зависит от вашего желаемого использования предполагаемых сообществ.Задача определения наземной правды из сети подпадает под (приблизительную) теорему об отсутствии свободного обеда, то есть (примерно) не существует никакого алгоритма, так что он возвращает «лучшие» сообщества, чем любой другой алгоритм, если мы усредним результаты повсе возможности.

Answer 3

Я не совсем уверен в своем ответе, но, возможно, вы можете попробовать это.Знаете ли вы о распространении этикетки?Основная идея заключается в том, что у вас есть некоторые узлы в графе, которые помечены, т. Е. Они принадлежат сообществу, и вы хотите присвоить метки другим немаркированным узлам в вашем графе.LPA распространит эти метки по всему графику и предоставит вам список узлов и сообществ, к которым они принадлежат.Эти сообщества будут такими же, как те, к которым принадлежит ваш помеченный набор узлов.

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

Вы можете прочитать о LPA здесь , а также здесь