Reduction the dimensionality of the task of finding critical nodes in the network

Cover Page

Cite item

Full Text

Abstract

One of the classes of problems solved in the assessment of the stability of an engineering network is the problem of finding critical nodes. In many formulations, this problem is posed as finding a subset of nodes of a given cardinality (critical nodes) such that the failure of which would cause maximum damage to the entire network. And the most common way to assess the damage in such a formulation is to determine the number of connected node pairs in the network with excluded critical nodes. For such nodes that correspond to the minimum number of connected pairs, additional measures are required to increase reliability and safety. Several methods of solving the problem of finding critical nodes use reducing it to an equivalent linear programming problem. The main problem of this approach is the large size of the problem, and consequently, the high computational complexity of its solution. The work conducts research on various characteristics of vertices of a graph model of a network, the analysis of the values of which will allow determining in advance the fact of belonging to the subset of critical or, conversely, to the subset of non-critical nodes. Thanks to this, it is possible to form additional constraints that reduce the dimensionality of the linear programming problem and its computational complexity, which will allow finding critical nodes in engineering networks with a large number of objects in an acceptable time. During the research, a large number of different subproblems were solved, so the work describes only the first, preparatory part of it.

About the authors

Andrey Aleksandrovich Krygin

V.A. Trapeznikov Institute of Control Sciences of RAS

Email: andreyakr@yandex.ru
Moscow

Sofia Mikhaylovna Tarasova

V.A. Trapeznikov Institute of Control Sciences of RAS

Email: tarasva\_sofia@mail.ru
Moscow

References

  1. Минпросвещения России. – Режим доступа: https://edu.gov.ru/modernization (дата обращения: 22.05.2024).
  2. Перспективы применения комплексов альтернативнойэнергии на примере республики Таджикистан. – Режимдоступа: https://research-journal.org/archive/10-64-2017-october/perspektivy-primeneniya-kompleksov-alternativnoj-energii-na-primere-respubliki-tadzhikistan (дата обращения:21.05.2024).
  3. Программа реновации. Итоги и планы на 2024 г. – Ре-жим доступа: https://www.sobyanin.ru/programma-renovatsii-itogi-i-plany-na-2024(дата обращения: 22.05.2024).
  4. ХАЧИЯН Л.Г. О точном решении систем линейных нера-венств и задач линейного программирования // Вычисл. ма-тем. и матем. физ. – 1982. – №22(4). – С. 999–1002.
  5. Электроэнергия в Беларуси: распределение – ста-тьи энергетической тематики. – Режим доступа:https://energobelarus.by/blogs/Energy_dis-senting_opinion/19/(дата обращения: 21.05.2024).
  6. BECZI E., GASKO N. Approaching the bi-objective criticalnode detection problem with a smart initialization-basedevolutionary algorithm // Peer Computer Science. – 2021. –Vol. 7. – P. 750–758.
  7. BONNANS J.F., GILBERT J.C., LEMARECHAL C. et al.Numerical optimization: Theoretical and practical aspects. –Springer Berlin–Heidelberg, 2006. – Vol. 51. – P. 494–495.
  8. CHEN W., JIANG M., JIANG C. et al. Critical node detectionproblem for complex network in undirected weighted networks //Physica A: Statistical Mechanics and its Applications. – 2020. –Vol. 538. – P. 11–45.
  9. DINH T.N., XUAN Y., THAI M.T. et al. On NewApproaches of Assessing Network Vulnerability: Hardness andApproximation // IEEE ACM Trans. on Networking. – 2012. –Vol. 20(2). – P. 609–619.
  10. GLORY U.A., ARULSELVAN A., AKARTUNALI K. et al.Efficient methods for the distance-based critical node detectionproblem in complex networks // Computers and OperationsResearch. – 2021. – Vol. 131. – P. 108–121.
  11. HOOSHMAND F., MIRARABRAZI F., MIRHASSANI S.A.Efficient Benders decomposition for distance based criticalnode detection problem // Omega. – 2020. – Vol. 93. – P. 16–31.
  12. LALOU M., KHEDDOUCI H. Network VulnerabilityAssessment Using Critical Nodes Identification // Int.Symposium on Networks, Computers and Communications(ISNCC). – 2023. – P. 1–6.
  13. LIU C., GE G., ZHANG Y. Identifying the cardinality-constrained critical nodes with a hybrid evolutionaryalgorithm // Information Sciences. – 2023. – Vol. 642. –P. 24–41.
  14. MEGZARI A., PRAVIJA RAJ P.V., OSAMY W. Applications,challenges, and solutions to single- and multi-objective criticalnode detection problems: a survey // J. Supercomput. – 2023. –Vol. 79. – P. 19770–19808.
  15. MUNIKOTI S. ,DAS L., NATARAJAN B. Scalable graphneural network-based framework for identifying critical nodesand links in complex networks // Neurocomputing. – 2023. –Vol. 422. – P. 211–221.
  16. SALEMI H., BUCHANAN A. Solving the Distance-BasedCritical Node Problem // INFORMS Journal on Computing. –2022. – Vol. 34(3). – P. 1309–1326.
  17. SHEN S., SMITH J.C., GOLI R. Exact interdiction modelsand algorithms for disconnecting networks via node deletions //Discrete Optimization. – 2012. – Vol. 9. – P. 172–188.
  18. SHEN Y., NGUYEN N.P., XUAN Y. et al. On the Discovery ofCritical Links and Nodes for Assessing Network Vulnerability //IEEE/ACM Trans. on Networking. – 2013. – Vol. 21. –P. 963–973.
  19. THAI M.T., DINH T.T., SHEN Y. Hardness and Approximationof Network Vulnerability // Handbook of CombinatorialOptimization. – 2013. – Vol. 5. – P. 1631–1666.
  20. UGURLU O., AKRAM N., AKRAM V.K. Critical nodesdetection in IOT-based cyber-physical systems: Applications,methods, and challenges // Emerging trends in IoT andintegration with data science, cloud computing, and big dataanalytics. – 2022. – Vol. 2022. – P. 226–239.
  21. VEREMYEV A., PROKOPYEV O.A, PASILIAO E.L. Criticalnodes for distance-based connectivity and related problems ingraphs // Networks. – 2015. – Vol. 66. – P. 170–195.
  22. WALTEROS J.L., VEREMYEV A., PARDALOS P.M. et al.Detecting critical node structures on graphs: A mathematicalprogramming approach // Networks. – 2018 – Vol. 73. –P. 48–88.
  23. XU Y., GUO P. MEA-CNDP: A Membrane EvolutionaryAlgorithm for Solving Biobjective Critical Node DetectionProblem // Computational Intelligence and Neuroscience. –2021 – Vol. 2021. – P. 101–118.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».