Определение характеристик вершины для снижения размерности задачи нахождения критических узлов сети

Автор(ы): Крыгин А.А., Тарасова С.М.

Выпуск: 118

Рубрика: Управление техническими системами и технологическими процессами

Год: 2025

Библиография: Крыгин А.А., Тарасова С.М. Определение характеристик вершины для снижения размерности задачи нахождения критических узлов сети // Управление большими системами. - 2025. - Вып. 118. - С.325-361.

Дата опубликования: 30.11.2025

Ключевые слова: устойчивость электрических сетей, поиск критических узлов, графовые модели сетей

Аннотация: Одним из актуальных направлений исследования устойчивости сетей является класс задач поиска критических узлов --- наборов узлов, при переходе которых в неработоспособное состояние сети будет нанесен максимальный ущерб. Для решения задач этого класса сеть моделируется в виде невзвешенного и неориентированного графа. Такие модели применяются при исследованиях связности сетей и широко распространенной метрикой оценки ущерба для них является количество связных пар вершин. Набор вершин считается критическим, если в графе, из которого этот набор удален, количество связных пар вершин минимально среди всех наборов такой же мощности. Помимо метода полного перебора для решения этой задачи используется метод сведения ее к эквивалентной задаче линейного программирования. В описываемом исследовании рассматривается метод снижения размерности задачи линейного программирования за счет подбора двух характеристик вершины так, чтобы несколько вершин с наибольшим значением первой характеристики почти всегда являлись критическими (встречались в большинстве решений) и несколько вершин с наименьшим значением второй характеристики почти никогда не являлись критическими. Тогда часть переменных, соответствующих найденным критическим и некритическим вершинам, можно исключить из задачи линейного программирования, что приводит к сокращению ее размерности. Для корректной постановки задачи потребовалось решить ряд подготовительных подзадач, описанных в предыдущей работе. Данная работа посвящена второй, заключительной части исследования.

Author(s): Krygin A., Tarasova S.

Article title: Reduction the dimensionality of the task of finding critical nodes in the network

Issue: 118

Year: 2025

Keywords: resilience of electrical networks, search for critical nodes, graph models of networks

Abstract: One of the current research directions in network robustness is the class of critical node identification problems — sets of nodes whose removal would cause the maximum damage to the network's functionality. To solve problems of this class, the network is modeled as an unweighted, undirected graph. Such models are used in studies of network connectivity, and a widely adopted metric for assessing damage is the number of connected pairs of vertices. A set of vertices is considered critical if, in the graph from which this set is removed, the number of connected vertex pairs is minimized among all sets of the same size. In addition to exhaustive search methods, this problem is often approached by reducing it to an equivalent linear programming problem. The current research examines a method for reducing the dimensionality of the linear programming problem by selecting two vertex characteristics such that several vertices with the highest values of the first characteristic are almost always critical (appear in most solutions), and several vertices with the lowest values of the second characteristic are almost never critical. This allows for the partial exclusion of variables corresponding to the identified critical and non-critical vertices from the linear programming problem, thereby reducing its size. To correctly formulate the problem, a number of preparatory sub-tasks, described in previous work, needed to be addressed. This paper is devoted to the second, final part of the study.