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

Question

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

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

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

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

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

score 6 · Accepted Answer · 07 ноября 2008, 15:42

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

Что касается обнаружения сообщества, в BGL нет встроенных алгоритмов специально для этого (но, возможно, вы сможете внести свой вклад, когда закончите свой проект). Есть несколько алгоритмов, которые могут быть полезны при построении алгоритма обнаружения сообщества. Алгоритмы max-flow / min-cut обычно используются при обнаружении сообществ (если между двумя узлами возможен большой поток, то они, скорее всего, будут в одном сообществе, если поток небольшой, то минимальный разрез, вероятно, будет представлять дороги между сообществами ). Также есть эвристика, чтобы упорядочить узлы графа для уменьшения пропускная способность . Узлы, составляющие «сообщества», вероятно, будут находиться близко друг к другу в таком порядке.

score 0 · Answer 2 · 07 ноября 2008, 15:41

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

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

Кроме того, в графиках нет понятия «расстояние».

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

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

@ Дэвид Нехме

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

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

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

2 ответов