Research on reliability of complex network for estimating network reliability

Abstract

Network reliability is an important index in measuring the reliability of large-sized network, but network reliability calculation is a NP-hard problem, and simulation is a feasible approach to estimating network reliability. Aiming at the problem of reliability evaluation in a complex network, develop a general scheme that combines Crude Monte Carlo and event-driven, and a novel reliability assessment method based on event-driven is put forward. The unbiased and the accurate estimation of the proposed method are analyzed from a theoretical point of view. Experimental results demonstrate that the proposed method is more efficient than other algorithms, such as high simulation efficiency, fine estimation accuracy and greatly reducing the algorithm complexity.

Keywords

Network reliability failure events Monte-Carlo event-driven connectivity

1 Introduction

With the continuous development of society and science technology, human society has accelerated the process of networking. Such as electric power, transportation, urban water supply, gas network and other systems are very much important network systems that maintain the function of the modern city and economic development. Once a fault occurs, it will cause a significant and even disastrous impact. So network reliability is an important aspect of ensuring network security [1]. Especially, network security has become the attention focus of the international society in recent years. In view of the present network situation, we need to strengthen developing a network and a network reliability assessment, and improve network security [2]. So analysis and estimating of the network reliability are extremely important for a complex network. It can effectively improve the network construction and management capabilities through studying the reliability of a complex network, it helps improving the factor of network security, and it is conducive to improving survivability and survivability of the network. So it is extremely important to evaluate the reliability of a complex network.

Reliability is the key aspect to measure the performance of the network system. As is well known, the reliability assessment of a complex network system is NP-hard problem [3], because their computational effort growing exponentially and increases the number of nodes and links in the network. Searching for efficient computing algorithm that can evaluate the reliability is a hot research topic in large complex network system. In recent years, many people have put forward a variety of methods to calculate the reliability of the network and they have made many contributions. To sum up, these methods can be roughly divided into two categories. One is a method that can accurate compute the reliability of the complex network, including inclusion-exclusion principle [4 –8], the state enumeration [1, 9] and the factor decomposition [10 –14]. For example, the basic idea of the factor decomposition is to select a side of the network, and its reliability problem is decomposed into two sub problems. The first sub problem is thus, assuming that the selected edge is failed. The second sub problem is assuming that the selected edge of the network is work, so the reliability of the network is obtained by solving these sub problems. But factor decomposition algorithm can only decompose the state of one selected side every time, and the decomposition process of the algorithm is very slow, and the number of the decomposition is much more, thus it is not suitable for calculating the reliability of the large and dense network. The complexity of the exact reliability algorithms is exponential increasing with the increasing scale networks and the number of nodes increasing, and this kind of algorithms can only be applied to analyze the reliability in medium and small scale networks. For large complex engineering network system, it cannot be solved because of the complexity of the network. The amount of calculation is rapidly expanding, and the computational efficiency of the algorithm is becoming lower and lower.

The other is the method that can estimate network reliability approximately. The approximate calculation method is used to approximate the exact value through the boundary value of the reliability. Especially, with the increasing of the network scale, these methods that can approximately estimate network reliability have been attracted much attention from researchers. These methods mainly have the upper and lower bounds of network reliability [15, 16], such as Monte Carlo(MC), improved MC [17 –19]. A summary of combinatorial as well as computational properties of the diameter-constrained network reliability is presented [20 –23], which extends well-known properties of the classical network reliability measure. An algorithm for computing the reliability is presented, which can compute the network reliability [24]. Propose a novel method for the network reliability in terms of capacitated-minimum-paths without knowing minimum-paths in advance [25], and a simple algorithm for evaluating the network reliability based on the minimal cut set [26, 27] is presented in [28]. They are a simple and efficient. Two-terminal reliability problem [29, 30] is solved, which find the best possible bounds on the probability of an operating path between two given nodes s and t without assuming independence of failures [31]. Utilize a deep connection between reliability and chip firings on graphs to improve previous bounds for reliability, and a more accurate characterization of the matroid complex prove useful in improving the bounds on all-terminal network reliability [32]. The study serves as a guide to research the problem of the network reliability, as its computation is known to be NP-Hard in exact computation of network reliability, some scholars have adopted the accurate calculation method, such as factoring algorithm [33 –35] and Binary Decision Diagram algorithm [36, 37], etc. but some scholars have studied the approximation algorithm through the above introduction. In addition, there are upper and lower bounds algorithms and Monte Carlo. For a larger network, the network reliability calculation of precise value is very difficult. However, considering time and accuracy. It is unfeasible based on the exact algorithm of the network reliability. Exact computation of network reliability is feasible only for small sized networks. Numerous researchers propose some algorithms which approximately estimate networks reliability. Especially, Monte Carlo simulation is one of the optimal algorithms to estimate the network reliability, etc. When the upper and lower bounds method is determined to determine the range of the ideal reliability bounds, usually sacrifices computational complexity. Monte Carlo algorithm is a simulation method based on probability and statistics, and it can simulate the actual physical process. It can solve many problems that are too complex to establish accurate mathematical models. There are some advantages of low complexity and rather intuitive, and it is widely used to simulate study for a large network.

Which improve effectively the estimation accuracy of CMC using constant sampling times. But these methods of sampling are also time-driven, they still require some prior information of the network such as paths-sets or cuts-sets or other information. Because of the reasons summed up above. Hence, the algorithm we proposed works better than their algorithms from theory and practice point of view. In addition, the testing results show that the proposed method can have better efficiency for solving the complex network reliability problem. In this present paper, we have proposed combining Event-driven with Monte Carlo (EMC) to minimize the cost under reliability constraints. The method is guaranteed to be effective when the failure probabilities of the edges are sufficiently small. We have compared the proposed method with previous work for solving the related problems in [38, 39]. Hence, the algorithm which we proposed works better than their algorithms from a theoretical point of view. In addition, the testing results show that the proposed method can have better efficiency for solving the complex network reliability problem.

2 Definitions and notation

We deal with an undirected graph G = (V, E) is a set of the nodes (or vertices) V = {v₁, v₂, ⋯ , v_i, ⋯ v_N} that represents the nodes of a network, connected together by a set of the edges(or links) E ={ e₁, e₂, ⋯ , e_i, ⋯ e_M }, where N and M are the number of the vertices and the number of the edges in the graph, respectively. Depending on the edges’ states, the network has two possible states. Each edge can be either operational (up) or failed (down). The failure edges are assumed to be independent events. If edge e_i is operational, then x (e_i) = 1. If edge e_i is failed, then x (e_i) = 0.

Suppose that edge e_i ∈ E is operational with probability p (e_i), that is, p (e_i) is the network reliability of edge e_i, and unreliability q (e_i) = 1 - p (e_i) is defined as the probability that a set of edges e_i is failed in the undirected graph. We postulate that element failures are mutually independent events.

The network state is a binary random variable. We assume that the network state is a vector X ={ x (e_i) |e_i ∈ E }, so network state vector X has a probability, which is formulated as follow. $Pr (X) = \prod_{e_{i} \in E} {1 - p (e_{i}) + x (e_{i}) [2 p (e_{i}) - 1]}$ (1)

As we see these next definitions allow us to compute the network reliability R (G). Because the network reliability is closely related to the probability of the connected network, we have that R (G) = Pr( X ).

This function Ψ ( X ) is referred to as the structure function of the graph, if the network state X expresses that the network is operational, Ψ ( X ) = 1, otherwise Ψ ( X ) = 0. Suppose that S is state space of the network state X , so there are 2^M elements in the state space S, and it is the complete set of all network states. Thus, the network reliability is as follow. $R (G) = E [Ψ (X)] = \sum_{X \in S} Pr (X) Ψ (X)$ (2)

In fact, from the above results, we can conclude that the exact calculation formula is a NP-hard problem. The number of the elements in the state space S is an exponential function of the link number M, and enumerating these states is a very high complexity. Therefore, it is an effective method to use the MC simulation to estimate the formula (2).

3 The method of CMC for estimating the network reliability

The Monte Carlo is a simulation method based on probability and statistics experiments, and the Monte Carlo constructs a series of samples according to the probability model of the random variables in some systems. We use samples to calculate the solutions of the target samples, and the estimation of the solution of the target is obtained by statistical processing. The CMC network reliability simulation based on time-driven is briefly defined as follows.

According to probability model of the formula (1), randomly generate K independent samples from the network state space S, for the paper convenience, this article record the independent samples as X ¹, ⋯ , X ^K respectively. Then the estimate value for the network reliability of the formula (2) is defined as follow. $R (G) = \frac{1}{K} \sum_{i = 1}^{K} Ψ (X^{i})$ (3)

It can be easily proved that E [R (G)] and R (G) are equal, that is the formula (3) is unbiased estimation of the formula (2), as the variance of R (G) is defined as follows. $Var [Ψ (X)] = R (G) [1 - R (G)]$ (4)

Therefore, the variance of the estimator R (G) is as follows. $Var [R (G)] = \frac{1}{K} R (G) [1 - R (G)]$ (5)

From formula (5), we know that the estimation accuracy of network reliability is related to the variance of the sample K and statistic Ψ ( X ). When the number of the sample K is certain, the smaller statistic Ψ ( X ) is, the more accurate the estimation is.

Now the algorithm of CMC is described in detail as follows.

Input: G = (V,E), each link reliability p (e_i), sample K, k = 0
Output: Calculate network reliability R(G)
1: For t = 0 to t = K do
2: For i = 0 to i = M do
3: If p (e_i)>U (Generate random variables for e_i, U ∈ [0)
4: then x (e_i) =1
5: End If
6: i++
7: End For
8: If ψ (X) = (obtain network state vector X )
9: then k +
10: End If
11: ++
12: End For
13: R(G)=
14: Return(R)

4 The EMC method for estimating network reliability

The Crude Monte Carlo is a noteworthy simulation tool for estimating network reliability. In order to further study estimating network reliability combined with Crude Monte Carlo, and we have carried out the relevant study. The CMC is a method of discrete time-driven, which updates network status with increasing of the time unit, generate some failed and connected events in each time unit, and updates the network status (failed network state or connected network state), then simulate using time-driven simulation. But in this paper, we develop a new method that combines event-driven and Crude Monte Carlo. The main idea is to find a more efficient simulation method, which creates failed event time of each edge in undirected graph G. To achieve driven simulation, must look for the highest priority failed time and the corresponding event, and update network states. We will introduce a new estimating method based Monte Carlo, which is designed as shown in Fig. 1.

Fig.1

Process diagram for the improved method.

We design three parts in order to realize the EMC method, which is formulated as follows.

Suppose that Event Table (ET) and Time Pointer (TP) are used to describe event table and the time pointer of failure events in each link.

Suppose that time updating is used to update time pointer in the highest priority event.

Suppose that event updating is used to update the network status and event table.

Based on the above analysis, the operations of the event table are defined as follows.

Insert (ET, e_i, TPe_i). The fault event of parameter (e_i, TPe_i) is inserted into ET, and the event is updated.

Remove (ET, e_i, TPe_i). The fault event of parameter (e_i, TPe_i) is deleted from ET, and the event is updated.

Get-TP_min(ET). Find and return the most priority time pointer TP_min from ET, and time isupdated.

4.1 The EMC method

Assume that the sample K times in link state x (e_i) for edge e_i, Y_i is represented the number of link failure events, that is, there are Y_i times when x (e_i) = 0. Because the probability p (e_i) of connected state is constant, so Y_i is a random variable which obeys binomial distribution, which is defined asfollows.

$\begin{matrix} Pr (Y_{i} = y) = (\begin{matrix} K \\ y \end{matrix}) q^{y} (e_{i}) p^{K - y} (e_{i}), \\ 0 \leq y \leq K \end{matrix}$ (6)

The CMC algorithm constructs the state sequence X (e_i) with the length of K by K random variables U for link e_i. But the difference between EMC and CMC is that, EMC constructs directly time pointer sequence TPe_i of fault events through Y_i, which confirms X (e_i) implicitly, as shown in Fig. 2.

Fig.2

Sampling Of CMC and EMC.

Sampling of EMC is divided into two steps:

Generate binomial variable Y_i based on K and p (e_i).

Randomly generated Y_i time pointer TPe_i about fault event of e_i in [0,K].

A brief description of the specific steps of EMC is formulated as follows.

Step 1. Initialize K, let k = 0, generate Y_i time pointer TPe_i for all the links e_i, and Insert(ET, e_i, TPe_i).

Step 2. If ET is empty, then Goto Step 6, otherwise, Goto Step 3.

Step 3. Let x (e_i) = 1, and let TP_min = Get - TP_min (ET).

Step 4. For all e_i, if TPe_i = TP_min, then let x (e_i) = 0, and Remove (ET, e_i, TPe_i).

Step 5. Obtain the network status X , if Ψ ( X ) = 1, then let k++, otherwise, Goto Step 2.

Step 6. So get estimated value of network reliability, let $R (G) = \frac{k}{K}$ .

4.2 A proof of the unbiasedness for the EMC

The estimation of the EMC is to be proved unbiased, and it can be converted to sample following Pr( X ) probability according to the formula (1) in the network status X , thus is proved. In the following, we need to prove it. Suppose that all elements of x (e_i) in the network status X are independent, and that can be proved. Pr(x (e_i) = 0) = q (e_i).

Combination the formula (6) and the EMC sampling method, then

$\begin{matrix} Pr (x (e_{i}) = 0) \\ = \sum_{y = 0}^{K} Pr {Y_{i} = y} Pr {x (e_{i}) = 0 | Y_{i} = y} \end{matrix}$ (7)

Because events are randomly distributed in K sampling, That is, for a given y, then $Pr {x (e_{i}) = 0 | Y_{i} = y} = \frac{y}{K} .$

Based on the formula (6) and the formula (7) can be transformed into the following formulas. $\begin{matrix} Pr (x (e_{i}) = 0) \\ = \sum_{y = 0}^{K} {\frac{y}{K} (\begin{matrix} K \\ y \end{matrix}) q^{y} (e_{i}) p^{K - y} (e_{i})} \end{matrix}$ (8) $\begin{matrix} Pr (x (e_{i}) = 0) \\ = q (e_{i}) \sum_{y = 1}^{K} {(\begin{matrix} K - 1 \\ y - 1 \end{matrix}) q^{y - 1} (e_{i}) p^{K - y} (e_{i})} \end{matrix}$ (9)

Thus, the sum of the probability for the formula (9) is the Binomial distribution and its value is 1.

This proves that Pr(x (e_i) = 0) = q (e_i). So, EMC is an unbiased evaluation of R (G).

4.3 Variance analysis of the EMC

When x¹ (e_i) , x² (e_i) , ⋯ , x^K (e_i) is generated, we use the same random variable, and network state vector X ¹, X ², ⋯ , X ^K of the EMC is related, therefore, the evaluation variance of the EMC can’t be calculated by the formula (5).

Because both EMC and MC belong to CMC, and the variance is a function that adds values from the network structure function Ψ ( X ). When the sample size is K, according to the formula of the variance for the sum of variables, so the evaluation variance of MC can be calculated by the formula (10):

$\begin{matrix} Var (R) \\ = \frac{\sum_{i = 1}^{K} Var [Ψ (X^{i})] + 2 \sum_{i = 1}^{K} \sum_{j = i + 1}^{K} Cov [Ψ (X^{i}), Ψ (X^{j})]}{K^{2}} \end{matrix}$ (10)

Any two state vectors X ⁱ and X ^j are independent in CMC and covariance between them is 0. ${Cov}^{CMC} = Cov [Ψ (X^{i}), Ψ (X^{j})] = 0$

For corresponding elements of any two state vectors, xⁱ (e_i) ∈ X ⁱ is closely related to x^j (e_i) ∈ X ^j in the EMC, so Cov (xⁱ (e_i) , x^j (e_i)) < 0, then Cov^BEMC < 0. Because of the complexity of the network structure function Ψ ( X ), it is complicated to make Cov^BEMC precise, but there is Var^BEMC (R) < Var^CMC (R).

5 Simulation experiment and results analysis

In order to analyze efficiency of these algorithms and the relationship between the networks complexity, we take the grid network of 25 nodes as an example to carry out the simulations. The grid network is generated three kinds of link number: 40, 56 and 72, and their network complexity increases. As shown in Fig. 3, and there are network A, B and C.

Fig.3

Three kinds the grid network of 25 nodes.

Under the same hardware environment, the CMC and EMC are used to simulate for the reliability of the network A. There are these parameters: p (e_i) = 0.99, e_i ∈ E and K = 10⁶.

The estimated results and consumption time of the two methods were recorded respectively, and each method is simulated for 30 times, then the evaluation standard deviation of each method is calculated based on the 30 times statistical values. The standard deviation formula is defined as follow, and the results are shown in Fig. 4. $Std = \sqrt{Var}$ (11)

According to the factor theorem [39], the accurate reliability value of the network A can be calculated, and its value is R (G) = 0.99958. The experimental results are as shown in Fig. 4(a), and the evaluation mean values that the two methods obtained are astringed the accurate value, and the unbiased analysis and variance analysis of the 4 section areverified.

The experimental results are shown in Fig. 4(b), and the proposed algorithm not only consumes time less than CMC, but also greatly improves the simulation efficiency.

Fig.4

(a) Simulation accuracy comparison.

Fig.4

(b) Consumption time comparison.

In order to compare the efficiency of each method and the relationship between network size and link state, and the above mentioned method is used to carry out nine times simulations respectively based on p (e_i) = 0.9, 0.99 and 0.999 in Fig. 3. To reflect the superiority of the method in this paper, we do a lot of comparison experiments according to two improved algorithms based on CMC in literature [38, 39] apart from CMC under the same simulation objects and environment, and the results of the experiments are as shown in Table 1.

Table 1

Simulation comparison under different network conditions

		p (e_i) =0.9		p (e_i) =0.99		p (e_i) =0.999
		Standard deviation	Time(s)	Standard deviation	Time(s)	Standard deviation	Time(s)
CMC	A	4.1×10^–4	2.682	3.2×10^–5	2.157	3.3×10^–6	2.131
	B	2.3×10^–4	3.183	2.2×10^–5	2.278	2.0×10^–6	2.239
	C	1.0×10^–4	3.345	3.6×10^–6	2.451	1.7×10^–6	2.423
EMC	A	3.6×10^–4	2.455	2.5×10^–5	0.952	2.4×10^–6	0.210
	B	1.9×10^–4	2.949	1.7×10^–5	1.367	1.9×10^–6	0.305
	C	7.2×10^–5	3.058	2.3×10^–6	1.749	1.7×10^–6	0.422
[38]	A	3.8×10^–4	2.314	3.0×10^–5	2.049	3.1×10^–6	1.863
	B	1.9×10^–4	3.121	1.6×10^–5	2.188	2.0×10^–6	1.905
	C	1.1×10^–4	3.572	3.5×10^–6	2.477	1.9×10^–6	2.245
[39]	A	3.2×10^–4	2.732	2.5×10^–5	2.311	2.6×10^–6	2.283
	B	1.7×10^–4	3.378	1.5×10^–5	2.565	1.7×10^–6	2.543
	C	6.9×10^–5	3.793	2.2×10^–6	2.849	1.7×10^–6	2.787

From Table 1, it is easy to find that consumption time of the four methods is gradually reduced with the increase of link reliability when the network complexity is the same. But the reduction of the EMC is the largest in the CMC, literature [38] and literature [39]. Because the EMC needs to produce less random seeds under the same sample in the simulation experiments. At the same time, when the reliability is higher, and the EMC jumps over a large number of connected events and gets a higher efficiency. There are some application limitations for the reduced preprocessing in literature [38], and the simplification of network topology is limited in Fig. 3, therefore, its time consumption is basically equivalent to CMC. Need to calculate the network cut set before sampling in literature [39], so its time consumption is the biggest in these methods, and it is not very sensitive when link reliability is changed, and sampling pretreatment has high complexity.

It is consumption time that four methods are simulated in Network C, which is described as shown in Fig. 5. Consumption time of the EMC is the least, and its consumption time is 3.058 s when p (e_i) =0.9.

Fig.5

Consumption time in network C.

Experiment results are illustrated in Fig. 6 when p (e_i) =0.90, we see that consumption time of these algorithm s is the higher with the improvement of the network complexity, but the EMC is the least in different complex networks. The EMC is the best algorithm in these algorithms too. Consumption time of four methods is gradually increased with the increasing of the network complex.

Fig.6

Consumption time in Network A, B and C.

Experimental results are illustrated in Fig. 7 when p (e_i) =0.99. We see that consumption time of the EMC is the least in different complex networks. The EMC is the best algorithm in these algorithms too. Consumption time of four methods is gradually increased with the increase of the network complex.

Fig.7

Consumption time in network A, B and C.

Experimental results are illustrated in Fig. 8 when p (e_i) =0.999. We see that consumption time of the EMC is the least in different complex networks. The EMC is the best algorithm in these algorithms too. Its consumption time of the EMC is becoming lower, but the changes of consumption time for other algorithms are not obvious when their network reliability is very much high.

Fig.8

Consumption time in network A, B and C.

Exploiting all methods do a number of experiments in network C and experimental results are illustrated in Fig. 9. We do all experiments in the same complex network, and find that consumption time of each method is gradually reduced with the increase of link reliability, and reducing scope of the EMC is the largest in four methods, and find that consumption time is the least too. Since the EMC needs to produce less random seeds under the same sampling in the simulation experiments. Meanwhile, the EMC jumps over a large number of connected events and gets a higher efficiency when the reliability is higher.

Fig.9

Comparison of consumption time in network C.

With the increase of link reliability, consumption time of the four methods is gradually reduced when the network complexity is the same. Meanwhile, estimated standard deviation has a trend of decreasing gradually. The dimension of the state vector will be increased, and time consumption will be increased accordingly when the network complexity increases. From formula (5) in CMC, we see that, when the link reliability becomes larger, then p (e_i)↑ , R (G) ↑ , Std^CMC ↓. Combined with the variance analysis of the 4.3 section, then p (e_i)↑ , Std^EMC ↓, and simulation results are coincident with the Table 1. The results have further verified variance theory analysis of literature [20] and literature [39], and this paper will not repeat them.

When the link reliability and the network complexity are the same, time consumption of the EMC is the least, and the estimation accuracy of literature [39] is the highest, because data is pre-treated using cut sets in literature [39], thus, the problem is transformed into the segment simulation of cut set, and compresses sampling dimension, so this method has a lower estimate variance, but this improvement of estimation accuracy is small, but time consumption is almost an order of magnitude higher than the EMC. It is a strategy that improves accuracy by sacrificing efficiency, and we can make specific tradeoffs combined with practical applications.

6 Conclusions

The distribution of network fault events on the time axis has been analyzed based on that, the reliability of complex network based on Event-driven mechanism has been studied, and a Monte Carlo estimation method based on the events that were constructed using time pointer has been proposed. We compared and analyzed these problems of estimation variance and its accuracy from a theoretical point of view, and we did lots of the experiments by the EMC, CMC and two improved algorithms, and analyzed the experimental data. Experiment results show that the proposed algorithm in this paper greatly reduces the complexity and improve the estimation accuracy, and it is an effective simulation method for dealing with large scale network and the reliability problems of extreme values.

Footnotes

Acknowledgments

The authors would like to thank for financial support by youth fund project of the humanities and social sciences of Education Ministry (No. 15YJC870004), Social Sciences fund project of Hunan Province (No. 13YBA302) and education Science in Hunan province in 12th Five-Year planning project (XJK014CGD081, XJK011BXJ004).

References

Kavousifard

and Samet

, Consideration effect of uncertainty in power system reliability indices using radial basis function network and fuzzy logic theory, Neurocomputing74 (2011), 3420–3427.

Yeh

W.-C.

, A novel node-based sequential implicit enumeration method for finding all d-MPs in a multistate flow network, Information Sciences (2015), 283–292.

Colbourn

C.J.

, The Combinatorics of Network Reliability, Oxford University Press, New York, 1987.

Buzacott

J.A.

, Node partition formula for directed graph reliability, Networks17(3) (1987), 227–240.

Luo

and Trivedi

K.S.

, An improved algorithm for coherent system reliability, IEEE Trans Reliab47(1) (1998), 73–78.

Zhao

L.C.

and Kong

F.J.

, A new formula and an algorithm for reliability analysis of network, Microelectron Reliability37(4) (1997), 511–518.

Yeh

W.C.

, A greedy branch-and—bound inclusion-exclusion algorithm for calculating the exact multi—state network reliability, IEEE Trans on Reliability57(1) (2008), 88–93.

Buzacott

J.A.

and Chang

S.K.

, Cut set intersections and node parti-tion, IEEE Trans Reliab31(4) (1982), 385–389.

Lin

Y.K.

, Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity, Reliability Engineering & System Safety92(5) (2007), 646–652.

10.

Resende

, Implementation of a factoring algorithm for reliability evaluation of undirected networks, IEEE Trans on Reliability37(5) (1988), 462–468.

11.

Soh

and Rai

, An efficient cut set approach for evaluating com-munication-network reliability with heterogeneous link-capacities, IEEE Transactions on Reliability54(1) (2005), 133–144.

12.

Wood

P.K.

, A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliabili-ty, Networks1(5) (1985), 173–190.

13.

Satyanarayana

and Chang

M.K.

, Network reliability and the factoring theorem, Networks13 (1983), 107–120.

14.

Yi-Feng

, Xiu-Zhen

and Ming-Qi

, Algorithm for compu-ting two-terminal network reliability based on network simplification and vector set decomposition, Application Research of Computer27(12) (2010), 4750–4754.

15.

Sarintip

and Kailash

, An algorithm for lower relia-bility bounds of multistate two-terminal networks, IEEE Trans Reliability55(2) (2006), 199–206.

16.

Kin-Ping

, Monte carlo network reliability ranking estimation, IEEE Trans Reliability56(1) (2007), 50–57.

17.

Yeh

and Lin

, A particle swarm optimization approach based on monte carlo simulation for solving the complex network reliability problem, IEEE Trans Reliability59(1) (2010), 212–221.

18.

Yeh

W.-C.

, Lin

Y.-C.

and Chung

Y.Y.

, A particle swarm optimization approach based on monte carlo simulation for solving the complex network reliability problem, IEEE Trans Reliability59(1) (2010), 212–221.

19.

Karp

R.M.

and Luby

, Monte-Carlo algorithms for the planar multiterminal network reliability problem, Journal of Complexity (1) (1985), 45–64.

20.

Petingi

, Diameter-related properties of graphs and applications to network reliability theory, WSEAS Transactions on Mathematics9(12) (2013), 884–894.

21.

Cancela

and Petingi

, On the characterization of the domination of a diameter-constrained, Discrete Applied Mathematics154(13) (2006), 1885–1896.

22.

Canale

, Cancela

and Robledo

, On computing the 2-diameter-constrained K-reliability of networks, International Transactions in Operational RE-Search20(1) (2013), 49–58.

23.

Petingi

, A diameter-constrained network reliability model to determine the probability that a communication network meets delay con-straints, WSEAS Transactions on Commu-Nications6(7) (2008), 574–583.

24.

Yeh

W.-C.

, A novel method for the network reliability in terms of capacitated minimum-pathswithout knowing minimum-paths in advance, Journal of the Operational Research Society56 (2005), 1235–1240.

25.

Zhen

, Xin-Li

and Guo-Xun

, Algorithm for computing mult-state network reliability based on transition of d-mincuts and d-minpaths, Application Research of Computers28(11) (2011), 4270–4273.

26.

Zhen

, Xin-Li

and Jun-Niu

, Matrix decomposition algorithm for calculating reliability of multistate network based on minimal cuts, Systems Engineering Theory & Practice32(9) (2012), 1986–1995.

27.

Yeh

W.-C.

, A simple algorithm to search for all MCs in networks, European Journal of Operational Research174 (2006), 1694–1705.

28.

Yifeng

, Yanhong

and Xiuzhen

, New decomposition algorithm for computing two-terminal network reliability, Computer Engineering and Applications47(30) (2011), 79–82.

29.

Lei

, Yufeng

and Yuqing

H.U.

, Factorization realizing approxim ate estim ation of 2-term inal networks reliability, Computer Engineering and Applications48(12) (2012), 53–57.

30.

Hansen

, Jaumard

, Best

G.-B.

, et al., second order bounds for two-terminal network reliability with dependent edge failures, Discrete Applied Mathematics96–97 (1999), 375–393.

31.

Brown

J.I.

, Colbourn

C.J.

and Richard

, Nowakowski, Chip firing and all-terminal network reliability bounds, Discrete Optimization6 (2009), 436–445.

32.

, Ai-Qun

and He

, Evaluation method for the network reliability based on the entropy measures, IEEE Trans Inform Theory10(12) (2009), 423–426.

33.

Yan

, Xin-Feng

and Guo-Hua

, Application of factoring theorem in analysis of CIMS network reliability, Computer Integrated Manufacturing Systems11(12) (2005), 1621–1625.

34.

Yeh

, An improved sum-of-disjoint-products technique for the symbolic network reliability analysis with known minimal paths, Reliability Engineering and System Safety92(2) (2007), 260–268.

35.

Yeh

and Lin

, A particle swarm optimization approach based on monte carlo simulation for solving the complex network reliability problem, IEEE Trans Reliability59(1) (2010), 212–221.

36.

Hardy

, Lucet

and Limnios

, K-terminal network reliability measures with binary decision diagrams, IEEE Trans Reliability56(3) (2007), 506–515.

37.

Sharafat

A.R.

, All-terminal network reliability using recursive truncation algorithm, IEEE Trans Reliability58(2) (2009), 338–347.

38.

Adbullah

, Combining Network Reductions and Simulation to Estimate Network Reliability[C], Proceedings of the 2007 Winter Simulation Conference, Washington D.C., USA, Association for Computing Machinery, 2007, pp. 2301–2305.

39.

Manzi

, Labbe

, et al., Fishman’s sampling plan for computing network reliability, IEEE Trans Reliability50(1) (2001), 41–46.