Перевод названия: MODIFICATION OF THE ALGORITHM SGCLUSTα FOR THE SIGN GRAPH CLUSTERING PROBLEM
Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Системы управления, информационные технологии и математическое моделирование; Омск; Омск
Год издания: 2022
Идентификатор DOI: 10.25206/978-5-8149-3487-1-2022-1-166-172
Ключевые слова: sign graph, clusterization, the balance of the signed graph, знаковые графы, кластеризация, сбалансированность знакового графа
Аннотация: В работе исследуется одна из задач знакового баланса задача разбиения знакового графа. Критерием качества разбиения знакового графа является функция суммарной ошибки, которая определяется как выпуклая комбинация внутрикластерной и межкластерной ошибок. Данная задача является NP-полной. В работе предлагается модификация полиномиалПоказать полностьюьного алгоритма SGClustα решения задачи разбиения знакового графа без ограничения на количество кластеров. Алгоритм на вход принимает граф без какого-либо начального разбиения. Минимизация функционала ошибки происходит двухэтапным методом. Каждый этап использует жадную стратегию. На первом этапе выделяется в новый кластер вершина с максимальным количеством инцидентных отрицательных ребер с целью уменьшения внутрикластерной ошибки. На втором этапе путем объединения кластеров минимизируется межкластерная ошибка This paper investigates one of the sign balance problems - the problem of partitioning a sign graph. Similar problems arise in social psychology, in the analysis of multiagent systems, social networks, thematic modeling of texts. The criterion for the quality of sign graph partitioning is the total error function, which is defined as the convex combination of intra-cluster and inter-cluster errors. In this formulation the problem is NP-complete. This paper proposes a polynomial algorithm for solving the sign graph partitioning problem without limitation on the number of clusters. For its work the algorithm takes a graph without any initial partitioning. Minimization of the error function is done by a two-step method. Each stage uses a greedy strategy. At the first stage the node with the maximum number of incident negative edges is allocated to a new cluster in order to reduce the intra-cluster error. The second step minimizes the inter-cluster error by combining clusters. The theorem on the computational complexity of the developed algorithm is proved. Computational experiments demonstrating the effectiveness of the algorithm are presented
Журнал: Системы управления, информационные технологии и математическое моделирование
Номера страниц: 166-172
Место издания: Омск
Издатель: Омский государственный технический университет