doi: 10.17586/2226-1494-2021-21-2-241-248


УДК 004.942

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

Семенов К.В., Шуваев Ф.Л., Витензон К.И.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:

Семенов К.В., Шуваев Ф.Л., Витензон К.И. Анализ способов снижения устойчивости сетей на основе последовательного удаления ключевых элементов // Научно-технический вестник информационных технологий, механики и оптики. 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 24th 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 25th 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. 41st 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


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2021 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика