Применение метрик центральности для поиска критических узлов и оценки их влияния на транспортную сеть

   В работе предлагается методика идентификации критических узлов транспортной сети мегаполиса на основании комбинированной метрики, учитывающей несколько различных показателей центральности графа. Цель исследования заключается в том, чтобы выявить наиболее значимые элементы транспортной инфраструктуры и оценить их влияние на устойчивость системы при возникновении сбоев. Для построения графа дорожной сети использованы инструменты OSMnx и данные OpenStreetMap, прошедшие фильтрацию по автомобильным дорогам, что позволило сформировать адекватную модель улично-дорожной сети города.
   В качестве базовых показателей применены классические метрики центральности: центральность по посредничеству (Betweenness); центральность, основанная на степени узла (Degree); центральность по близости (Closeness); гармоническая центральность (Harmonic), а также метрика по нагрузке (Load). Все метрики нормализованы – приведены к единой шкале для сопоставимости результатов. На их основе предложено использовать интегральную комбинированную метрику, представляющую собой среднее значение нормализованных показателей, что позволяет комплексно учитывать как топологические, так и функциональные свойства узлов.
   Для проверки методики проведено имитационное моделирование, включающее сценарии увеличения весов ребер для эмуляции пробок, а также полное исключение из сети отдельных узлов. Полученные результаты подтвердили, что ключевым фактором остается центральность по посредничеству, однако использование комбинированной метрики дает более устойчивую и сбалансированную оценку. Установлено, что удаление критических узлов существенно увеличивает среднюю длину кратчайших путей, что свидетельствует о высокой уязвимости сети и подчеркивает необходимость приоритизации таких объектов при планировании развития и защите транспортной инфраструктуры.

1. Complexity and Vulnerability Analysis of Critical Infrastructures: A Methodological Approach / Y. Deng, L. Song, Z. Zhou, P. Liu // Hindawi Mathematical Problems in Engineering. 2017. Vol. 2. Р. 1–12. Article ID8673143.

2. Mattsson L., Jenelius E. Vulnerability and resilience of transport systems A discussion of recent research // Transportation Research. Part A. Рolicy and Practice. 2015. Vol. 81. P. 16–34.

3. Крыгин А. А, Куприянов Б. В. Определение критических узлов транспортной сети // Управление большими системами. 2022. Вып. 100. С. 194.

4. Рублева О. Критерий аддитивности конечного метрического пространства // Вестник Московского университета. Математическая механика. 2012. № 2. С. 8–11.

5. Wilson A. G. A statistical theory of spatial distribution models // Transportation Research. 1967. Vol. 1, Iss. 3. Р. 253–269.

6. On Uniqueness in Steiner Problem / M. Basok, D. Cherkashin, N. Rastegaev, Ya. Teplitskaya // International Mathematics Research Notices. 2024. P. 8819–8838. https://doi.org/10.1093/imrn/rnae025.

7. Winter P. Steiner Problem in Networks: A Survey // Networks. 1987. P. 129–167. https://doi.org/10.1002/net.3230170203.

8. Lalou M., Tahraoui M. A., Kheddouci H. The Critical Node Detection Problem in Networks: A Survey // Comp. Sci. Rev. 2018. Vol. 28. P. 92–117. https://doi.org/10.1016/j.cosrev.2018.02.002.

9. A comparative study of robustness measures for cancer signaling networks / Z. Mingxing, L. Jing, W. Shuai, H. Shan // Big Data and Information Analytics. 2017. Vol. 2, Iss. 1. P. 87–96. DOI 10.3934/bdia.2017011.

10. A comparative study of network robustness measures / J. Liu, M. Zhou, S. Wang, P. Liu // Frontiers of Computer Science. 2017. Vol. 11, Iss. 4. P. 568–584. DOI 10.1007/s11704-016-6108-z.

11. Щербакова Н. Г. Меры центральности в сетях // Проблемы информатики. 2015. № 1. С. 18–30.

12. Хабаров В. И., Беков М. А., Квашнин В. Е. Критические объекты транспортной инфраструктуры мегаполисов и агломераций // Вестник Сибирского государственного университета путей сообщения. 2024. № 3 (70). С. 20–27. DOI 10.52170/1815-9265_2024_70_20.

13. Borgatti S., Everett M. A graph-theoretic perspective on centrality // Social Networks. 2006. Part 28. DOI 10.1016/j.socnet.2005.11.005.

14. Stamos I., Paravantis J. A. Transportation Networks in the Face of Climate Change Adaptation: A Review of Centrality Measures // Future Transportation. 2023. Vol. 3 (3). P. 878–900. DOI 10.3390/futuretransp3030049.

15. Holme P. Consistency and differences between centrality measures across distinct classes of networks // PLOS ONE. 2021. Vol. 16 (7). DOI 10.1371/journal.pone.0220061.

16. Boeing G. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks // Computers, Environment and Urban Systems. 2017. Vol. 65. P. 126–139.

17. Pandas: fast, powerful, flexible and easy to use open-source data analysis and manipulation tool // Pandas. URL: https://pandas.pydata.org (дата обращения: 10.10.2024).

18. Numpy: The fundamental package for scientific computing with Python // NumPy. URL: https://numpy.org (дата обращения: 10.10.2024).

19. Freeman L. C. Centrality in Social Networks: Conceptual Clarification // Social Networks. 1979. Vol. 1 (3). P. 215–239. DOI 10.1016/0378-8733(78)90021-7.

20. Hoede C., Bakker R. A Theory of Domination in Graphs // Discrete Mathematics. 1996. Vol. 151 (1-3). P. 207– 214. DOI 10.1016/0012-365X(95)00215-6.

21. Freeman L. C. A Set of Measures of Centrality Based on Betweenness. Sociometry. 1977. Vol. 40 (1). Р. 35– 41. DOI 10.2307/3033543.

22. Беков М. А. Анализ применения методов центральности для поиска критических узлов на примере графа города N // Политранспортные системы : материалы XIII Всероссийской научно-технической конференции с международным участием (24–25 октября 2024 г.) ; Сиб. гос. ун-т путей сообщения. Новосибирск : Изд-во СГУПС, 2024. С. 465–470.