Библиотека ускоренных графиков:Есть ли аккуратный алгоритм, встроенный в BGL для обнаружения сообщества?

Question

Кто-нибудь там использует BGL для больших производственных серверов?

• Из скольких узлов состоит ваша сеть?
• Как вы справляетесь обнаружение сообщества
• Есть ли у BGL какие-нибудь классные способы обнаружения сообществ?
• Иногда два сообщества могут быть связаны друг с другом одним или двумя краями, но эти края ненадежны и могут исчезнуть.Иногда краев вообще нет.

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

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

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

Answer 1

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

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

Answer 2

Насколько я знаю, в BGL нет никаких алгоритмов, специально предназначенных для обнаружения сообщества.

Под "островом" вы подразумеваете несвязанный подграф?

Кроме того, графики не имеют никакого понятия о "расстоянии".

Эта "социальная дистанция" - это то, что вам придется определить.Как только вы это сделаете, большая часть работы будет выполнена.

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

@ David Nehme

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

Кроме того, он говорит о расстоянии между двумя несвязанными графиками.Чтобы смоделировать это, вы должны ввести внешнюю концепцию расстояния между узлами, отдельную от расстояния до края.