ISSN 2071-0410 · EISSN 2311-2263
Язык: ru

Статья: ПОДХОД К АНАЛИЗУ И ПОСТРОЕНИЮ АЛГОРИТМОВ РЕШЕНИЯ ОДНОЙ ЗАДАЧИ КЛАСТЕРИЗАЦИИ НА ЗНАКОВЫХ ГРАФАХ (2024)

Читать онлайн

Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClustα с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки.

Ключевые фразы: ЗНАКОВЫЙ ГРАФ, КОРРЕЛЯЦИОННАЯ КЛАСТЕРИЗАЦИЯ, СИСТЕМАТИЗАЦИЯ АЛГОРИТМОВ, ПОТЕНЦИАЛЬНЫЕ ФУНКЦИИ
Автор (ы): СОЛДАТЕНКО А.А.
Соавтор (ы): СЕМЕНОВА Д.В., ИБРАГИМОВА Э.И.
Журнал: ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА

Идентификаторы и классификаторы

УДК
519.17. Теория графов
Для цитирования:
СОЛДАТЕНКО А.А., СЕМЕНОВА Д.В., ИБРАГИМОВА Э.И. ПОДХОД К АНАЛИЗУ И ПОСТРОЕНИЮ АЛГОРИТМОВ РЕШЕНИЯ ОДНОЙ ЗАДАЧИ КЛАСТЕРИЗАЦИИ НА ЗНАКОВЫХ ГРАФАХ // ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА. 2024. № 64