Інтелектуальна система прогнозування стійкості складних мереж

Abstract

Розроблено інтелектуальну інформаційну систему оцінювання стійкості складних мереж, їх оптимізації а також прогнозування поведінки в умовах, наближених до реальних. У роботі стійкість мережі поділяється на міцність, тобто стійкість до руйнування мережі та опір, тобто стійкість мережі до процесів поширення у ній певних явищ на зразок вірусів. Для всебічного оцінювання мережі розроблена система застосовує наступні міри стійкості[1]: зв’язність графу мережі, зв’язність вершин та ребер, натуральну зв’язність, алгебраїчну зв’язність, небектрекінгову зв’язність, спетральний радіус, середню відстань, ефективність мережі та коефіцієнт кластеризації. Метою цієї роботи є: розробка інелектуальної системи прогнозування та підвищення стійкості складних мереж шляхом оптмиізації її структури з врахуванням специфічного середовища її функціонування. Об’єктом дослідження є: стійкість складних мереж, тобто їх здатність підтримувати функціонування та задану продуктивність в умовах різних типів вторгнень або збоїв. Предметом дослідження є: методи прогнозування стійкості та оптимізації структури мережі, а також моделювання поведінки мережі в умовах наближених до реальних. Ця система є продуктом, який збирає у собі різні підходи до підвищення стійкості мережі у різних умовах, які користувач може налаштувати самостійно. У системі використано широкий перелік мір стійкості, та надається можливість вибору одночасно мінімізації та максимізації міцності мережі, які система може оцінити за допомогою проведення стохастичного моделювання процесу поширення у ній. Для оптимізації структури мережі визначено задачу багатокритеріальної оптимізації, яка має дві функції мети: максимізація(мінімізація) обраної міри стійкості та мінімізація вартості оптимізації. Визначено обмеження на процеси оптимізації: допустиму вартість оптимізації, допустиму кількість вузлів та ребер які можуть бути додані/видалені у процесі оптимізації. Для розв’язку поставленої задачі застосовано відповідно адаптований генетичний алгоритм. Розроболена модель оптимізації, навідміну від відомих рішень[2,3] дозволяє покращити міцність мережі не лише додаванням нових та перепідклювенням старих ребер мережі, а і передбачає додавання до неї вузлів. Таке розширення у подальшому може бути викорстано для додавання ваг вузлім для відображення їх пропускної чи генеративної здатності і розподілу навантаження на них, а також, коли є обмеження до максимальної довжини ребра, як от у телекомунікаційних мережах, для яких необхідно встановлювати ретранслятори, які у мережі виглядатимуть як вузли. Як бенчмарк, для прогнозування швидкості передачі інформації у мережі використано симулювання процесу поширення на основі ланцюгів Маркова, який був описаний у роботі [4], ефективність якого досягається лише обчисленням переходу у стани, які завідомо мають ненульові ймовірності при переході з поточного стану відповідно до стохастичного алгориму Гіллеспі [5]. Розроблений алгоритм можна використати як для прогнозування наслідків епідемії, так і для оцінки зв’язності мережі та швидкості передачі інформації у ній. Архітектура системи є розподіленою та побудована з наступних функціональних модулів: інтерфейс користувача, оцінювання, оптимізація, бенчмаркінг, бекенд та база даних. Інтерфейс системи реалізовано як веб-сторінку, яка містить усі необхідні форми для введення параметрів для проведення досліджень, а також візуалізацію для спрощення розуміння структури та процесів у складних мережах. Мережу візуалізовано за допомогою інтерактивного графу, який містить всю необхідну інформацію про вузли та ребра, а також графіки, які відображають результати експериментів. Як основну мову для розробки системи використано Python, для роботи з мережами - iGraph, для роботи з генетичним алгоритмом - DEAP, для реалізації інтерфейсу - Dash та Plotly, як систему управління базами даних обрано MongoDB. Система може бути корисною для адміністраторів комп’ютерних, телекомунікаційних, транспортних та інших мереж та їх дослідників, і може бути використана як на етапі як проектування системи, так і експлуатації.

An intelligent information system for assessing the resilience of complex networks, their optimization, and predicting behavior in conditions close to real ones has been developed. In the paper, network resilience is divided into robustness, that is, resistance to network destruction, and resistance, that is, network resistance to the spread of certain phenomena in it, such as viruses. For a comprehensive assessment of the network, the developed system uses the following robustness measures[1]: connectivity of the network graph, connectivity of vertices and edges, natural connectivity, algebraic connectivity, non-backtracking connectivity, spectral radius, average distance, network efficiency and clustering coefficient. The purpose of this work is the development of an intellectual system of predicting and increasing the resilience of complex networks by optimizing its structure taking into account the specific environment of its operation. The object of the study is: the resilience of complex networks, that is, their ability to maintain functioning and the given performance in the conditions of various types of intrusions or failures. The subject of the research is: methods of predicting resilience and optimizing the structure of the network, as well as modeling the behavior of the network in conditions close to real ones. This system is a product that combines different approaches to increase network resilience in different conditions, which the user can configure independently. The system uses a wide list of robustness measures, and it is possible to simultaneously minimize and maximize the robustness of the network, which the system can estimate using stochastic modeling of the propagation process in it. To optimize the network structure, a multi-objective optimization problem was defined, which had two goal functions: maximization (minimization) of the selected measure of stability and minimization of the optimization cost. Restrictions on optimization processes were defined: the allowable cost of optimization, the allowable number of nodes and edges that can be added/deleted during the optimization process. An appropriately adapted genetic algorithm was used to solve the given problem. The developed optimization model, unlike known solutions[2,3], allows to improve the strength of the network not only by adding new and reconnecting old edges of the network, but also involves adding nodes to it. Such an extension can later be used to add weights to nodes to reflect their throughput or generation capacity and to distribute the load on them, as well as when there is a limit to the maximum edge length, such as in telecommunication networks, for which it is necessary to install repeaters that are in the network will be considered as nodes. As a benchmark, to predict the speed of information spreading in the network, the simulation of the propagation process based on continuous-time Markov chains was used, which was described in [4], the efficiency of which is achieved only by calculating the transition to states that are known to have non-zero probabilities when transitioning from the current state according to the stochastic Gillespie's algorithm [5]. The developed algorithm can be used both for predicting the consequences of the epidemic and for assessing the connectivity of the network and the speed of information spreading in it. The system architecture is distributed and built from the following functional modules: user interface, evaluation, optimization, benchmarking, backend, and database module. The system interface is implemented as a web page, which contains all the necessary forms for entering parameters for conducting research, as well as visualization to simplify the understanding of the structure and processes in complex networks. The network is visualized using an interactive graph that contains all the necessary information about nodes and edges, as well as graphs that display the results of experiments. Python was used as the main language for system development, iGraph for working with networks, DEAP for working with the genetic algorithm, Dash and Plotly for the interface implementation, and MongoDB as the database management system. The system can be useful for administrators of social, computer, telecommunication, transport and other networks and their researchers, and can be used both at the stage of system design and operation.