Алгоритмы разбиения графа

[AlexDem]

Есть большой граф средней степени связности. Он не статичен - в него постоянно добавляются новые вершины, рёбра; что-то удаляется, перестраивается. Нужен алгоритм, динамически поддерживающий разбиение такого графа на минимально связные куски. То есть - позволяющий определить, в какой из существующих разделов следует поместить вновь добавляемую вершину, пересчитать принадлежность соседних вершин при добавлении или удалении рёбер или вершин. Алгоритм должен работать быстро, пусть не совсем точно.

Универсальных решений здесь нет, но эвристические - возможны. Может кто знает хорошие работы в этом направлении? Я нашёл ряд работ (пока не знаю - насколько хороших), но может что-то упустил, на что стоит обратить внимание?

Примеры:
Graph Partitioning Models for Parallel Computing
Graph partitioning for high performance scientific simulations
Исследование методов организации данных в задачах разбиения графов больших размерностей

[AKM]

Переношу в корневой раздел.

[bin]

А не является ли этот граф деревом/лесом деревьев? Если можно обойтись деревом, наподобие дерева директорий компьютерных дисков - задача сильно упростится. Т.е. нельзя ли свести ее к задаче балансировки деревьев?

[AlexDem]

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

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

[mserg]

В программировании в ограничениях существует подобная проблема. Пробовал писать нашим мэтрам по теории графов – результат нулевой. На данный момент задача не решена.

Возможно, поможет поиск по ключевой фразе Dynamic Graphs.

[AlexDem]

А алгоритм Kernighan-Lin насколько плох? Там товарищ вроде обещает то, что нужно: "Generalization of the Kernighan-Lin/Fiduccia-Mattheyses algorithm to handle weighted graphs, arbitrary number of sets and lazy initiation". Я просто думал, что может есть что-нибудь поинтересней.

[Pavlovsky]

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

[AlexDem]

Не понял Вашу мысль - каким образом структура хранения может повлиять на принципы разбиения? Операции я привёл: добавление отдельных вершин, рёбер, их изменение, удаление; чтение - уж как-нибудь приделаю.

[mserg]

to AlexDem
Чтобы сказать, хороша эвристика или плоха, нужен набор адекватных реальной жизни тестовых данных. Для данной задачи, видимо, это симулятор с параметрами. "Прогоняя" на нем алгоритм, можно оценить качество эвристики. Если нет набора тестовых данных – то получаем разговор ни о чем, так как всегда можно подобрать «хорошие» для конкретной эвристики «данные» (симуляции изменений графа), и данные, на которых алгоритм будет работать «неадекватно».

[AlexDem]

Тогда поставим вопрос так: вот попробую я этот "Kernighan-Lin", и окажется он для моей задачи неважным... Какой алгоритм мне можно попробовать ещё? Есть ли такие?

[mserg]

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

[AlexDem]

Хорошо, спасибо! Я просто боялся пройти мимо какого-нибудь удачного решения.