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.

Согласие на обработку персональных данных

 

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