Algorithms for calculating network reliability based on the decomposition approach

When designing and developing networks in various spheres of human activity, related, for example, to the telecommunications and banking sectors, order confirmation and creditworthiness systems, and others, an important criterion is their reliability. The task of assessing the reliability of the network arises, as a rule, in two cases: qualitative analysis of existing systems or optimization in the design of new systems. Note also that when formulating this task, it is necessary to determine from which reliability criteria to proceed. In this paper, the classical indicator of its connectivity will be considered as a parameter of network reliability. A mathematical model describing a network is usually a random graph in which the vertices represent the network nodes in question, such as workstations, routers, servers and other devices or structures, and the edges represent the communication channels of these objects. Each element of a random graph is present in it with a certain probability, expressing its reliability. The reliability of the network in this representation will be understood as the probability of connectivity of the vertices of the graph. Next, the paper will consider the problem of calculating the probability of connectivity of an undirected graph with absolutely reliable vertices, the probability of whose presence is equal to one, and unreliable edges, the probabilities of whose presence will be determined by some real numbers from the segment from zero to one. The exact calculation of this indicator is NP-hard problem, which makes it difficult for networks of real dimension. Modifications of the factorization method used for accurate calculation are proposed, based on the decomposition of the network by a vertex cut (section, separator) formed by two vertices. For more efficient use of decomposition, the structural similarity of the resulting subgraphs is taken into account. As well as the graphs obtained from them by gluing the cutting vertices. Three algorithms have been developed that, on average, accelerate the process of calculating the probability of connectivity of an arbitrary graph. To compare the proposed algorithms with the factorization method and the factorization method with preliminary decomposition, the results of numerical experiments are presented.