=Paper=
{{Paper
|id=Vol-2859/paper1
|storemode=property
|title=Modeling the Survivability of Network Structures
|pdfUrl=https://ceur-ws.org/Vol-2859/paper1.pdf
|volume=Vol-2859
|authors=Aleksandr Dodonov,Dmytro Lande
|dblpUrl=https://dblp.org/rec/conf/its2/DodonovL20
}}
==Modeling the Survivability of Network Structures==
https://ceur-ws.org/Vol-2859/paper1.pdf
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) Ckn11 ( 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")