The paper describes the models of systems and investigates their structural survivability. A threshold estimate of the system survivability is introduced. This estimate depends on the size of the largest connected component of the network 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 approximated by cubic polynomials.
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.
In the generally accepted models [
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 network 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 survivability, 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 example, 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 [
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 [
G V , E ney polynomial for an undirected graph is defined as follows:
TG (x, y) AE (x 1)k(A)k(E) ( y 1)k(A)|A||V| , where k( A) denotes the number of the graph connected components (V , A) . It can be seen from the definition that the polynomial is completely TG defined and polynomial in x and y.
1. TG (1,1) is equal to the number of spanning forests;
TG (1, 2) is equal to the number of subgraphs G with the same number of connected components as G;
3. TG (2,1) 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: The Tutte-Whitney polynomial for a cycle G Z The Tutte-Whitney polynomial for a tree G with n nodes: TG (x, y) xn1. n with n nodes: TZ (x, y) y x xn1.
n
n Fn (x, y) Ckn11(x y y2 yk 1)Fk 1(1, y)Fnk (x, y).
k 1
The relationship between the canonical survivability R(G, p) and the Tutte-Whitney polynomial is given by the equality:
R(G, p) (1 p)|V |k (G) p|E||V |k (G)TG 1, 1 .
p
The exact calculation of the canonical survivability of a system is an NP-hard
problem, 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
consisting of n edges, it is necessary to walk through all spanning subgraphs of graph G [
Therefore, in many works, alternative approximate approaches are proposed for
assessing the survivability of systems, in particular, models based on an artificial neural
network [
For modeling, three artifact networks are investigated as an example, namely, the Barabási-Albert, Erdös-Renyi and Watts-Strogatz networks. These networks can be considered as prototypes of many real networks. 3.1
Most real artifact networks have a power-law distribution. It turned out that this distribution 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.
It has been proven that it is the “rich getting richer” phenomenon that leads to the
emergence of power laws in networks [
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
D.J. Watts and S. Strogatz discovered a phenomenon common to many real-world
networks called the Small Worlds effect [
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 Then the following procedure is performed: with a probability p , 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" arises (it is clearly expressed at p (0.01, 0.1) ).
With a further increase p , 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).
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: 1. System model - a graph consisting of nodes and links (undirected) S (V , E) . Nodes - homogeneous functional components.
2. "Power" of the system - the number of nodes in the largest connected component 3. The system is in the “live” state, functionally capable, if the specific “power” of the system is not less than a certain threshold , ie. Vs Vo , 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 * , at which the system leaves the "alive" state, i.e. Vs Vo . 5
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 s , which V 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, Barabá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 depending 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 , i.e.: | Vs | Vo , 0.2 then, accordingly, we get the values of the threshold probability for networks:
Model name Erdős-Renyi 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 polynomial are sufficient. Taking into account the network topology and the analytical estimates 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 decreases even at low values of the probability of destructive influences (removal of links). 6
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 network connectivity under a destructive effect on it.
This indicator (the threshold probability of removing individual edges) is more complex 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 inequality 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 accounting for networks in which links are not completely deleted, but "regenerated", or new links can be established.
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)
library("igraph")
N=200
g <- barabasi.game(N, directed = FALSE)
d=1
t=components(g)[