Method for finding cuts for engineering infrastructure management tasks
- Авторлар: Vandilovskaya P.A.1, Krygin A.A.1, Lukinova O.V.1, Roschin A.A.1
-
Мекемелер:
- V.A. Trapeznikov Institute of Control Sciences of RAS
- Шығарылым: № 111 (2024)
- Беттер: 226-246
- Бөлім: Control of technological systems and processes
- URL: https://bakhtiniada.ru/1819-2440/article/view/289122
- DOI: https://doi.org/10.25728/ubs.2024.111.9
- ID: 289122
Дәйексөз келтіру
Толық мәтін
Аннотация
The goal of the functioning of engineering networks is to ensure the delivery of a particular resource to a consumer, ideally with uninterrupted supply which directly depends on the integrity of the network infrastructure. However, various factors such as attacks by malicious actors, natural disasters, and technological accidents can lead to the disconnection of certain parts of the network, resulting in the disruption of resource delivery. This necessitates the task of identifying the most vulnerable parts of the engineering network in terms of potential damage, which allows appropriate measures to be taken to protect the network from negative factors and ensure maximum uninterrupted resource delivery. Engineering networks are commonly modeled as graph structures, therefore one method of solving this task is to find the cuts of the network graph. While such methods exist, they all have certain limitations. This study proposes a new method for finding all cuts of a directed graph of arbitrary dimension, which eliminates these limitations, describes the algorithm for this method, and provides theoretical justification. The concept of the method is based on constructing graph cuts (multicuts) in such a way that all cuts are identified, and can be done in a reasonable amount of time. Examples of engineering networks where this method can be used as a tool for making rational decisions in operating network objects include power grids, transportation networks, water supply and sewerage networks, as well as communication and telecommunications networks.
Негізгі сөздер
Авторлар туралы
Polina Vandilovskaya
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: polinavandi@yandex.ru
Moscow
Andrey Krygin
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: andreyakr14@gmail.com
Moscow
Olga Lukinova
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: lobars@mail.ru
Moscow
Alexander Roschin
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: rochinaa@ipu.ru
Moscow
Әдебиет тізімі
- ГРИШКЕВИЧ А.А., PIATEK L., БУРМУТАЕВ А. Нахождение одно-, двух- и трехэлементных разрезов графа //Вестник ЮрГУ, серия «Математическое моде-лирование и программирование». – 2008. – №15(115). – Вып. 1. – С. 12–22.
- ДОРРИ М.Х., РОЩИН А.А., СЕРЕДА Л.А. Применение программного комплекса РДС для расчетов и визуали-зации последствий выхода из строя инженерных со-оружений // Автоматизация в промышленности. – 2017. – № 11. – С. 11–14.
- РЯБИНИН И.А. Надежность и безопасность структур-но- сложных систем. – СПб.: Изд-во СПб. гос. ун-та, 2007. – 276 с.
- ПОТТОСИН Ю.В., ПОТТОСИНА С.А. Поиск разреза графа в решении некоторых задач логического проекти-рования // Vescì Nacyânalʹnaj akadèmìì navuk Belarusì. Seryâ fìzìka-matèmatyčnyh navuk. – 2016. – №3. – С. 111–118.
- ПИРОВА А.Ю. Параллельные алгоритмы разделения графов: учебное пособие. – Нижний Новгород: Нижего-родский госуниверситет, 2019. – 20 с.
- СВАМИ М., ТХУЛАСИРАМАН К. Графы, сети и алго-ритмы. – М.: Мир, 1984. – 454 с.
- AGUDELO L., MUNOZ N., LÓPEZ-LEZAMA J.M. Vulner-ability assessment of power systems to intentional attacks us-ing a specialized genetic algorithm // Dyna (Medellin, Co-lombia). – 2015. – Vol. 82, Iss. 192. – P. 78–84.
- CAGNO E., GRANDE O., TRUCCO P. Towards an inte-grated vulnerability and resilience analysis for underground infrastructures // Reliability Engineering & System Safety. – 2011. – Vol. 96, Iss. 1. – P. 139–148.
- GREBENYUK G.G., NIKISHOV S.M. Blocking of Energy and Resource Supply of Target Objects in Network Infra-structures // Automation and Remote Control. – 2018. – Vol. 79(3). – P. 535–544.
- HAENNI R. Generating Diagnoses from Conflict Sets // Proc. of the 11th Int. Conf. FLAIRS. – 1998 – URL: ww.aaai.org/Papers/FLAIRS/1998/FLAIRS98-081.pdf (дата обращения: 23.03.2023).
- KARGER D.R. Global Min-cuts in RNC, and Other Ramifi-cations of a Simple Min-Cut Algorithm // SODA: Journal. – 1993. –Vol. 93. –P. 21–30.
- KARIMI E., MADANI S.M., EBRAHIMI A. Power trans-mission system vulnerability assessment using genetic algo-rithm // Intelligent Systems in Electrical Engineering Fall. – 2012. – Vol. 3, No. 3. – P. 1–10.
- KIM T., WRIGHT S.J., BIENSTOCK D. et al. Vulnerability Analysis of Power Systems // IEEE Trans. on Network Sci-ence and Engineering. – 2016. – Vol. 3, Iss. 3. – P. 132–146.
- MAY R.P. Genetic Algorithms for Agent-Based Infrastruc-ture Interdependency Modeling and Analysis. – URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455.354&rep=rep1&type=pdf (дата обращения: 23.03.2023).
- ROSELYNA J.P., DEVARAJB D., DASH S.S. Multi-Objective Genetic Algorithm for voltage stability enhance-ment using rescheduling and FACTS devices // Ain Shams Engineering Journal. – 2014. – Vol. 5, Iss. 3. – P. 789–801.
- STOER M., WAGNER F. A simple min-cut algorithm // Jour-nal of the ACM. – 1997. – Vol. 44(4). – P. 585–591.
- VALENCIA V.V., MAJ P.E. Network Interdependency Modeling for Risk Assessment on Built Infrastructure Sys-tems. – 2013. – URL: https://pdfs.semanticscholar.org/95ba/f36ae65157638a83f82084c39884b3f0fcb2.pdf?ga=2.74081425.2003714931.1570034586-1895369083.1570034586 (дата обращения: 23.03.2023).
Қосымша файлдар
