Параметр 'ufactor' в метисе для кластеризации дисбаланса

Question

Я использую METIS для кластеризации пользователей социальных сетей.

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

Я нахожу параметр ufactor в руководстве, которое подходит (я думаю) для моего случая, но я не понял, что он на самом деле делает. У меня есть большой график и попытался с некоторым значением ufactor, Для одного набора данных ufactor=1000 работает очень хорошо, но для другого набора данных он не может даже разбить график. Я не могу интерпретировать этот результат, так как я не понимал, что он на самом деле делает. Вот что я нашел в руководстве по этому поводу:

Определяет максимально допустимый дисбаланс нагрузки между разделами. Значение x указывает, что допустимый дисбаланс нагрузки равен (1 + x)/1000. Дисбаланс нагрузки для j-го ограничения определяется как max_i(w[j, i])/t[j, i]), где w [j, i] - доля общего веса j-го ограничения, которое назначено к i-му разделу, а t [j, i] - желаемый целевой вес j-го ограничения для i-го раздела (т. е. тот, который указан с помощью -tpwgts). Для -ptype=rb значение по умолчанию равно 1 (т. Е. Дисбаланс нагрузки равен 1,001), а для -ptype=kway значение по умолчанию равно 30 (т. Е. Дисбаланс нагрузки равен 1,03).

Кто-нибудь может помочь мне интерпретировать это? Вот что jth ограничения? что такое -ptype=rb/kway?

Answer 1

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

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

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

Но вернемся к исходному вопросу:

Что такое -ptype=rb/kway ?

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

Какое j-е ограничение?

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

Смотрите руководство:

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

РЕДАКТИРОВАТЬ: Поскольку вы пояснили, что вы хотите посмотреть на фиксированное количество кластеров, я вижу, как разделение графа может быть полезным здесь. Позвольте мне проиллюстрировать, что ufactor средства:

Дисбаланс разделенного графа (в этом простом случае) вычисляется как максимум дисбаланса для каждого раздела, который примерно равен частному partition size / average partition size, Поэтому, если мы допустим максимальный дисбаланс 2, это означает, что самый большой раздел в два раза больше среднего раздела. Обратите внимание, что ufactor не указывает дисбаланс напрямую, он указывает, сколько пермилл от 1 допускается дисбаланс. Так ufactor=143 фактически означает, что ваш максимально допустимый дисбаланс составляет 1,143, что имеет смысл, поскольку ваши кластеры не так уж далеко друг от друга. Так что в вашем случае вы, вероятно, будете использовать большие значения для ufactor, чтобы позволить группам иметь совершенно разные размеры.

Последствия большого дисбаланса

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

Как насчет спектрального разделения, ...?

Общий подход METIS работает следующим образом:
Большинство входных графов слишком велики для непосредственного разбиения, поэтому используются так называемые многоуровневые методы:

• Граф сначала укрупняется (узлы объединяются при попытке сохранить структуру графа), пока его размер не станет возможным для прямого разбиения
• Самый грубый граф разделяется с использованием метода начального разбиения, где мы могли бы использовать различные подходы (комбинаторное деление на части, спектральное деление на части, точные решения с использованием ILP, ...).
• Затем график не огрубляется, и на каждом шаге небольшое количество узлов перемещается от раздела к разделу в локальном поиске, чтобы улучшить общее срезание края.

Моя личная рекомендация

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

Как вы можете прочитать на домашней странице METIS, он в основном используется для довольно разреженных графиков ("методы конечных элементов, линейное программирование, СБИС и транспорт"), тогда как социальные сети гораздо плотнее и имеют другую структуру (степени следуют за степенью закон распределения)

В методе грубого слияния METIS используется сопоставление тяжелых краев для объединения узлов, которые каким-то образом расположены близко друг к другу, что отлично подходит для предполагаемых приложений, для социальных сетей, однако методы укрупнения на основе кластеров могут оказаться более эффективными.
Еще одна библиотека, которая немного медленнее в целом, но реализует некоторые предустановки, особенно для социальных сетей, - это KaHIP, подробности см. В руководстве.

(Я должен отметить, однако, что я предвзят в этом отношении, так как я много работал с этой библиотекой;-))