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

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

6 голосов
/ 07 ноября 2008

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

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

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

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

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

Ответы [ 2 ]

6 голосов
/ 07 ноября 2008

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

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

0 голосов
/ 07 ноября 2008

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

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

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

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

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

@ David Nehme

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

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

...