Библиографическое описание:МОДИФИКАЦИЯ АЛГОРИТМА SGCLUSTα ДЛЯ ЗАДАЧИ КЛАСТЕРИЗАЦИИ ЗНАКОВОГО ГРАФА : доклад, тезисы доклада / Э. И. Ибрагимова, Д. В. Семенова, А. А. Солдатенко. - [Б. м. : б. и.], 2022. - Текст : непосредственный // Системы управления, информационные технологии и математическое моделирование : Материалы IV Всероссийской научно-практической конференции с международным участием. В 2-х томах / Отв. редактор В.Н. Задорожный ; Системы управления, информационные технологии и математическое моделирование (2022 ; 19.05 - 19.05 ; Омск). - Омск : Омский государственный технический университет, 2022. - I. - С. 166-172. - ISBN 978-5-8149-3487-1, DOI 10.25206/978-5-8149-3487-1-2022-1-166-172. Перевод заглавия: MODIFICATION OF THE ALGORITHM SGCLUSTα FOR THE SIGN GRAPH CLUSTERING PROBLEM
Аннотация:В работе исследуется одна из задач знакового баланса задача разбиения знакового графа. Критерием качества разбиения знакового графа является функция суммарной ошибки, которая определяется как выпуклая комбинация внутрикластерной и межкластерной ошибок. Данная задача является 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
