Інтелектуальна система прогнозування стійкості складних мереж
Автор: Куриляк Юліан Анатолійович
Кваліфікаційний рівень: магістр (ОНП)
Спеціальність: Системний аналіз (освітньо-наукова програма)
Інститут: Інститут комп'ютерних наук та інформаційних технологій
Форма навчання: денна
Навчальний рік: 2022-2023 н.р.
Мова захисту: англійська
Анотація: Розроблено інтелектуальну інформаційну систему оцінювання стійкості складних мереж, їх оптимізації а також прогнозування поведінки в умовах, наближених до реальних. У роботі стійкість мережі поділяється на міцність, тобто стійкість до руйнування мережі та опір, тобто стійкість мережі до процесів поширення у ній певних явищ на зразок вірусів. Для всебічного оцінювання мережі розроблена система застосовує наступні міри стійкості[1]: зв’язність графу мережі, зв’язність вершин та ребер, натуральну зв’язність, алгебраїчну зв’язність, небектрекінгову зв’язність, спетральний радіус, середню відстань, ефективність мережі та коефіцієнт кластеризації. Метою цієї роботи є: розробка інелектуальної системи прогнозування та підвищення стійкості складних мереж шляхом оптмиізації її структури з врахуванням специфічного середовища її функціонування. Об’єктом дослідження є: стійкість складних мереж, тобто їх здатність підтримувати функціонування та задану продуктивність в умовах різних типів вторгнень або збоїв. Предметом дослідження є: методи прогнозування стійкості та оптимізації структури мережі, а також моделювання поведінки мережі в умовах наближених до реальних. Ця система є продуктом, який збирає у собі різні підходи до підвищення стійкості мережі у різних умовах, які користувач може налаштувати самостійно. У системі використано широкий перелік мір стійкості, та надається можливість вибору одночасно мінімізації та максимізації міцності мережі, які система може оцінити за допомогою проведення стохастичного моделювання процесу поширення у ній. Для оптимізації структури мережі визначено задачу багатокритеріальної оптимізації, яка має дві функції мети: максимізація(мінімізація) обраної міри стійкості та мінімізація вартості оптимізації. Визначено обмеження на процеси оптимізації: допустиму вартість оптимізації, допустиму кількість вузлів та ребер які можуть бути додані/видалені у процесі оптимізації. Для розв’язку поставленої задачі застосовано відповідно адаптований генетичний алгоритм. Розроболена модель оптимізації, навідміну від відомих рішень[2,3] дозволяє покращити міцність мережі не лише додаванням нових та перепідклювенням старих ребер мережі, а і передбачає додавання до неї вузлів. Таке розширення у подальшому може бути викорстано для додавання ваг вузлім для відображення їх пропускної чи генеративної здатності і розподілу навантаження на них, а також, коли є обмеження до максимальної довжини ребра, як от у телекомунікаційних мережах, для яких необхідно встановлювати ретранслятори, які у мережі виглядатимуть як вузли. Як бенчмарк, для прогнозування швидкості передачі інформації у мережі використано симулювання процесу поширення на основі ланцюгів Маркова, який був описаний у роботі [4], ефективність якого досягається лише обчисленням переходу у стани, які завідомо мають ненульові ймовірності при переході з поточного стану відповідно до стохастичного алгориму Гіллеспі [5]. Розроблений алгоритм можна використати як для прогнозування наслідків епідемії, так і для оцінки зв’язності мережі та швидкості передачі інформації у ній. Архітектура системи є розподіленою та побудована з наступних функціональних модулів: інтерфейс користувача, оцінювання, оптимізація, бенчмаркінг, бекенд та база даних. Інтерфейс системи реалізовано як веб-сторінку, яка містить усі необхідні форми для введення параметрів для проведення досліджень, а також візуалізацію для спрощення розуміння структури та процесів у складних мережах. Мережу візуалізовано за допомогою інтерактивного графу, який містить всю необхідну інформацію про вузли та ребра, а також графіки, які відображають результати експериментів. Як основну мову для розробки системи використано Python, для роботи з мережами - iGraph, для роботи з генетичним алгоритмом - DEAP, для реалізації інтерфейсу - Dash та Plotly, як систему управління базами даних обрано MongoDB. Система може бути корисною для адміністраторів комп’ютерних, телекомунікаційних, транспортних та інших мереж та їх дослідників, і може бути використана як на етапі як проектування системи, так і експлуатації. Ключові слова: складні мережі, стійкість мережі, міцність мережі, опір мережі, прогнозування стійкості мережі, оптимізація структури мережі. СПИСОК ВИКОРИСТАНИХ ЛІТЕРАТУРНИХ ДЖЕРЕЛ 1. Scott Freitas et al. Graph vulnerability and robustness: A survey. IEEE Transactions on Knowledge and Data Engineering (2022). 2. D. T. Gillespie. Stochastic simulation of chemical kinetics. Annu. Rev. Phys. Chem. 58 (2007), pp. 35–55. 3. Yulian Kuryliak, Michael Emmerich, and Dmytro Dosyn. Efficient Stochastic Simulation of Network Topology Effects on the Peak Number of Infections in Epidemic Outbreaks. arXiv preprint arXiv:2202.13325 (2022). 4. Xiaoke Zhang et al. Towards robustness optimization of complex networks based on redundancy backup In: 2015 IEEE Congress on Evolutionary Computation (CEC). IEEE. 2015, pp. 2820–2826. 5. Jichang Zhao and Ke Xu. Enhancing the robustness of scale-free networks. Journal of Physics A: Mathematical and Theoretical 42.19 (2009), p. 195003.