# Approximate Method to Evaluate Reliability of Complex Networks

Authors: Petru Caşcaval
Journal: Complexity
 (2018)

---

## Abstract

This paper deals with the issue of reliability evaluation in complex networks, in which both link and node failures are considered, and proposes an approximate method based on the minimal paths between two specified nodes. The method requires an algorithm for transforming the set of minimal paths into a sum of disjoint products (SDP). To reduce the computation burden, in the first stage, only the links of the network are considered. Then, in the second stage, each term of the set of disjoint link-products is separately processed, taking into consideration the reliability values for both links and adjacent nodes. In this way, a reliability expression with a one-to-one correspondence to the set of disjoint products is obtained. This approximate method provides a very good accuracy and greatly reduces the computation for complex networks.


---

## Body

## 1. Introduction

The network reliability theory is extensively applied in many real-world systems that can be modeled as stochastic networks, such as communication networks, sensor networks, social networks, etc. A variety of tools are used for system modeling and computation of reliability or availability indices that describe in a certain way the ability of a network to carry out a desired operation. Most tools are based on algorithms described in terms of minimal path set or minimal cut set (see, for example, [1–8]). Unfortunately, the problem of computing the network reliability based on the set of the minimal paths or cuts is NP-hard [7, 9]. For this reason, in case of more complex networks, other techniques for approximate reliability evaluation are also applied, such as those based on network decomposition or on Monte Carlo simulations (see, for example, [10–16]).In this work, we deal with the problem of evaluation of two-terminal reliability or availability indices in medium-to-large networks, based on SDP algorithms, in which both link and node failures are considered.Many authors address this problem assuming that the nodes of the system are perfectly reliable (see, for example, [1, 4–6]). However, in a communication system, nodes also have certain probability of failure so that the reliability evaluation assuming perfect nodes is not realistic.The failure of a node inhibits the work of all links connected to it. Based on this concept, starting from the given network with unreliable nodes, reduced models with perfect nodes but with links having increased failure probabilities can be obtained. This method is simple, but not so accurate. Because the failure of a node inhibits the work of all adjacent links, the work of the links connected to it depends on the state of this common node. However, a reduced model is solved under the hypothesis according to which the failures that affect the network are independent. For this reason, the reliability estimation must be accepted with caution. Indeed, the estimation error of two-terminal network reliability could be unacceptable in many cases, especially when the failure probabilities of the nodes have high values.To highlight this aspect, let us consider a simple network with unreliable nodes as presented in Figure1(a). The reliability of the connection between nodes 1 and 4 has to be evaluated. These two terminal nodes are considered in series with the rest of the network. Three reduced models with perfect nodes and links having increased probabilities of failure are presented in Figures 1(b)–1(d). With dashed line, it is indicated that the failure of a node can be modeled by a cut of the links connected to it. Consequently, in case of a reduced model with perfect nodes, the reliability of the links in the network must be adjusted accordingly. It is easy to observe that other reduced models are also possible.Figure 1
A simple network: (a) initial model; (b–d) reduced models.
(a)
Unreliable nodes
(b)
Perfect nodes—model 1
(c)
Perfect nodes—model 2
(d)
Perfect nodes—model 3For the reduced models presented in Figure1, Table 1 shows how the reliability of each link in the network is adjusted to capture the fact that the nodes of the given network are also unreliable.Table 1
Adjusted reliability values for the links in the network.
Reduced model
New reliability values
Model 1
pa′=pap2, pb′=pbp2, pc′=pcp3, pd′=pdp3, pe′=pep2p3
Model 2
pa′=pap2, pb′=pb, pc′=pcp3, pd′=pd, pe′=pep2p3
Model 3
pa′=pa, pb′=pbp2, pc′=pc, pd′=pdp3, pe′=pep2p3For a numerical evaluation of these approximate models, let us consider a network with the following reliability values for the nodes and the links:p1=0.99, p2=0.98, p3=0.97, p4=0.96, pa=0.99, pb=0.98, pc=0.97, pd=0.96, and pe=0.95. The numerical results expressing the reliability estimation of the connection between nodes 1 and 4 R1‐4 are presented in Table 2.Table 2
Numerical resultsR1–4.
Exact result
Approximate results obtained based on the reduced models
Model 1
Model 2
Model 3
0.9467
0.9466
0.9477
0.9476These numerical results show that the reduced models with perfect nodes might be useful in a way, but the reliability estimation is not so accurate, even for this simple network.A better solution that makes a link-based reliability evaluation algorithm adaptable to communication systems is given by Aggarwal et al. [2]. Thus, based on a SDP expression obtained with the assumption of perfect nodes, the node reliability values are taken into account in a specific mode for each term of the set of disjoint link-products. However, the authors do not completely address aspects of the influence of a node on the links connected to it, as it will be seen in Section 5. Moreover, the method is limited to the SDP expressions generated with a so-called “single variable inversion” (SVI) technique. But, for complex networks, “multiple variable inversion” (MVI) techniques are required [1, 4, 14, 16].In this work, a new approximate method for two-terminal network reliability evaluation with a much better accuracy is proposed. The method is based on algorithms described in terms of minimal path set and covers both SVI and MVI expressions. Just like in [2], in the first stage, the method is focused only on the links of the network. For the any two given nodes, all the minimal paths are enumerated, and then this set of minimal paths is transformed into a set of disjoint products. In the second stage, each term of the sum of disjoint products including state variables associated to the links is processed distinctly by considering both links and adjacent node reliability values.This new approximate method reduces the computation time for large networks to a great extent, compared with an exact method. This reduction in computation time is explained by the fact that the node failures are taken into account only in the second stage when the computation process is simpler, belonging to theOn×m class of complexity, where n is the number of disjoint link-products and m is the number of the network components.The rest of this paper is organized as follows. Section2 introduces notations, assumptions, and a short nomenclature, while Section 3 presents general issues regarding the problem of network reliability evaluation. Section 4 provides a method for exact evaluation of two-terminal network reliability when both node and link failures are considered. Section 5, the most extensive one, presents a new approximate method that reduces the complexity of this problem in medium-to-large networks. Section 6 presents some obtained numerical results. The paper ends with some final remarks presented in Section 7.


## 2. Notations and Preliminary Considerations

### 2.1. Nomenclature

(a)
Reliability: the two-terminal reliability of a stochastic network expresses the probability that there exists at least one path between any two specified nodes (let us say a source node and a target one) which operate successfully
(b)
Connected nodes: two nodes which can communicate with each other are connected; otherwise, they are disconnected
(c)
Minimal path: a minimal set of links and their adjacent nodes whose good operation ensures that two given nodes are connected. For a minimal path, any proper subset is no longer a path
(d)
Uniproduct: Boolean product composed only of distinct uncomplemented variables
(e)
Subproduct: part of a Boolean product that is a complemented or an uncomplemented uniproduct
(f)
Mixproduct: product of one uncomplemented subproduct and one or more complemented subproducts
(g)
Disjoint products: a set of products expressing mutually exclusive states


### 2.2. Notations

(a)
GV,E is a network model with node set V=y1,y2,…,yk and link set E=x1,x2,…,xm
(b)
s,t∈V,s≠t, are the source and target nodes
(c)
px is the reliability of node x∈Vor link x∈E, and qx=1−px
(d)
Rs−t is the two-terminal reliability of network GV,E with s and t the source and target nodes (s−t network reliability)
(e)
PA denotes the probability of the event A


### 2.3. Assumptions

(a)
Each component in the network (i.e., node or link) is either operational or failed, so a logical variable is used to indicate its state. The same notationsy1,y2,…,yk and x1,x2,…,xm are used to denote these logical variables
(b)
The events of failure that affect the nodes or the links in network are stochastically independent


## 2.1. Nomenclature

(a)
Reliability: the two-terminal reliability of a stochastic network expresses the probability that there exists at least one path between any two specified nodes (let us say a source node and a target one) which operate successfully
(b)
Connected nodes: two nodes which can communicate with each other are connected; otherwise, they are disconnected
(c)
Minimal path: a minimal set of links and their adjacent nodes whose good operation ensures that two given nodes are connected. For a minimal path, any proper subset is no longer a path
(d)
Uniproduct: Boolean product composed only of distinct uncomplemented variables
(e)
Subproduct: part of a Boolean product that is a complemented or an uncomplemented uniproduct
(f)
Mixproduct: product of one uncomplemented subproduct and one or more complemented subproducts
(g)
Disjoint products: a set of products expressing mutually exclusive states


## 2.2. Notations

(a)
GV,E is a network model with node set V=y1,y2,…,yk and link set E=x1,x2,…,xm
(b)
s,t∈V,s≠t, are the source and target nodes
(c)
px is the reliability of node x∈Vor link x∈E, and qx=1−px
(d)
Rs−t is the two-terminal reliability of network GV,E with s and t the source and target nodes (s−t network reliability)
(e)
PA denotes the probability of the event A


## 2.3. Assumptions

(a)
Each component in the network (i.e., node or link) is either operational or failed, so a logical variable is used to indicate its state. The same notationsy1,y2,…,yk and x1,x2,…,xm are used to denote these logical variables
(b)
The events of failure that affect the nodes or the links in network are stochastically independent


## 3. Considerations on Network Reliability Evaluation

ConsiderGV,E the network under study and s,t∈V,s≠t, the source and target nodes. For this model, consider the minimal path set MPS=P1,P2,…,Pnp. Note that a minimal path Pi∈MPS is expressed by a product of distinct logical variables associated with some links or nodes of the network, and the reliability of this path is given by
(1)PPi=∏c∈Pipc.Starting from this minimal path set, a structure functionS=⋃i=1npPi is defined, and the two-terminal network reliability of this model is calculated by
(2)Rs−t=PS=P⋃i=1npPi.Efficient methods for enumerating all minimal paths are presented in [14, 17, 18]. To compute the network reliability Rs−t based on (2), the well-known rule of sum of disjoint products is recommended:
(3)P⋃i=1nAi=PA1+PA¯1∩A2+PA¯1∩A¯2∩A3+⋯+PA¯1∩A¯2∩⋯∩A¯n−1∩An.For this purpose, the structure functionS is transformed into an equivalent form S′, composed only of disjoint products (DP), so that the two-terminal network reliability Rs−t is given by
(4)Rs−t=PS′=⋃jDPj=∑jPDPj.Observe that (4) is easy to compute, so that the problem of computing the two-terminal network reliability essentially boils down to generating a new set of disjoint products starting from the set MPS of minimal paths. Unfortunately, this task falls in the NP-hard category.The first computerized SDP algorithm was proposed by Aggarwal et al. [3], but one of the best known SDP algorithms for transforming the structure function to a sum of disjoint products is given by Abraham [4].IfP and Q are two undisjoint products, and x1,x2,…,xs∈P\Q, according to Abraham’s theorem, the following logical expression can be written as follows:
(5)P+Q=P+x¯1Q+x1x¯2Q+x1x2x¯3Q+⋯+x1x2⋯xs−1x¯sQ.Note that, to ensure that two products are disjoint, only a single complemented variable is added with each new term. Abraham’s algorithm is a reference for the so-called SVI algorithms. Two improved SVI algorithms are presented in [19, 20].To reduce the computation time, other approaches based on the so-called MVI technique have been devised (see, for example, [5, 6, 21–23]).When an MVI technique is applied, a product may contain distinct logical variables (complemented or not) but also one or more complemented subproducts. For instance, take seven variables representing a network state where links 2 and 4 are not both operational, link 6 is operational, link 7 is in the failed state, and links 1, 3, and 5 are in a do-not-care state. In an MVI approach, this network state is represented by the Boolean expressionx2x4¯x6x7¯, whereas in an SVI approach, by the expression x2¯x6x7¯+x2x4¯x6x7¯, so that the advantage of the MVI approach is obvious.An excellent survey on MVI techniques can be found in [16]. A new MVI technique, called NMVI, is proposed by Caşcaval and Floria in [1].According to the NMVI method, in order to expand a productQ in relation to a given uniproduct P, so that any new generated product to be disjoint with P, the following two MVI rules are applied.Rule 1.
Type I expansion
Ifx1,x2,…,xs∈P\Q, the following equation can be written as follows:
(6)P+Q=P+x1x2⋯xsQ+x1x2⋯x¯sQ.
WhenP and Q are both uniproducts, for the new term x1x2⋯xsQ, the absorption law is applicable, so that a reduced logical expression with two disjoint products is obtained:
(7)P+Q=P+x1x2⋯x¯sQ.Rule 2.
Type II expansion
ConsiderP=x1x2⋯xiR1, and Q=x1x2⋯xixi+1⋯xs¯R2. By applying the Boolean rule xy¯=x¯+xy¯, the following logical expression results are as follows:
(8)P+Q=P+x1x2⋯xixi+1⋯xs¯R2=P+x1x2⋯xi¯R2+x1x2⋯xixi+1⋯xs¯R2.
WhenR1∈R2, the term x1x2…xixi+1⋯xs¯R2 is absorbed by product P, so that a reduced logical expression composed of two disjoint products is obtained:
(9)P+Q=P+x1x2⋯xi¯R2.As shown in [1], NMVI is an efficient method, providing fewer disjoint products compared with other well-known MVI methods, as CAREL [5], VT [6], or KDH88 [21].In the next two sections, we address the problem of two-terminal network reliability evaluation, in which both link and node failures are considered. First, an exact method of reliability evaluation is discussed. Then, a new approximate method is presented, with the advantage of being much faster and able to offer a very good accuracy.


## 4. Exact Evaluation of Network Reliability

For two given nodes,s and t, an exact evaluation of two-terminal network reliability can be obtained based on the set of minimal paths that include both links and adjacent nodes. Compared with the case in which the study is limited to the links of the network, when the nodes are also considered, the number of the minimal paths is unchanged, but any term is extended by also including the adjacent nodes. To illustrate this method, let us analyze the network N1 presented in Figure 2(a), where the source and target nodes are 1 and 5. These two terminal nodes are considered in series with the rest of the network. For these two given nodes, the set of minimal paths is
(10)MPS=3bf,34beg,24adg,23acf,234aceg,234adef,234bcdg.Figure 2
Network models with unreliable nodes: (a) 5-node, 7-link network (N1); (b) 13-node, 22-link network (N2); (c) 20-node, 40-link network (N3).
(a)
5-node, 7-link network (N1)
(b)
13-node, 22-link network (N2)
(c)
20-node, 40-link network (N3)By applying the NMVI method, the following set of disjoint products results as follows:(11)DPS=3bf,34begf¯,24adfg3b¯,24adgf¯3be¯,23acfb¯4dg¯,234acegb¯d¯f¯,234adefb¯c¯g¯,234bcdga¯e¯f¯.Finally, the reliabilityR1–5 is given by
(12)R1−5=p1p5p3pbpf+p3p4pbpepg1−pf+p2p4papdpgpf1−p3pb+1−pf1−p3pbpe+p2p3papcpf1−pb1−p4pdpg+p2p3p4papcpepg1−pb1−pd1−pf+papdpepf1−pb1−pc1−pg+pbpcpdpg1−pa1−pe1−pf.The same network is analyzed in [2], example 2. So, we compared the numerical result obtained based on this equation with the result generated with equation (21) presented in [2]. These results are identical. For example, assuming for all the nodes a reliability of 0.98 and for all the links a reliability of 0.95, both methods give a reliability value R1–5=0.969611.To cover both nodes and links, much more logical variables are used. The problem that arises in this case is that the number of disjoint products increases to a large extent when complex networks are evaluated. To highlight this aspect, comparative results with respect to the network modelsN2 and N3 given in Figure 2 are presented in Table 3.Table 3
The number of disjoint products. Comparative results.
Network models
Number of minimal paths
Number of disjoint products generated by NMVI, including
Only links
Both links and nodes
N2
281
2269
3151
N3
16618
1799888
3353457Compared with the case in which the study is limited to the links of the network, when the adjacent nodes are also considered, the number of disjoint products increases significantly. The relative growth with respect to the number of disjoint products is about 39% for networkN2, but for the more complex network N3, this relative growth reaches 86%.


## 5. Approximate Approach for Network Reliability Evaluation

The process of generating the set of disjoint products is a difficult one, of NP-hard complexity. In order to reduce the computation time, the process of enumerating the minimal paths and their development as a sum of disjoint products is focused only to the links of the network. For this purpose, for a linkxi∈E, let Xi be a logical variable that reflects the event of successful communication through that branch—that means that the link xi and the two adjacent nodes are operational. Thus, the structure function S can be expressed in terms of these logical variables X1,X2,…,Xm.In the second stage, each term of the sum of disjoint products is processed distinctly by considering both links and adjacent node reliability values. The node reliability values are taken into account in a specific mode for each term of the set of disjoint link-products, when only the adjacent nodes of the links that compose the current product are considered. This is the starting point for this approximate approach.Based on the set of disjoint productsDPS=DP1,DP2,…,DPn, the two-terminal network reliability is computed by applying (4).A termDP in the set of disjoint products is a mixproduct that includes one uniproduct, noted with U, and one or more complemented subproducts. Figure 3 shows such a complex mixproduct.Figure 3
Illustration of a complex mixproduct:DP=X1X2⋯X9X11¯X12¯⋯X18¯X19X20¯X21¯X22X23X24¯.As illustrated in Figure3, the uniproduct U reflects a state of operability of a part of the network that ensures the connection between the source and target nodes. Let SAN be the set of all adjacent nodes of the links that compose the uniproduct U. All these links and all the nodes that belong to SAN are operational. Consequently, the probability of the network state described by U is given by
(13)PU=∏x∈Upx∏y∈SANpy.The main problem is how to compute or at least evaluate with a good accuracy the probability of a network state described by a complemented subproduct (such a subproduct is illustrated in Figure3 with a dashed line).A complemented subproduct reflects a state of inoperability of a branch or of a bigger portion of the network. To begin with, consider the case where such a portion of the network is independent of that portions described by the other complemented subproducts. Under these circumstances, the current term can be independently evaluated. Two cases are distinguished.Case 1 (a single complemented variable (an SVI term)).
Consider a single complemented variableXi¯ (an SVI term) associated with the link xi that connects two nodes; let us say yi and yj (for instance, the variable X11¯ in Figure 3). The probability of this event is
(14)PXi¯=1−pxi′,where
(15)pxi′=pxipyi,ifyj∈SAN,yi∉SAN,pxipyj,ifyi∈SAN,yj∉SAN,pxipyipyj,ifyi,yj∉SAN.Equations (13) and (14) are found in another form in [2] where the same problem of network reliability evaluation is treated. Remember that the method presented in [2] covers only SDP expressions composed of SVI terms.Case 2 (an MVI term).
Consider a complemented subproductX1X2⋯Xk¯ (an MVI term) that describes a state of inoperability of a portion of the network as illustrated in Figure 4.
The probability that this portion of the network to be inoperable is(16)PX1X2⋯Xk¯=1−Q,where the product Q includes not only the reliability of the corresponding links but also the reliability of the adjacent nodes that do not belong to SAN, considered only once. More exactly, the probability Q is computed by the following sequence of steps presented in Pseudocode 1.Figure 4
Illustration of a MVI term:X1X2⋯Xk¯.Pseudocode 1: Computing the product Q.
Q=1;
fori=1:k
Q=Q∗pxi;
ifyi∉SAN then Q=Q∗pyi;
end
ifyk+1∉SAN then Q=Q∗pyk+1;Even though the two portions of the network described by two complemented subproducts may not have any common link, they may have one or even more common nodes. Consequently, the state of inoperability of these two portions of the network may be due to the failure of such a common node. Of course, we refer to a common node that does not belong toSAN.In the first stage, the analysis of these dependencies given by the common nodes is limited to the level of pairs of complemented subproducts. The following three cases are distinguished.Case 3 (two SVI terms with a common node).
Consider two complemented variablesXi¯ and Xj¯ that describe a state of inoperability for two branches xi and xj that have yk as a common node, as illustrated in Figure 5. The node yk∉SAN.Figure 5
Illustration of two inoperable links with a common node.Let us define the probabilitiespxi′ and pxj′ associated with the links xi and xj, given as follows:
(17)pxi′=pxi,ifyi∈SAN,pxipyi,ifyi∉SAN,pxj′=pxj,ifyj∈SAN,pxjpyj,ifyj∉SAN.By applying the theorem of total probability to the event space {yk, y¯k}, the following equation can be written as follows:
(18)PXi¯Xj¯=PX=pykPX∣yk+1−pykPX∣y¯k.As(19)PX∣y¯k=1,PX∣yk=1−pxi′1−pxj′,finally, the equation becomes
(20)PXi¯Xj¯=1−pykpxi′+pxj′−pxi′pxj′.Note that this case is not treated in [2].Case 4 (an MVI term and an SVI one with a common node).
Consider, for example,X1X2X3¯ and X4¯ to be two terms in DP describing a state of inoperability of two portions of the network as illustrated in Figure 6. The common node y2∉SAN.Figure 6
Illustration of an MVI term and an SVI one with a common node.Let us define the probabilitiespx1′, px2′, px3′, and px4′ given as follows:
(21)px1′=px1,ify1∈SAN,px1py1,ify1∉SAN,px2′=px2,ify3∈SAN,px2py3,ify3∉SAN,px3′=px3,ify4∈SAN,px3py4,ify4∉SAN,px4′=px4,ify5∈SAN,px4py5,ify5∉SAN.By applying the theorem of total probability to the event space {y2, y¯2}, the following equation can be written as follows:
(22)PX1X2X3¯X4¯=PX=py2PX∣y2+1−py2PX∣y¯2.As(23)PX∣y¯2=1,PX∣y2=1−px1′px2′px3′1−px4′,finally, the following equation results in
(24)PX1X2X3¯X4¯=1−py2px1′px2′px3′+px4′−px1′px2′px3′px4′.Note that, if the two events were treated independently, the following equation would result in(25)PX1X2X3¯PX4¯=1−px1′px2′px3′py21−px4′py2=1−py2px1′px2′px3′+px4′−px1′px2′px3′px4′py2<PX1X2X3¯X4¯.Remark 1.
Equation (25) shows that when a common node is not taken into account, the reliability estimation is a pessimistic one.Case 5 (two MVI terms with a common node).
Consider, for example,X1X2¯ and X3X4¯ to be the two MVI terms describing a state of inoperability of two parts of the network, as illustrated in Figure 7, where the communication between nodes 1 and 2 and between nodes 3 and 4 is not possible. The common node y5∉SAN.
Let us define the probabilitiespx1′, px2′, px3′, and px4′ given by the following:
(26)pxi′=pxi,ifyi∈SAN,pxipyi,ifyi∉SAN,i=1,2,3,4.Figure 7
Illustration of two MVI terms with a common node.The probability of this state,PX1X2¯X3X4¯, can be determined by applying the rule of total probability to the event space y5,y¯5.IfX=X1X2¯X3X4¯, the following equation can be written as follows:
(27)PX=py5PX∣y5+1−py5PX∣y¯5.Obviously,PX/y¯5=1.
(28)PX∣y5=1−px1′px2′1−px3′px4′=1−px1′px2′−px3′px4′+px1′px2′px3′px4′.Finally, the equation becomes(29)PX1X2¯X3X4¯=1−py5px1′px2′+px3′px4′−px1′px2′px3′px4′.To exemplify these 5 rules previously defined, consider the mixproduct(30)DP=X1X2⋯X9X11¯X12¯⋯X18¯X19X20¯X21¯X22X23X24¯,as illustrated in Figure 3. The mixproduct DP includes the uniproduct U=X1X2⋯X9 and for this operable path, the set of adjacent nodes is SAN=y1,y2,…,y10.Taking into account the common nodes for the SVI and MVI terms, the probability of the mixproductDP can be evaluated with a good accuracy by the following:
(31)PDP=PUPX11¯PX12¯X13¯PX14¯X15¯PX16¯×PX17¯X18¯PX19X20¯X21¯PX22X23X24¯.By applying the rules presented before, the following equations result in(32)PU=px1px2⋯px9py1py2⋯py10,PX11¯=1−py11px11py12,PX12¯X13¯=1−py13px12+px13′−px12px13′,where px13′=px13py14.
(33)PX14¯X15¯=1−py15px14+px15−px14px15,PX16¯=1−py15px16py16anapproximateevaluation,PX17¯X18¯=1−py18px17′+px18′−px17′px18′,where px17′=px17py17 and px18′=px18py19.
(34)PX19X20¯X21¯=1−py20px19px20+px21′−px19px20px21′,where px21′=px21py21.
(35)PX22X23X24¯=1−py22px22py23px23py24px24py25.Observe that, related to the probability of this mixproduct, an approximation is made with respect to the termsX14¯, X15¯, and X16¯, because the links x14, x15, and x16 have a common node, y15∉SAN. This case is discussed in more detail below.Case 6 (many terms with a common node).
Consider three linksx1, x2, and x3 with a common node and the network state reflected by the SVI terms X1¯, X2¯, and X3¯, as illustrated in Figure 8.
Suppose thaty4∉SAN. Let us first define the probabilities px1′, px2′, and px3′ by the following:
(36)pxi′=pxi,ifyi∈SAN,pxipyi,ifyi∉SAN,i=1,2,3.Figure 8
Illustration of three SVI terms with a common node.In order to evaluate the probabilityPX1¯X2¯X3¯, the theorem of total probability is applied to the event space {y4, y¯4}. The following equation results in
(37)PX1¯X2¯X3¯=PX=py4PX∣y4+1−py4PX∣y¯4.Obviously,PX/y¯4=1. When the node y4 is operational, X1¯, X2¯, and X3¯ reflect independent events, so that
(38)PX1¯X2¯X3¯=PX1¯PX2¯PX3¯.Consequently, we have(39)PX∣y4=1−px1′1−px2′1−px3′=1−px1′−px2′−px3′+px1′px2′+px1′px3′+px2′px3′−px1′px2′px3′.Finally, the equation becomes(40)PX1¯X2¯X3¯=1−py4px1′+px2′+px3′−px1′px2′−px1′px3′−px2′px3′+px1′px2′px3′.Observe that, in case of an exact evaluation, the equation is composed of23=8 terms. This result can be generalized for the case with more events X1¯,X2¯,…,Xm¯ that depend on the state of a common node. The equation for computing the probability PX1¯X2¯⋯Xm¯ comprises 2m terms. To reduce the computation time, the method we propose is limited to the pairs of events depending on the state of a common node, for which the equation (20, 24, or 29 as is the case) comprises only four terms.This is the approximation that may slightly affect the result given by the method we propose. Also, this work does not treat those cases when two MVI terms have two or more common nodes, considering that these cases are very rare. Nevertheless, this method provides a network reliability evaluation with a very good accuracy, as can be seen in the next section. In all the checks we have made, this method has generated exact values or slightly pessimistic results. So, the reliability value given by this method can be interpreted as a lower limit and it can be explained on the basis of (25) and Remark 1. This aspect is very important for a reliability study.Before ending this section, an answer to the next question is required: why did this method focus only on minimal paths and not on minimal cuts at all? Indeed, it is well known that for networks with high reliability, the approaches based on minimal cuts are generally more appropriate for an approximate evaluation. However, in our case, an approach similar to that applied to the minimal paths is no longer appropriate, because when both node and link failures are considered, one must take into account a set of cuts consisting of nodes, a set of cuts consisting of links, and another one that comprises both nodes and links. So, when the nodes are also considered, the number of minimal cuts increases very much. For this reason, the proposed method is focused only on minimal paths.


## 6. Numerical Results

To illustrate the efficiency of this approximate method, we consider the network modelsN2 and N3 presented in Figure 2. For these networks, Table 4 presents comparative results, by assuming for all the nodes a reliability value of 0.98 and for all the links a reliability value of 0.95. Observe that the proposed method gives an accurate result for the network N2, and it gives a slightly approximate value with five accurate decimal places for the larger network N3.Table 4
Network reliability evaluation (Rs−t). Comparative results.
Network model
Source and target nodes
Exact method based on NMVI
The proposed method
N2
s=1, t=13
0.982883
0.982883
N3
s=1, t=20
0.959579
0.959575Computing time for reliability evaluation is presented in Table5. Compared to the exact method presented in Section 5, for network model N3, the proposed approximate method greatly reduces the computational time, from 57 min 17 s to 18 min 43 s.Table 5
Computing time for reliability evaluation.
Network model
Exact method based on NMVI
The proposed method
N2
0.1 s
0.06 s
N3
57 min 17 s
18 min 43 sThe values presented in Table5 highlight the rapid growth of the computation time for the reliability evaluation with an increasing network size. The methods of network reliability evaluation based on SDP algorithms fall in the NP-hard category and, consequently, are difficult to apply for very large networks, such as social networks. In these cases, other techniques for approximate evaluation can also be applied, especially the Monte Carlo simulation (see, for example, [24–27]). Even so, the methods based on SDP algorithms are still necessary for the validation of simulation programs.


## 7. Final Remarks

In this work, the problem of two-terminal network reliability evaluation in which both link and node failures are considered is discussed. An approximate method that provides a very good accuracy is proposed. Compared to an exact method, this approximate method greatly reduces the computation time for complex networks.The proposed solution can be applied with any SDP algorithm, but the accuracy of the reliability estimation depends on the method used for transforming the set of minimal paths into a set of disjoint products. When the number of disjoint products is lower, the reliability estimation is better. For this reason, efficient MVI algorithms as NMVI or the hybrid algorithm given by Chaturvedi and Misra [23] are recommended. Another approach based on binary decision diagrams (BDDs) is also recommended [28].



---

*Source: 5967604-2018-11-12.xml*