Алгоритмы для ограниченной кластеризации на приписанных графах с некоторыми ограничениями уровня кластера на их атрибутах

Question

У меня есть график с узлами 240 тыс. И ребрами 550 тыс. С пятью атрибутами на узел, исходящий из автоэнкодера из разреженного набора данных. Я рассчитываю разбить график на n кластеров, так чтобы сходство атрибутов внутри раздела было максимальным, разделы связаны, и сумма одного из атрибутов не превышает пороговое значение для любого данного кластера.

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

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

Answer 1

Прежде всего, проблема, скорее всего, NP-сложная, поэтому лучшее, что вы можете сделать, - это жадная оптимизация.Это определенно поможет сначала разбить граф на подмножества, которые никогда не могут быть соединены (удалите связи узлов, которые недостаточно похожи, затем вычислите связанные компоненты).Затем для каждого компонента (который, мы надеемся, намного меньше, чем 250 тыс., В противном случае вам не повезло!) Запустите классический оптимизатор , который позволяет вам указать функцию стоимости.Вероятно, хорошей идеей будет использовать целочисленную линейную программу и рассмотреть двойственную версию задачи Лагранжа.