Анализ способов снижения устойчивости сетей на основе последовательного удаления ключевых элементов

Семенов К.В., Шуваев Ф.Л., Витензон К.И. Анализ способов снижения устойчивости сетей на основе последовательного удаления ключевых элементов // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 2. С. 241–248. doi: 10.17586/2226-1494-2021-21-2-241-248

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

1. Ashtiani M., Salehzadeh-Yazdi A., Razaghi-Moghadam Z., Hennig H., Wolkenhauer O., Mirzaie M., Jafari M. A Systematic survey of centrality measures for protein-protein interaction networks // BMC Systems Biology. 2018. V. 12. N 1. P. 80. doi: 10.1186/s12918-018-0598-2
2. Еремеев И.Ю., Татарка М.В., Шуваев Ф.Л., Цыганов А.С. Анализ мер центральности узлов сетей на основе метода главных компонент // Информатика и автоматизация. 2020. Т. 19. № 6. С. 1307–1331. doi: 10.15622/ia.2020.19.6.7
3. Singer Y. Dynamic measure of network robustness // Proc. IEEE 24^th Convention of Electrical & Electronics Engineers in Israel. 2006. P. 366–370. doi: 10.1109/EEEI.2006.321105
4. Mingxing Z., Jing L., Shuai W., Shan H. A comparative study of robustness measures for cancer signaling networks // Big Data and Information Analytics. 2017. V. 2. N 1. P. 87–96. doi: 10.3934/bdia.2017011
5. Liu J., Zhou M., Wang S., Liu P. A comparative study of network robustness measures // Frontiers of Computer Science. 2017. V. 11. N 4. P. 568–584. doi: 10.1007/s11704-016-6108-z
6. Витензон К.И., Вышинский А.П., Колесник А.В. Методика оценивания структурной устойчивости системы спутниковой связи с учетом важности передаваемой информации // Труды Военно-космической академии им. А.Ф. Можайского. 2019. № 667. С. 74–79.
7. Barabási A.-L. Network Science. Glasgow: Cambridge University Press, 2016. 453 p.
8. Шуваев Ф.Л., Татарка М.В. Анализ математических моделей случайных графов, применяемых в имитационном моделировании информационно-коммуникационных сетей // Вестник Санкт-Петербургского университета ГПС МЧС России. 2020. № 2. С. 67–77.
9. Newman M.E.J. Networks: An Introduction. N.Y.: Oxford University Press Inc., 2010. 1042 p.
10. Hartmann A., Mézard M. Distribution of diameters for Erdős-Rényi random graphs // Physical Review E. 2018. V. 97. N 3. P. 032128. doi: 10.1103/PhysRevE.97.032128
11. Csardi G., Nepusz T. The igraph software package for complex network research // InterJournal Complex Systems. 2006. V. 1695.
12. Lê S., Josse J., Husson F. FactoMineR: An R package for multivariate analysis // Journal of Statistical Software. 2008. V. 25. N 1. P. 1–18. doi: 10.18637/jss.v025.i01
13. Bonchi F., De Francisci Morales G., Riondato M. Centrality measures on big graphs: Exact, approximated, and distributed algorithms // Proc. of the 25^th International Conference Companion on World Wide Web. 2016. P. 1017–1020. doi: 10.1145/2872518.2891063
14. Brandes U., Borgatti S., Freeman L. Maintaining the duality of closeness and betweenness centrality // Social Networks. 2016. V. 44. P. 153–159. doi: 10.1016/j.socnet.2015.08.003
15. Шевченко Д.Н., Литвин А.Ю., Федянин М.А. Имитационное моделирование графа состояний в задачах анализа надежности технических систем // Проблемы физики, математики и техники. 2018. № 3(36). С. 101–104.
16. Chen P.-Y., Choudhury S., Hero A.O. Multi-centrality graph spectral decompositions and their application to cyber intrusion detection // Proc. 41^st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2016. P. 4553–4557. doi: 10.1109/ICASSP.2016.7472539
17. Шуваев Ф.Л., Татарка М.В. Анализ динамики мер центральности математических моделей случайных графов // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 2. С. 249–256. doi: 10.17586/2226-1494-2020-20-2-249-256
18. Gibson H., Vickers P. Using adjacency matrices to lay out larger small-world networks // Applied Soft Computing Journal. 2016. V. 42. P. 80–92.doi: 10.1016/j.asoc.2016.01.036
19. Faust K. Comparing social networks: Size, density, and local structure // Metodološki zvezki. 2006. V. 3. N 2. P. 185–216.
20. HolmeP., Kim B.J., Yoon C.N., Han S.K. Attack vulnerability of complex networks // Physical Review E. 2002. V. 65. N 5. P. 056109. doi: 10.1103/PhysRevE.65.056109
21. Lu Z.-M., Li X.-F. Attack vulnerability of network controllability // PLoS One. 2016. V. 11. N 9. P. e0162289. doi: 10.1371/journal.pone.0162289
22. Dong S., Mostafizi A., Wang H., Gao J., Li X. Measuring the topological robustness of transportation networks to disaster-induced failures: a percolation approach // Journal of Infrastructure Systems. 2020. V. 26. N 2. P. 04020009. doi: 10.1061/(ASCE)IS.1943-555X.0000533

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