Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Информационные технологии и математическое моделирование (ИТММ-2022); Томск; Томск
Год издания: 2023
Ключевые слова: знаковый граф, задача кластеризации графа, дерево решений
Аннотация: В настоящей работе рассматривается задача кластеризации для неориентированных и невзвешенных знаковых графов без кратных ребер и петель с функционалом ошибки в виде линейной комбинации межкластерной и внутрикластерной ошибок. Данная задача относится к классу NP-трудных задач. Также известно, что ее решение может быть не единственным. Исследуются свойства разработанного ранее эвристического алгоритма SGClusta. Основное внимание уделено исследованию зависимости результата работы данного алгоритма от начальной перенумерации вершин графа и предлагается подход, который специальным образом игнорирует нумерацию вершин, что приводит к нахождению для каждой перенумерации множества кластеров. При этом подход учитывает изоморфные друг другу перенумерации, что значительно сокращает пространство перебора. В результате строится дерево решений данного алгоритма.
Журнал: Информационные технологии и математическое моделирование (ИТММ-2022)
Номера страниц: 259-264
Место издания: Томск