Open access peer-reviewed chapter

Obtaining and Using Cumulative Bounds of Network Reliability

Written By

Alexey S. Rodionov and Denis A. Migov

Submitted: December 8th, 2016 Reviewed: November 3rd, 2017 Published: December 20th, 2017

DOI: 10.5772/intechopen.72182

Chapter metrics overview

1,223 Chapter Downloads

View Full Metrics


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
  • estimation
  • cumulative updating

1. Introduction

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 [17]; 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 [4], average pairwise reliability [5, 6], and diameter constrained reliability [7].

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 [8], 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) [2], 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 [13]. 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 [14].

  1. G—Undirected probabilistic network;

  2. V—Set of nnodes;

  3. E—Set of medges;

  4. ei; eij – i-th edge or edge that connects i-th and j-th nodes, depending on context;

  5. pjOperating probability of j-th edge;

  6. wiWeight of node i, WT = (w1,…,wn);

  7. W(G) Total weight of nodes of G;

  8. R(G) All-terminal reliability of G, that is, probability that every two nodes are connected;

  9. K—Set of terminal nodes;

  10. RKdG—Diameter constrained reliability of G,that is, the probability that every two nodes from Kare connected by a path that travel through not more than dedges;

  11. LB, UB—Lower and upper bounds of Greliability. In case of ATR, we use the original notation form [13]: RL, RU;

  12. R0Predefined threshold for the network reliability value;

  13. N(G) (M(G))Mathematical expectation of the number of disconnected (or connected) pairs of nodes in G;

  14. 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);

  15. R¯Average pairwise reliability of G;

  16. C—Edge chain composed of edges e1,…,ek;

  17. G/C(G/e)Network Gwith a contracted chain C(edge e);

  18. G\C(G\e)Network Gwithout chain C(edge e); and

  19. Ge—Network Gwith 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 Gand a factored element e,we will obtain the two networks: Ge, where eis absolutely reliable, and G\e, where eis absolutely unreliable, so we could remove it. The probability of Geis equal to the pivot element reliability, and the probability of G\eis equal to the pivot element failure probability. For a reliability index Relof 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:


Figure 1.

The factoring method.

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 [13]. Another way to accelerate the reliability computing by using various reduction [4] and decomposition [17] 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 R0. If LB>R0, then the network is reliable. If UB<R0, then the network is unreliable. The LBmust necessarily be non-decreasing, and the UBmust necessarily be non-increasing. Another obligatory condition is the equality of LB, UBat 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 [13].

As a rule, any algorithm of calculation of mathematical expectation for a non-negative function μ of a random graph Gpractically comes to summarizing non-negative values. According to the definition of mathematical expectation in the discrete case [14]:


where Γ is a set of all possible final realizations of Gthat are obtained during factorization.

If some realizations Γ0are obtained along with their probabilities, and a function μ is obtained for all these realizations, then the LBis greater or equal to the corresponding partial sum.

Now let us assume that for μ, its possible minimal μmand maximal μMvalues 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 Hiis obtained and μHiis calculated:


For ATR, μm=0and μM=1, so we arrive to the equations presented by Won and Karray in [13], while for MENC μm=1and μM=n, where nis 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) [15] could be used [16] .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 Gby removing a pivot chain, or removing it and contracting its terminal nodes, while CR reduces it for calculating the ATR of the network GR, in which, this chain is substituted by a single edge. Let a chain Cconsist of kedges, its terminal nodes are sand t, and let an edge esthas a reliability pst, then [16]


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 Ghave a cutnode uthat divides Ginto two subnetworks G1and G2, therefore, RG=RG1RG2. RL1and RU1are lower and upper bounds for RG1, respectively. Like wise, RL2and RU2are the lower and upper bounds for RG2, respectively. Then RL1RL2RGRU1RU2.

Let us estimate the ATR of subnetworks G1and G2in turn starting from G1. While estimating the ATR of G1, we have no information about the ATR of G2, thus RL2=0and RU2=1, and RLfor R(G) is 0, while RUfor R(G) is RUG1. After some steps of estimating RG1, we switch to estimating RL2and RU2, thus improving RLand RUfor G, and so on. Therefore, we calculate the bounds for RG1and RG2separately (possibly in parallel). Now let us continue with applying this scheme to calculating the bounds for RG1and RG2by the factoring method.

Similar to [15], we suppose that some networks H1, H1, …, HIare obtained from G1, and networks K1, K2,,KJfrom G2by factorization (1). Let us denote xi=PHi, yi=RHi, 1 ≤ i ≤ I, and si=PKi, ti=RKi, 1 ≤ i ≤ J. Then [16]:


Statement 1For all a,b such that 1 ≤ a ≤ I, 1 ≤ b ≤ J, the following inequalities hold:


Proof of the statement can be found in [16], 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 Ghas a node cut u,vthat divides it into two subnetworks G1and G2(Figure 2). For any network Hthat contains the nodes uand vwe will denote a network that is obtained by contracting these nodes as H′.

Figure 2.

The networkGwith two-node cut and auxiliary networks.

For the first time, the approach based on two-node cut was presented by Kevin Wood [17] 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 Wis 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 [21]—for the k-terminal reliability calculation. Despite the fact that the method from [17] presents a graph transformation for further factoring, and the method from [20] 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 [22]: the so-called longitudinal and cycle cuts. All the listed results, which we have obtained, are described in detail in [19]. Following is the corresponding Eq. [20] for the ATR without proof:

The following equation holds:


The equation for three-node cut is sufficiently more complicated [18, 19]:


where nodes 1, 2, and 3 composes the threee-node cut, Gixyzis a graph that is obtained by merging yand znodes in Gi, and Gixyzis obtained by merging x, y,and znodes. The expression for four-node cut has also been obtained [19], 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 [1620], 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. (910) were presented.

Let us describe how we can use expression (9) and update the ATR bounds separately for both subgraphs G1and G2(Figure 2) for obtaining the ATR bounds of the whole graph G.

Suppose that some networks H1,,HIare obtained from G1during the factoring process. If this factoring does not involve edges incidental to uor v, then parallel factoring in G1uvleads to obtain H1uv,,HIuv. Let us introduce the following denotations: xi=PHi, yi=RHi, xi=PHiuv, and yi=RHiuv, for 1 ≤ i ≤ I. As in both G1and G1uv, the factoring is executed by the same pivot edges, we have xi=xi. Obviously yiyibecause H1uvdiffers from Hiby the edge (u,v) that has reliability 1 in H1uv. Similarly, by the factoring in G2by edges that are not incidental to xor y, we obtain the networks K1,,Kj, and by the factoring in G2uv, we obtain K1,,KJ. Let us denote siPKi, ti=RKi, si=PKiuv, and ti=RKiuvfor 1 ≤ i ≤ J. Similar to the above case, we have si=si, titi. Let L=maxIJ, and let xi=yi=yi=0for I+1iL, si=ti=ti=0for J+1iL.

Let us obtain RL1,i,RU1,i,RL1,i,RU1,i,RL2,i,RU2,i,RL2,i,RU2,ifor1iL:


As is shown in [13], 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 RL1,iRL1,i,RU1,iRU1,i, as yiyi;RL2,iRL2,i, RU2,iRU2,i, as titi.

Now we obtain RLj, and RUjfor odd and even jseparately. For j = 2i, 0 ≤ i ≤ L:


For j = 2i + 1,0 ≤ i ≤ L − 1:


Statement 2For 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 [16], 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 uand vdo not belong to a pivot chain. In the case of CR RUj1RUj1xj1p, RUj1RUj1xj1p, where pis a multiplier by which the reliability of a reduced network must be multiplied in CR [4].

4.4. Case studies

We have compared the algorithms presented with node cuts UAB_C and UAB_2NC to the algorithm CR from [13] that does not take possible cutnodes or two-node cuts into account. The results [16] of the comparison are presented in Tables 13. 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.

G10.9UAB_CR39 s5,245,491
G10.9UAB_C<1 ms2504
G10.94UAB_CR34 s639,562
G10.94UAB_C<1 ms2643
G20.5UAB_CR2 s259,879
G20.5UAB_C60 ms4322
G20.901UAB_CR3 min 22 s24,765,569
G20.901UAB_C45 ms3233

Table 1.

Comparison of UAB_CR and UAB_C.

We have chosen the two networks G1and G2for testing UAB_C, and the two networks G3and G4for testing UAB_2NC.

The network G1consists of two 9-vertex complete graphs which are connected by a cutnode. Thus, it contains 17 nodes and 72 edges.

The network G2consists 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 G3(48 nodes and 79 edges) is composed of two 5 × 5 lattices which are connected by two nodes (Figure 3).

Figure 3.

The union of two 5 × 5 lattices by two nodes.

The network G4(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.

Figure 4.

The union of two complete five-node networks by two nodes without connecting edge.

The edges G1and G4are equally reliable with p = 0.5, while the edges G2and G3are equally reliable with p = 0.9. RG1=0.9307194, RG2=0.883248, RG3=0.903168801959, and RG4=0.982472649148.

Tables 2 and 3 present the results for G3and G4, 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)RecursionsTime (s)Recursions

Table 2.

Results of the numerical experiments for the network G3.

Time (s)RecursionsTime (s)Recursions
0.9980.3645,374< 1 ms35

Table 3.

Results of the numerical experiments for the network G4.

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 R0to 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 [7], 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 Pstdof all the paths with a limited length between s, tis generated. By Pdthe union of Pstdfor all the pairs of terminals is denoted. P(e) is composed of the paths of Pdwhich include the edge e. The list of CPFM arguments are given below [7]:

  • npst: the number of paths of length at most dbetween sand tin G;

  • linksp: the number of non-perfect edges (edges esuch that p(e) < 1) in the path p, for every pPd.

  • feasiblep: 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;

  • connectedst: this is a flag, which has the value True when sand tare connected by a perfect path of length at most dand 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 [27], 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.

FunctionFACTO (np(s,t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)ifRL > R0 or RU < R0 then

    eis 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)


FunctioncontractEdge(np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)Pr = Pr * pe

for eachp = (s,..,t) in P(e) such that feasible(p) = truedo

    links(p) = links(p) - 1    

    ifconnected(s,t) = falseandlinks(p) = 0 then

                 connected(s,t) true

                 connectedPairs = connectedPairs + 1                 

                 ifconnectedPairs = |K|*(|K|-1)/2 thenRL = RL + Pr

FACTO (np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)endcontractEdge

FunctiondeleteEdge(np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)Pr = Pr *(1-pe)

For eachp = (s,…,t) in P(e) such that feasible(p) = truedo

       feasible(p) = false

       np(s,t) = np(s,t) - 1

       ifnp(s,t) = 0 thenRU = 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 [2527], 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.

Figure 5.

The Intellinet network.

Below we show how RLand RUare 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).

Figure 6.

The behavior of DCR bounds for the Intellinet network.


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” [15] 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 Ghave some attached trees in its structure is shown in Figure 7.

Figure 7.

The graph with attached trees.

In the case of the ATR, we have the trivial equality RG=peRG\e, where eis the edge that connects the dangling node to the graph. As removing ewith probability 1peleads to graph disconnection, the upper bound must be decreased by 1pe. The lower bound rests unchanged, but probabilities of all further realizations of G\emust be multiplied by pe. If there are some attached trees as shown in Figure 7, then the ATR of the graph Gis equal to the ATR of this graph without all attached trees G0multiplied by the product of reliabilities of all the edges in these trees (let us denote it as Pr): RG=PrRG0. Thus, we continue with the graph G0, LBdoes not change, Prmust be included as a multiplier in probabilities of further realizations, and UBis 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 [14], the following equation was derived with deleting the dangling node tthat is incidental to the node s:


Here wtis 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 Gwith the only difference: the weight of the node s becomes equal to ws+pstwt.

From this, we obtain the following changes in the bounds: LBEDPis increased by 1pstwtWGwtand the UBEDPis decreased by pstwtWGwt. 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 [6].


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 LBand UB, may be a better approximation of μ(G). Let us have the bounds LBiand uBiat a step i > 0 and let μiGbe 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, μm=0and LB=UB=μG, so


while in the case of MENC, μm=1and μM=Cn2, so


At the last step, LB=UB=μG, and from (19) we have that the proposed approximation also equals this value.

In Figures 810, 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.

Figure 8.

The behavior of bounds and approximations of EDP, the exact value is 20.915633.

Figure 9.

The behavior of bounds and approximations of MENC, the exact value is 12.562672.

Figure 10.

The behavior of bounds and approximations of PFT, the exact value is 0.196600.

As we can see the ABT has become better than the average of LBand UBfrom 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):

  1. 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.

  2. 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).


9. Conclusion

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.


  1. 1. Colbourn CJ. The Combinatorics of Network Reliability. New York, NY, USA: Oxford University Press; 1987. 160 p
  2. 2. Jereb L. Network reliability: Models, measure and analysis. In: 6th IFIP Workshop on Performance Modeling and Evaluation of ATM Networks; 1998. p. T02/1–T02/10
  3. 3. Moore EF, Shannon CE. Reliable circuits using less reliable relays. Journal of The Franklin Institute. 1956;262(4b):191-208
  4. 4. Shooman AM. Algorithms for network reliability and connection availability analysis. In: Electro/International 1995, Boston, MA, USA. 1995, pp. 309-333
  5. 5. Sun F, Shayman MA. On pairwise connectivity of wireless multihop networks. International Journal of Security and Networks. 2007;2(1/2):37-49
  6. 6. Rodionov AS, Rodionova OK. Exact bounds for average pairwise network reliability. In: The 7th International Conference on Ubiquitous Information Management and Communication; Malaysia. ACM; 2013. Article No. 45
  7. 7. Cancela H, Petingi L. Diameter constrained network reliability: Exact evaluation by factorization and bounds. In: Int. Conf. on Industrial Logistics; Okinawa, Japan. 2001. p. 359-356
  8. 8. Pandurangan G, Raghavan P, Upfal E. Building low-diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communications. 2003;21(6):995-1002
  9. 9. Valiant LG. The complexity of enumeration and reliability problems. SIAM Journal on Computing. 1979;8(3):410-421
  10. 10. Bodlaender HL, Wolle T. A note on the complexity of network reliability problems. IEEE Transactions on Information Theory. 2004;47:1971-1988
  11. 11. Deuermeyer LA. New approach for network reliability analysis. IEEE Transactions on Reliability. 1982;31(4):350-354
  12. 12. Goyal NK, Misra RB, Chaturvedi SK. Snem: A new approach to evaluate terminal pair reliability of communication networks. Journal of Quality in Maintenance Engineering. 2005;11(3):239-253
  13. 13. Won JM, Karray F. Cumulative update of all-terminal reliability for faster feasibility decision. IEEE Transactions on Reliability. 2010;59(3):551-562
  14. 14. Rodionov AS. Cumulative estimated values of structural Network’s reliability indices and their usage. In: Dynamics of Systems, Mechanisms and Machines; Omsk, Russia. IEEE Press; 2016. p. 1-4
  15. 15. Rodionova OK, Rodionov AS, Choo H. Network probabilistic connectivity: Exact calculation with use of chains. In: International Conference on Computational Science and Its Application. Lecture Notes in Computer Science, vol. 3036; Heidelberg: Springer; 2004. p. 565-568
  16. 16. Rodionov AS, Migov DA, Rodionova OK. Improvements in the efficiency of cumulative updating of all-terminal network reliability. IEEE Transactions on Reliability. 2012;61(2):460-465
  17. 17. Wood RK. Triconnected decomposition for computing K–terminal network reliability. Networks. 1989;19:203-220
  18. 18. Migov DA. Using node cuts for exact calculation of network probabilistic connectivity. In: Aryn EM, editor. Proc. Int. Conf. on Computational Technologies in Science, Engineering and Education, vol. 2; 20–22–09-2006; Pavlodar, Kazakhstan. 2006. p. 51-58. (in Russian)
  19. 19. Migov DA Random Graph Probabilistic Connectivity Calculation Using Node Cuts [Dissertation] ICM&MG SB RAS, Novosibirsk, Russia: 2008. 97 p. (in Russian) Abstract available from:
  20. 20. Migov DA, Rodionov AS, Rodionova OK, Choo H. Network probabilistic connectivity: Using node cuts. In: EUC Workshop. LNCS, vol. 4097; Springer; 2006. p. 702-709
  21. 21. Migov DA. Calculation of K-terminal network probabilistic connectivity using 2-node cuts. Bull. Inst. of Comp. Math. Geoph. Ser. Computer Science. Proc. Int. Conf. on Problems of Operation of Information Networks; 7–11-08-2006; Berdsk, Russia. 2006;6:134-138. (in Russian)
  22. 22. Migov DA Network probabilistic connectivity computation with use of special kind vertex cuts. In: Proc. Russian Conf. of Young Scientists on Mathematical Modeling and Information Technologies; 1–03–11-2004; Novosibirsk, Russia. ICT SB RAS:2004. (in Russian) Available from:
  23. 23. Burgos JM, Amoza FR. Factorization of network reliability with perfect nodes I: Introduction and statements. Discrete Applied Mathematics. 2016;198:82-90
  24. 24. Burgos JM. Factorization of network reliability with perfect nodes II: Connectivity matrix. Discrete Applied Mathematics. 2016;198:91-100
  25. 25. Migov DA. Computing diameter constrained reliability of a network with junction points. Automation and Remote Control. 2011;72(7):1415-1419
  26. 26. Migov DA, Rodionov AS. Decomposing graph with 2-node cuts for diameter constrained network reliability calculation. In: 7th Int. Conference on Ubiquitous Information Management and Communication; Malaysia. New York: ACM; 2013. Article No. 39
  27. 27. Migov DA, Nesterov SN. Methods of speeding up of diameter constrained network reliability calculation. In: International Conference on Computational Science and its Application. LNCS, Vol. 9156(2); Springer. 2015. pp. 121-133
  28. 28. Rodionov AS, Rodionova OK. Network probabilistic connectivity: Expectation of a number of disconnected pairs of nodes. In: High Performance Computing and Communications. Lecture Notes in Computer Science, vol. 4208; Berlin: Springer; 2006. p. 101-109
  29. 29. Rodionov AS, Rodionova OK, Choo H. On the expected value of a number of disconnected pairs of nodes in unreliable network. In: Computational Science and its Applications. Lecture Notes in Computer Science, vol. 4707; Berlin: Springer; 2007. p. 534-543
  30. 30. Nechunaeva K, Migov D. Speeding up of genetic algorithm for network topology optimization with use of cumulative updating of network reliability. In: Conference on Ubiquitous Information Management and Communication; Bali, Indonesia. New York: ACM; 2015. p. Article No. 42
  31. 31. Migov DA, Nechunaeva KA, Nesterov SN, Rodionov AS. Cumulative updating of network reliability with diameter constraint and network topology optimization. In: Computational Science and its Applications. Lecture Notes in Computer Science, vol. 9786; Berlin. Springer; 2016. p. 141-152

Written By

Alexey S. Rodionov and Denis A. Migov

Submitted: December 8th, 2016 Reviewed: November 3rd, 2017 Published: December 20th, 2017