Обнаружение сообщества в полных и взвешенных сетях

У меня есть полный сетевой граф, в котором все вершины связаны друг с другом, и они различаются только формой своего разного веса. Примером сети может быть: торговая сеть, в которой все страны так или иначе связаны друг с другом и отличаются только формой разного объема торгов.

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

В голову пришло два варианта:

  1. Разрежьте сеть на более мелкие части, разрезав их на определенном «пороговом уровне веса».
  2. Или используйте алгоритм иерархического кластера, чтобы превратить всю сеть в блочную модель. Но я думаю, что проблема «без отклонений в геодезическом плане» останется.

cluster-analysis algorithm network-programming
person PeteWoods    schedule 04.07.2017    source источник
comment
Я считаю, что это скорее концептуальный вопрос, чем вопрос программирования.   -  person o_weisman    schedule 04.07.2017

Ответы (1)


arrow_upward
2
arrow_downward

Было предложено несколько методов.

Один простой, но эффективный метод был предложен в Быстрое развертывание сообществ в больших сетях (Blondel et al., 2008 ). Он поддерживает взвешенные сети. Цитата из аннотации:

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

Цитата из статьи:

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

Так что он должен работать для полного графика, но вам лучше его проверить.

Реализация C ++ доступна здесь (теперь поддерживается здесь).

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

person Lior Kogan    schedule 04.07.2017