Comparison of UAB_CR and UAB_C.
In this chapter, we study the task of obtaining and using the exact cumulative bounds of various network reliability indices. A network is modeled by a non-directed random graph with reliable nodes and unreliable edges that fail independently. The approach based on cumulative updating of the network reliability bounds was introduced by Won and Karray in 2010. Using this method, we can find out whether the network is reliable enough with respect to a given threshold. The cumulative updating continues until either the lower reliability bound becomes greater than the threshold or the threshold becomes greater than the upper reliability bound. In the first case, we decide that a network is reliable enough; in the second case, we decide that a network is unreliable. We show how to speed up cumulative bounds obtaining by using partial sums and how to update bounds when applying different methods of reduction and decomposition. Various reliability indices are considered: k-terminal probabilistic connectivity, diameter constrained reliability, average pairwise connectivity, and the expected size of a subnetwork that contains a special node. Expected values can be used for unambiguous decision-making about network reliability, development of evolutionary algorithms for network topology optimization, and obtaining approximate reliability values.
- network reliability
- factoring method
- network connectivity
- random graph
- diameter constraint
- probabilistic connectivity
- pairwise connectivity
- network topology optimization
- cumulative updating
The network reliability analysis is one of the primary tasks in the course of the network topology design and optimization. Usually, random graphs are used when modeling networks with unreliable elements [1–7]; therefore, the network reliability is defined as a connectivity measure in a random graph. There are many reliability indices of networks, for example, probabilistic connectivity , average pairwise reliability [5, 6], and diameter constrained reliability .
The most widespread network reliability index is the probabilistic connectivity of the corresponding random graph. Depending on the number of terminals (selected nodes that must be connected), there are three types of this measure such as two-terminal, all-terminal (ATR) and k-terminal reliabilities. The average pairwise reliability (APR) describes the network reliability from the point of connection between every two nodes, while a network may be still disconnected. The reliability of a network with a diameter constraint (DCR) is defined as the probability of each pair of nodes connectivity by paths that travel through a limited number of communication channels. This index is more useful, especially for P2P networks , wavelength division multiplexing networks, wireless sensor networks, and so on.
Another reliability index we consider in this chapter is the mathematical expectation of the size of a connected subgraph that contains a special node (MENC) , which describes the quality of monitoring area coverage.
Despite the fact that problems of exact reliability computations are NP-hard [9, 10], it is possible to conduct the exact calculation for networks of practical interest dimension, taking into account some special features of network topologies. For large-scale networks, various methods of reliability evaluation are widely used [11, 12]. Won and Karray suggested the cumulative updating of reliability bounds for uniqueness of decision on network feasibility . Originally, this approach was presented for ATR. In this chapter, we present our results on cumulative updating of other reliability indices, and some improvements for ATR bounds cumulative updating. In addition, the main ideas of constructing the cumulative bounds for random graph characteristics are discussed along with examples of their usage in obtaining better evaluation of reliability indices and improving bionic optimization algorithms.
2. The basic notations
We simulate a network with perfectly reliable nodes and unreliable links by an undirected random graph G = (V,E) with given presence probabilities 0 ≤ ei ≤ 1 of the edges. The notations which are used in this chapter are given below. Most of them coincide with the notations from .
G—Undirected probabilistic network;
V—Set of n nodes;
E—Set of m edges;
ei; eij – i-th edge or edge that connects i-th and j-th nodes, depending on context;
pj – Operating probability of j-th edge;
wi – Weight of node i, WT = (w1,…,wn);
W(G) – Total weight of nodes of G;
R(G) – All-terminal reliability of G, that is, probability that every two nodes are connected;
K—Set of terminal nodes;
—Diameter constrained reliability of G, that is, the probability that every two nodes from K are connected by a path that travel through not more than d edges;
LB, UB—Lower and upper bounds of G reliability. In case of ATR, we use the original notation form : RL, RU;
R0—Predefined threshold for the network reliability value;
N(G) (M(G))—Mathematical expectation of the number of disconnected (or connected) pairs of nodes in G;
CS(G; s)—Mathematical expectation of a number of nodes in a connected subgraph that contains a node s; if s = 1, then CS(G);
—Average pairwise reliability of G;
C—Edge chain composed of edges e1,…,ek;
G/C (G/e)—Network G with a contracted chain C (edge e);
G\C (G\e)—Network G without chain C (edge e); and
—Network G with an absolutely reliable edge e;
3. Factoring method and cumulative updating of network reliability bounds
The most common exact method for calculating various network reliability measures is the factoring method. According to this method, we divide the probability space, which consists of all particular network realizations, into two sets based on the presence or absence of a network element. Further on we refer to such a network element as a factored element, or a pivot element. As a result, for a given network G and a factored element e, we will obtain the two networks: , where e is absolutely reliable, and G\e, where e is absolutely unreliable, so we could remove it. The probability of is equal to the pivot element reliability, and the probability of G\e is equal to the pivot element failure probability. For a reliability index Rel of the initial network, the following expression holds (the total probability law):
Then the obtained networks are subject to the same factoring procedure. Recursions continue until either an unreliable network is obtained (0 is returned) or an absolutely reliable network is obtained (1 is returned). For ATR (Figure 1), expression (1) turns to:
We can speed up the factoring process by calculating the intermediate networks reliabilities directly, that is, without further factorization. For ATR calculation, the five-vertex graph reliability formula can be used . Another way to accelerate the reliability computing by using various reduction  and decomposition  methods, such as serial-parallel transformation on each recursive call of the factoring procedure, biconnected decomposition, and other methods.
The idea of the cumulative updating method is an incremental updating of exact lower (LB) and upper (UB) reliability bounds and comparing them with a given reliability threshold . If , then the network is reliable. If , then the network is unreliable. The LB must necessarily be non-decreasing, and the UB must necessarily be non-increasing. Another obligatory condition is the equality of LB, UB at the last step and exact reliability value R. One possible way of bounds updating is the usage of the factoring method. When a final graph or a disconnected graph is obtained, we can update bounds .
As a rule, any algorithm of calculation of mathematical expectation for a non-negative function μ of a random graph G practically comes to summarizing non-negative values. According to the definition of mathematical expectation in the discrete case :
where Γ is a set of all possible final realizations of G that are obtained during factorization.
If some realizations are obtained along with their probabilities, and a function μ is obtained for all these realizations, then the LB is greater or equal to the corresponding partial sum.
Now let us assume that for μ, its possible minimal and maximal values are known. In this case, we easily obtain the following bounds:
Finally, both bounds will obviously come to an exact value.
From (4), we easily obtain the equations for improving bounds when the new (i-th) realization is obtained and is calculated:
For ATR, and , so we arrive to the equations presented by Won and Karray in , while for MENC and , where n is a total number of nodes in a graph. Initial values of bounds are equal to these values.
4. Improvements for ATR bounds cumulative updating
4.1. The chain branching
Our methods named chain branching (CB) and chain reduction (CR)  could be used  .as a basis for two kinds of the ATR bound updating (UAB) algorithms named UAB based on CB (UAB_CB), and UAB based on CR (UAB_CR). These methods can be used if a network contains a chain, that is, a sequence of adjacent two-degree nodes. The CB reduces the calculation of ATR for calculating the ATRs of networks obtained from G by removing a pivot chain, or removing it and contracting its terminal nodes, while CR reduces it for calculating the ATR of the network , in which, this chain is substituted by a single edge. Let a chain C consist of k edges, its terminal nodes are s and t, and let an edge has a reliability , then 
The best choice is the usage of the longest chain as a pivot. However, it requires finding of all the chains. We may accelerate the calculation by choosing a chain (or an edge) incidental to a node with a minimal degree for obtaining a new chain.
4.2. The usage of Cutnodes
Let a network G have a cutnode u that divides G into two subnetworks and , therefore, . and are lower and upper bounds for , respectively. Like wise, and are the lower and upper bounds for , respectively. Then .
Let us estimate the ATR of subnetworks and in turn starting from . While estimating the ATR of , we have no information about the ATR of , thus and , and RL for R(G) is 0, while RU for R(G) is . After some steps of estimating , we switch to estimating and , thus improving RL and RU for G, and so on. Therefore, we calculate the bounds for and separately (possibly in parallel). Now let us continue with applying this scheme to calculating the bounds for and by the factoring method.
Statement 1 For all a,b such that 1 ≤ a ≤ I, 1 ≤ b ≤ J, the following inequalities hold:
Proof of the statement can be found in , as well as the algorithm with the use of cutnodes (UAB_C).
4.3. The usage of two-node cuts
Now let us describe the UAB modification that uses two-node cuts. Let the network G has a node cut u,v that divides it into two subnetworks and (Figure 2). For any network H that contains the nodes u and v we will denote a network that is obtained by contracting these nodes as H′.
For the first time, the approach based on two-node cut was presented by Kevin Wood  in 1989. It describes how to perform the reliability-preserving triconnected decomposition of a network for calculating its k-terminal reliability. Later in 2006, we have introduced a general method which allows using an arbitrary node cut for calculating all-terminal reliability [18, 19]. This method makes possible to reduce the reliability calculation to the calculation of reliabilities of a group of networks each one with a smaller dimension. The total number of these networks is 2*BW, where BW is the Bell number and W is the number of nodes in the cut. A particular case of two-node cut along with numerical experiments to demonstrate the efficiency for the ATR calculation was presented in [16, 20], and in —for the k-terminal reliability calculation. Despite the fact that the method from  presents a graph transformation for further factoring, and the method from  presents an expression for the network reliability, both of them practically lead to similar calculations of the same complexity. Another result was with the ATR calculation using special kind of node cuts : the so-called longitudinal and cycle cuts. All the listed results, which we have obtained, are described in detail in . Following is the corresponding Eq.  for the ATR without proof: The following equation holds:
The following equation holds:
where nodes 1, 2, and 3 composes the threee-node cut, is a graph that is obtained by merging y and z nodes in , and is obtained by merging x, y, and z nodes. The expression for four-node cut has also been obtained , but we do not present it due to its huge size.
However, our results on using an arbitrary node cut for all-terminal reliability calculation were published only in Russian [18, 19], and only the two-node cut case was presented in English [16, 20]. Maybe, this is the reason that these results are not so widely known, and therefore, the same ideas were proposed again by Juan Manuel Burgos and Franco Robledo Amoza [23, 24] in 2016. As we have done it in [16–20], in [23, 24], the authors show how to calculate the all-terminal reliability of a network with a node cut via reliabilities of a group of smaller networks, but in a somewhat different way. As a result, Eqs. (9–10) were presented.
Suppose that some networks are obtained from during the factoring process. If this factoring does not involve edges incidental to u or v, then parallel factoring in leads to obtain . Let us introduce the following denotations: , , , and , for 1 ≤ i ≤ I. As in both and , the factoring is executed by the same pivot edges, we have . Obviously because differs from by the edge (u,v) that has reliability 1 in . Similarly, by the factoring in by edges that are not incidental to x or y, we obtain the networks , and by the factoring in , we obtain . Let us denote , , , and for 1 ≤ i ≤ J. Similar to the above case, we have , . Let , and let for , for .
Let us obtain :
As is shown in , these values are the upper and lower bounds for reliabilities of the corresponding networks; these bounds are exact for i = L. In the case i = 0, the lower bounds are 0 and the upper bounds are 1.
Note that , as , , as .
Now we obtain , and for odd and even j separately. For j = 2i, 0 ≤ i ≤ L:
For j = 2i + 1,0 ≤ i ≤ L − 1:
Statement 2 For any 1 ≤ j ≤ 2 L, we have
If j = 2 L, then the second and the third inequalities become equalities. The proof of the statement can be found in , as well as the algorithm (UAB_2NC) with two-node cuts.
Note that both CB and CR can be used for speeding up the 2NC algorithm under the condition that the nodes u and v do not belong to a pivot chain. In the case of CR , , where p is a multiplier by which the reliability of a reduced network must be multiplied in CR .
4.4. Case studies
We have compared the algorithms presented with node cuts UAB_C and UAB_2NC to the algorithm CR from  that does not take possible cutnodes or two-node cuts into account. The results  of the comparison are presented in Tables 1–3. The CR was used while factoring for better performance, and the five-node networks were considered as simple ones. The PC with Intel Core Duo 2.93 GHz was used for testing.
|G2||0.901||UAB_CR||3 min 22 s||24,765,569|
We have chosen the two networks and for testing UAB_C, and the two networks and for testing UAB_2NC.
The network consists of two 9-vertex complete graphs which are connected by a cutnode. Thus, it contains 17 nodes and 72 edges.
The network consists of two 5 × 5 lattices which are connected by a cutnode. As a cutnode, we choose the corner. The resulting network contains 49 nodes and 80 edges. Table 1 shows the results of numerical experiments.
The network (48 nodes and 79 edges) is composed of two 5 × 5 lattices which are connected by two nodes (Figure 3).
The network (22 nodes and 108 edges) is composed of two 11-vertex complete graphs which are connected by two nodes without edge connecting them. A similar network that is composed of two 5-vertex complete graphs is presented in Figure 4.
The edges and are equally reliable with p = 0.5, while the edges and are equally reliable with p = 0.9. , , , and .
Tables 2 and 3 present the results for and , respectively. The third row contains the results when the threshold value coincides with the exact reliability value. The results for the factoring algorithm with chain reduction are shown in the second column. The results for the UAB_2NC are shown in the third column.
|Time (s)||Recursions||Time (s)||Recursions|
|Time (s)||Recursions||Time (s)||Recursions|
|0.998||0.36||45,374||< 1 ms||35|
As can be seen, the approach proposed has a great advantage. The efficiency of UAB as it is depends on the closeness of the threshold value to the reliability value R(G).
5. Cumulative updating of diameter constrained network reliability
For the DCR, expression (1) takes the following form:
We denote this method as a simple factoring method (SFM). Cancela and Petingi have proposed a modified factoring method for calculating DCR , which is much faster than the already described classical factoring method in the diameter constrained case (14). The Cancela and Petingi factoring method (CPFM) operates with a list of paths instead of graphs. For any terminals s, t, the list of all the paths with a limited length between s, t is generated. By the union of for all the pairs of terminals is denoted. P(e) is composed of the paths of which include the edge e. The list of CPFM arguments are given below :
: the number of paths of length at most d between s and t in G;
: the number of non-perfect edges (edges e such that p(e) < 1) in the path p, for every .
: this is a flag, which has the value False when the path is no longer feasible, that is, it includes an edge which failed; and True otherwise;
: this is a flag, which has the value True when s and t are connected by a perfect path of length at most d and False otherwise;
connectedPairs: the number of pairs of terminals which are connected by a perfect path of length at most d.
Pseudocode of the method proposed for the DCR bounds cumulative updating , which is based on CPFM, is presented below:
Input: G = (V;E), d, Pd, P(e), np(s; t), links(p), feasible(p), connected(s,t), connectedPairs, RL = 0, RU = 1, Pl = 1.
Function FACTO (np(s,t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)if RL > R0 or RU < R0 then
e is an arbitrary edge: 0 < pe < 1
contractEdge (np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)
deleteEdge (np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)
Function contractEdge(np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)Pr = Pr * pe
for each p = (s,..,t) in P(e) such that feasible(p) = true do
links(p) = links(p) - 1
if connected(s,t) = false and links(p) = 0 then
connectedPairs = connectedPairs + 1
if connectedPairs = |K|*(|K|-1)/2 then RL = RL + Pr
FACTO (np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)end contractEdge
Function deleteEdge(np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)Pr = Pr *(1-pe)
For each p = (s,…,t) in P(e) such that feasible(p) = true do
feasible(p) = false
np(s,t) = np(s,t) - 1
if np(s,t) = 0 then RU = RU - Pr
FACTO (np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)
For the speeding up of DCR calculation, it is possible to apply methods of reduction and decomposition. In our previous studies [25–27], we have obtained such methods which can calculate the DCR faster. These methods are the analogue of the well-known series-parallel transformation for CPFM, and the pivot edge selection strategy. Also, we have obtained decomposition methods for calculating DCR in the case with two terminals. The methods obtained allow us to significantly reduce the number of recursive calls in CPFM and the complexity of DCR computation. In the above algorithm, we assume that the series-parallel reduction has been already performed and the pivot edge selection strategy is used.
Below we show how RL and RU are changing during the procedure proposed for the Intellinet network topology (Figure 5). The edge reliability is equal to 0.7 for each edge and the diameter value is equal to 12. The threshold value was equal to the exact DCR value, which was previously calculated. The calculation time was about 12 min. Experiments were performed on Intel Xeon E31240 3.3 GHz, 8 cores (Figure 6).
6. Special problems of updating reliability bounds
When special methods of graph reduction or decomposition are applied for the speeding up of calculations, the corresponding equations for updating the bounds must be used. Derivation of such equations for different functions μ(G) is based on taking into account all ”inner” changes of bounds that are concealed inside intermediate steps thus leading to final results of such a reduction or a decomposition. For example, when “branching by chain”  is applied, consequent factoring by edges of a chain is used for derivation, and each factoring may require a change of bounds.
Now let us turn to an example of a simple reduction, which is removing a dangling node. Let the graph G have some attached trees in its structure is shown in Figure 7.
In the case of the ATR, we have the trivial equality , where e is the edge that connects the dangling node to the graph. As removing e with probability leads to graph disconnection, the upper bound must be decreased by . The lower bound rests unchanged, but probabilities of all further realizations of G\e must be multiplied by . If there are some attached trees as shown in Figure 7, then the ATR of the graph G is equal to the ATR of this graph without all attached trees multiplied by the product of reliabilities of all the edges in these trees (let us denote it as Pr): . Thus, we continue with the graph , LB does not change, Pr must be included as a multiplier in probabilities of further realizations, and UB is reduced by probability of at least one edge of attached trees, that is, 1-Pr. If the reduction takes place at the initial step, then the upper bound starts from Pr.
The case of APR is not so simple. It is known that the task of obtaining this reliability index is equivalent to the one of obtaining mathematical expectation of the number of disconnected pairs of nodes in a random graph (EDP, see [28, 29]). Indeed, the following equations are valid:
From these equations, bounds are easily obtained:
In , the following equation was derived with deleting the dangling node t that is incidental to the node s:
Here is the weight of the node t, initially 1. This weight shows an expected number of nodes that are merged in this node during the graph transformations: when using the factoring method, for example, one should remember the number of nodes that are merged if we assume that an edge between them is reliable. This weight is used for calculating the number of disconnected pairs of nodes when the graph is divided. Let W(G) be the total weight of the all nodes (initially, it is equal to the number of nodes) in G. G0 equals G with the only difference: the weight of the node s becomes equal to .
From this, we obtain the following changes in the bounds: is increased by and the is decreased by . Contrary to case of the ATR, the result of removing attached trees highly depends on their structures, so dangling nodes must be removed one at a time. The only known exception with the derived equation is the case of the attached chain .
7. Using cumulative bounds for network reliability approximation
A simple approximation of the function μ(G) through its bounds is their average: μ(G) = (LB + UB)/2. However, the bounds tend to the exact solution with different rates. It seems to be reasonable assuming that cross of lines, obtained by the linear approximation of curves for LB and UB, may be a better approximation of μ(G). Let us have the bounds and at a step i > 0 and let be the corresponding approximation. The following proportion takes place:
Hence, we have
Let us name this approximation as the approximation based on trends (ABT).
In the case of ATR, and , so
while in the case of MENC, and , so
At the last step, , and from (19) we have that the proposed approximation also equals this value.
In Figures 8–10, the behavior of bounds for the EDP of 4x4 lattice (p = 0.7), for the MENC of the same lattice with c-node 1, and for the probability of the flow transmission (PFT) between two diagonal corners of this lattice with throughput of all edges 1 and the edges reliability uniformly distributed between 0.5 and 1, are presented, respectively.
As we can see the ABT has become better than the average of LB and UB from the first step or very fast.
We consider the practical usage of cumulative bounds and ABT in the following section.
8. Using cumulative bounds in network topology optimization
When optimizing the network topology by a certain criteria, a fitness function (FF) must be calculated for each alternative. In our case (k-terminal reliability, MENC, and APR) this means using NP-hard algorithms for its obtaining. Note that using approximate algorithms may lead to wrong decisions when structures with close values of FF are compared.
We propose using the cumulative bounds for decision-making about whether a new solution obtained by crossover or mutation deserves including into population.
The ideas are simple (without the loss of generality, we assume that a task is maximizing some function of an unreliable network):
A wittingly inappropriate solution may be rejected before carrying out the exhaustive calculation of the corresponding FF. If the upper bound of the FF becomes smaller than the FF value of the worst solution in the current population, then this potential solution is rejected.
At initial stages, a new solution may be included into the population based on the LB value. If it exceeds the FF value of the worst solution in the current population, then this new solution substitutes the worst one with assigning ABT as an approximate value of the FF.
Note that inevitable narrowing of bounds of FF in population leads to seldom updating of the population and to a better approximation of FF.
The experiments [30, 31] with network topology optimization by the criteria of the ATR and the DCR show that using the cumulative bounds allow the speeding up of calculations up to two times without loss of precision or with negligible loss (about 10−7).
The general approach of obtaining the cumulative bounds of random graph functions is presented. We have shown the possibility of computing the cumulative bounds by partial sums and updating the cumulative bounds in case of applying different methods of reduction and decomposition. For example, various indices of the network reliability were considered: the all-terminal reliability, the diameter constrained reliability, the average pairwise connectivity, and the expected size of a subnetwork that contains a special node. Also, we have described how the cumulative bounds approach can be used for network reliability evaluation and development of evolutionary algorithms for the network topology optimization. Future works can include methods of computing the cumulative bounds for other reliability indices along with methods of reduction and decomposition, further improvement of evolutionary algorithms for the network topology optimization, and parallel algorithms for the network reliability analysis.
This research was supported by the Russian Foundation for Basic Research under grants 17-07-00775, 17-47-540977.