Modeling the survivability of network structures © Alexander Dodonov [0000-0001-7569-9360], © Dmytro Lande [0000-0003-3945-1178] Institute for Information Recording of NAS of Ukraine, Kyiv, Ukraine dodonov@ipri.kiev.ua, dwlande@gmail.com Abstract. The paper describes the models of systems and investigates their struc- tural survivability. A threshold estimate of the system survivability is introduced. This estimate depends on the size of the largest connected component of the net- work model after a destructive impact on it. This estimate is more complex than the canonical structural survivability index, where only the disruption of network connectivity is taken into account. The state of networks with different topology is investigated when their elements (links) are removed. The introduced indicator depends on the network topology and its size, at the same time, it is well approx- imated by cubic polynomials. Keywords: Survivability modeling, Structural reliability, Canonical survivabil- ity, Network model, Connectivity component, Survivability index. 1 Formulation of the Problem The most important fundamental properties of systems include survivability - the ability of systems to adapt to new operating conditions, to withstand adverse influences in the implementation of the main target function. There are several types of system surviva- bility: structural, functional, informational. This work is devoted to modeling the structural survivability of systems. In many cases, survivability is described as a qualitative property that does not lend itself to precise quantitative description. One of the tasks of this work is to give a clear quanti- tative assessment of survivability. Structural survivability is considered as the property of a system to maintain its func- tionality while passively resisting damage to individual elements. In a particular case, when the process of system elements destruction is specified, structural survivability is considered as structural reliability. Structural reliability criterion – the number of failed elements that do not violate the system performance in case of failure of any k system elements [1]. 2 Generally accepted models The scheme of functioning of a complex system can be specified using a network, a set of nodes and connections, which determines the physical structure of this system. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 2 In the generally accepted models [2], it is assumed that the removal of all links inci- dent to a certain node isolates it, interrupting all paths to other nodes - the network becomes disconnected, and the survivability of the network is zero. In this work, another criterion is adopted, a threshold one, namely, the size of the largest connected network component is considered. The connectivity of the entire net- work may be violated, but the system remains functionally capable if the corresponding maximum connected component in terms of volume (number of nodes) is not less than a certain predetermined threshold. Of course, based on this criterion, a complete graph will always be the most surviv- ability, however, it is not obvious what kind of networks, for example, the Erdös-Renyi, Barabási-Albnetwork, the small world network, quasi-hierarchical networks, etc. will be the most survivability. Finding out these facts can be of great importance, for exam- ple, when building security systems or organizational management systems. This paper examines how the probability of failure of the entire system varies from the probability of removing individual links in the network corresponding to the system for three reference networks with different topologies. The networks can then be ranked according to the level of structural survivability. In the works [3], [4], a canonical definition of the property of network survivability is proposed, in which destruction of individual links (graph edges) does not lead to a loss of connectivity. The canonical survivability of the network R(G, p) is defined as the probability that the graph (network G) remains connected after each link (edge) is removed with the same probability p. R(G, p) can be calculated by enumerating the skeletons of G. In practice, canonical survivability is closely related to the Tutte-Whitney polynomial TG , which is a graph invariant describing its combinatorial properties. The Tutte-Whitney polynomial [5] depends on two variables, is defined for any un- directed graph, and contains information about the graph connectivity. The Tutte-Whit- G  V , E  ney polynomial for an undirected graph is defined as follows: TG ( x, y)   A E ( x  1)k ( A)  k ( E ) ( y  1)k ( A) | A||V | , k ( A) (V , A) where denotes the number of the graph connected components . It can be TG seen from the definition that the polynomial is completely defined and polynomial in x and y. For any graph it is true: TG (1,1) 1. is equal to the number of spanning forests; TG (1, 2) 2. is equal to the number of subgraphs G with the same number of con- nected components as G; TG (2,1) 3. equals the number of acyclic subgraphs G. Quite simply, the Tutte-Whitney polynomials are calculated for the simplest "regular" network structures, here are the known results: 3 T ( x, y)  x n 1 . The Tutte-Whitney polynomial for a tree G with n nodes: G The Tutte-Whitney polynomial for a cycle G  Z with n nodes: n TZn ( x, y )  y  x    x n 1 . The Tutte-Whitney polynomial for a complete graph: n Fn ( x, y)   Ckn11 ( x  y  y 2    y k 1 ) Fk 1 (1, y ) Fn  k ( x, y). k 1 R(G, p) The relationship between the canonical survivability and the Tutte-Whit- ney polynomial is given by the equality:  1 R (G , p )  (1  p )|V | k ( G ) p| E ||V | k ( G )TG  1,  .  p The exact calculation of the canonical survivability of a system is an NP-hard prob- lem, the cost of solving which increases exponentially with the growth of the number of nodes and links, since to calculate the survivability of a polynomial of a graph con- sisting of n edges, it is necessary to walk through all spanning subgraphs of graph G [6 ]. Therefore, in many works, alternative approximate approaches are proposed for as- sessing the survivability of systems, in particular, models based on an artificial neural network [7]. Neural networks have high performance due to the use of massive paral- lelism of information processing. 3 Reference networks For modeling, three artifact networks are investigated as an example, namely, the Bara- bási-Albert, Erdös-Renyi and Watts-Strogatz networks. These networks can be consid- ered as prototypes of many real networks. 3.1 Barabási-Albert network: model of preferential connection Most real artifact networks have a power-law distribution. It turned out that this distri- bution is due to an effect called the cumulative advantage or preferential attachment. Power-law networks include Barabási-Albert networks. To build these networks, a special procedure is used, which consists in the fact that new nodes are gradually added to the initially small number of nodes, links from which are more likely to connect to those nodes that have more links. That is, in the process of network growth, new nodes are more likely to form connections with those nodes that are already characterized by a large number of connections. 4 It has been proven that it is the “rich getting richer” phenomenon that leads to the emergence of power laws in networks [8]). Obviously, when a new node joins the net- work, only one link is used, i.e. the number of edges in the network is comparable to the number of nodes, and the network is quasi-hierarchical (the hierarchy can be vio- lated only in the initial composition of nodes). The Barabási-Albert preferred join model is implemented, in particular, in the R language in the igraph package using the barabasi.game() function [9] (Fig. 1). Fig. 1. Barabási-Albert network 3.2 Erdös-Renyi network The Erdős-Renyi network [10] can be constructed by randomly distributing M connec- tions between N nodes. It is sometimes called the Poisson random graph model because of the Poisson degree distribution for N  , or sometimes just the random graph model. This model is equivalent to a model in which the value of the number of edges M is replaced by the corresponding probability p of a new edge appearing in the graph. The random graph model is implemented in the R language in the igraph package using the erdos.reny.game() function (Fig. 2). 3.3 Small World Network D.J. Watts and S. Strogatz discovered a phenomenon common to many real-world net- works called the Small Worlds effect [11]. They proposed a procedure for constructing a visual network model, which is inherent in this phenomenon. This model is a one-dimensional regular lattice consisting of N nodes, where each node is connected only to its 4 nearest neighbors and periodic boundary conditions are imposed – the lattice is folded into a ring. 5 Fig. 2. Erdös-Renyi network p Then the following procedure is performed: with a probability , a rewiring of a small number of links (edges) occurs, during which they are removed and replaced by other links connecting two randomly selected nodes. In the initial state of this network – it is regular – each node of which is connected to four neighboring ones. Then, in this network, some "near" connections are randomly replaced by "distant" ones – it is in this state that the phenomenon of "small worlds" p  (0.01, 0.1) arises (it is clearly expressed at ). p With a further increase , a network is formed that is close in properties to the Erdős-Renyi random network. To build a small world network in the R programming language, the watts.strogatz.game() function of the igraph library is called (Fig. 3). Fig. 3. Small World network 6 4 Suggested method In contrast to the methods presented above, which certainly deserve attention, this work proposes an approach based on simulation modeling. The advantages of this approach are obvious: the proposed procedural model is universal and applicable to any graph. The following approach to modeling the system survivability is implemented: S  (V , E ) 1. System model - a graph consisting of nodes and links (undirected) . Nodes - homogeneous functional components. 2. "Power" of the system - the number of nodes in the largest connected component Vs . 3. The system is in the “live” state, functionally capable, if the specific “power” of V V  the system is not less than a certain threshold  , ie. s o , where Vo is the initial size of the network. 4. A destructive effect is made on the links (edges) of the network. Each link can be removed with probability p . For each specific system, you can determine the measure of system survivability at a given threshold  , i.e. the probability of removing individual elements (links) p * , V V  at which the system leaves the "alive" state, i.e. s o . 5 Model analysis The model is implemented as a discrete process, at each step one link is removed from the selected network. At the same time, the number of nodes in the largest connected component was recalculated each time. Those. at a step s , this value will be Vs , which is equivalent to the state of the system with the simultaneous removal of edges with probability p  s / M . Simulation modeling of the process of destruction of three networks, namely, Bara- bási-Albert, Erdös-Renyi, Watts-Strogatz, was carried out. Modeling was carried out in the R programming language using the igraph library. The source codes of programs in the R language are given in Appendix 1 (network mapping) and Appendix 2 (study of the dependence of the "power" of the system de- pending on the iteration step – the number of removed edges). The simulation results are shown in Table 1 and in Fig. 4-6. If you set the destruction threshold, for example, as follows, the network is functional, if the size of the largest connected component Vs is 0.2 of the initial size of the network V0 | V | Vo   ,   0.2 , i.e.: s then, accordingly, we get the values of the threshold probability for networks: Erdős-Renyi: ≈ 0.8 Watts- Strogatz: ≈ 0.7 Barabási-Albert: ≈ 0.5. 7 Table 1. The simulation results Model name Parameters Regression formula Precision R2 Erdős-Renyi N=200, –3*10-8x3 + 10-5x2 – 0.99 M=500 0.0011x + 1.0091 Watts-Strogatz N=200 10-7x3 – 6*10-5x2 + 0.99 0.0061x + 0.8768 Barabási-Albert N=200 –4*10-7x3 + 0.0001 x2 – 0.97 0.0187x + 1.0029 Fig. 4. "Power" of the Erdös-Renyi network (of the network vertical axis) versus the number of remote connections (horizontal axis) Fig. 5. "Power" of the Watts-Strogatz network (vertical axis) versus the number of remote con- nections (horizontal axis) 8 Fig. 6. "Power" of the Barabási-Albert network (vertical axis) versus the number of remote con- nections (horizontal axis) As you can see, in each case, the curves are approximated with high accuracy by cubic polynomials, i.e. for an exact approximation three degrees of the Tutte-Whitney poly- nomial are sufficient. Taking into account the network topology and the analytical es- timates given earlier, we can conclude that the greatest structural survivability among the three considered networks is inherent in the Erdős-Renyi random network (in the case under consideration, this network has the largest number of edges). In second place is the small world network, this network in which the nodes have an average power of 2 with a distribution close to Poisson. And the worst survivability indicators are for the Barabási-Albert network, which is quasi-hierarchical. It should be noted that in the latter case, in contrast to the others, there is a "convex down" function of survivability, which indicates that the "power" considered in this work sharply de- creases even at low values of the probability of destructive influences (removal of links). 6 Conclusions In this work, a new indicator of the structural survivability of the network structure was introduced, which is based on the specific size of the maximum component of the net- work connectivity under a destructive effect on it. This indicator (the threshold probability of removing individual edges) is more com- plex than the canonical structural survivability indicator, which takes into account only the network connectivity violation. Obviously, the introduced indicator depends on the network topology and its size, at the same time, it is well approximated even by cubic polynomials. The development of the proposed model is possible by taking into account the ine- quality of the nodes of the network model and / or changing the "power" function of the network structure. Also, the considered model can be expanded in the direction of 9 accounting for networks in which links are not completely deleted, but "regenerated", or new links can be established. References 1. Velychko V.V., Popkov G.V., Popkov V.K. Models and methods for increasing the surviv- ability of modern communication systems. – Moscow: Hotline-Telecom, 2014. – 270 pp. 2. Synthesis and analysis of the survivability of network systems: monograph / Yu. Yu. Gromov, V.O. Drachev, K.A.Nabatov, O.G. Ivanova. – Moscow: Publishing house Mechan- ical engineering -1, 2007. – 152 pp. 3. Oxley, J.G. Matroid Theory / J.G. Oxley. – Oxford Science Publications, 1992. 4. Sekine, K. Computing the Tutte Polynomial of a Graph of Moderate Size / K. Sekine, H. Imai, S. Tani // Proceedings of the 6th International Symposium on Algorithms and Com- putation (ISAAC'95), Lecture Notes in Computer Science, 1995. 1004. 224 – 233. 5. Tutte, W.T. A Contribution to the Theory of Chromatic Polyno-mials. Canadian Journal of Mathematics, 1954. 6. 80-91. 6. Don T. Phillips; Alberto Garsia-Diaz. Fundamentals of Network Analysis. Prentice Hall, Englewood Cliffs, NJ, 1981, 474 pp. 7. Dolgov A.A. Investigation of the viability of network information systems using neural network models. Psychological and pedagogical journal Gaudeamus,№2 (16), 2010. – pp. 285-287. 8. Albert-László Barabási & Réka Albert. Emergence of scaling in random networks. Science, 1999. 286, 5439. 509-512. 9. Douglas A. Luke. A User’s Guide to Network Analysis in R. Springer International Pub- lishing Switzerland, 2015. DOI: https://doi.org/10.1007/978-3-319-23883-8 10. Erdős, P.; Rényi, A. On Random Graphs. I. Publicationes Mathematicae, 1959. 6: 290– 297. 11. Watts D.J., Strogatz S.H. Collective dynamics of “small-world” networks. // Nature, 1998. 393. 440-442. 10 Appendix 1. The source code of the program in the R language for displaying the Barabási-Albert network library("igraph") g <- barabasi.game(200, directed = FALSE) V(g)$color <- "yellow" V(g)[degree(g) > 6] $color <- "red" rescale <- function(nchar,low,high) { min_d <- min(nchar) max_d <- max(nchar) rscl <- ((high-low)*(nchar-min_d))/(max_d-min_d)+low rscl } node_size <- rescale(degree(g), 3, 12) plot(g, vertex.label = NA, vertex.size = node_size) Appendix 2. The source code of the program for studying the dependence of the "power" of the network depending on the iteration step (Barabási-Albert network) library("igraph") N=200 g <- barabasi.game(N, directed = FALSE) d=1 t=components(g)[2] r[d]=max(t[[1]])/N print("D: ") print(d) print(r[d]) X=N*N for (i in 1:X) { u=round((N-1)*runif(1))+1 v=round((N-1)*runif(1))+1 if (g[u,v]>0) { g[u,v]=0 d=d+1 t=components(g)[2] r[d]=max(t[[1]])/N print("D: ") print(d) print(r[d]) } } plot(r,type="l")