М. Ш. Левин

О задаче редактирования в кластеризации

В статье рассмотрена задача редактирования в кластеризации (удаление и добавление ребер и/или вершин исходного графа с целью формирования кластерной структуры), включая ее различные версии (задача редактирования ребер, задача редактирования вершин и др.). Приведен обзор литературы по данным задачам (типы задач, методы их решения). Особое внимание уделено задаче редактирования ребер. Для этой задачи представлены математические оптимизационные формулировки на минимизацию: (1) базовая задача редактирования ребер с минимизацией общего числа удаления ребер и добавления вершин, (2) версии указанной базовой задачи с весами для всех пар вершин (включая двух-критериальный случай), (3) многокритериальная задача при векторных весах пар вершин. Кратко описаны несколько других задач редактирования: (а) задача редактирования на основе только удаления ребер, (б) задача редактирования с учетом нескольких типов вершин, (в) задача редактирования на основе только удаления вершин. Численные примеры иллюстрируют рассмотренные задачи. Приведены перспективные направления исследований.

КЛЮЧЕВЫЕ СЛОВА: кластеризация, редактирование кластеров, комбинаторная кластеризация, комбинаторная оптимизация.