ГлавнаяАрхивО целочисленном линейном программировании для задач кластеризации вершин графа

О целочисленном линейном программировании для задач кластеризации вершин графа | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/3

Задачи кластеризации являются важной частвю анализа данных. В них требуется разбитв заданное множество объектов на несколько подмножеств (кластеров) на основе сходства объектов друг с другом. Задача кластеризации вершин графа является формализацией задачи кластеризации. Сходство объектов задаётся с помощвю рёбер некоторого графа, вершины которого взаимно однозначно соответствуют объектам. Существует множество вариантов задачи: с ограничением на число и размер кластеров, взвешенные и ориентированные постановки; все известные варианты задачи являются NP-трудными. Данная работа посвящена одному из подходов к решению задачи - построению моделей целочисленного линейного программирования. Приведён обзор известных и предложены новые подходы к построению таких моделей. Новые модели могут исполвзоватвся как для нахождения точных решений, так и для построения приближённых алгоритмов. Проведён вычислителвный эксперимент, направленный на оценку времени, необходимого алгоритмам, опирающимся на различные модели, для нахождения точного решения. Показано, что один из алгоритмов, опирающихся на новые модели, быстрее других находит решение для задачи с ограниченным числом кластеров.
  • Title О целочисленном линейном программировании для задач кластеризации вершин графа
  • Headline О целочисленном линейном программировании для задач кластеризации вершин графа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 70
  • Date:
  • DOI 10.17223/20710410/70/3
Ключевые слова
кластерный граф, целочисленное линейное программирование, NP-mрудная задача
Авторы
Ссылки
Schaeffer S. Е. Graph clustering // Comput. Sci. Rev. 2005. V. 1. No. 1. P. 27-64.
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113.
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. No. 1-2. P. 173-182.
Ben-Dor A., Shamir R., and Yakhimi Z. Clustering gene expression patterns // J.Comput. Biol. 1999. V.6. No.3-4. P.281-297.
Sole P. and Zaslavsky T. A coding approach to signed graphs // SIAM J. Discrete Math. 1994. No. 7. P. 544-553.
О целочисленном линейном программировании для задач кластеризации вершин графа | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/3
О целочисленном линейном программировании для задач кластеризации вершин графа | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/3