Sage Journals: Discover world-class research

Abstract

The construction spectrum is a useful tool to investigate the network reliability, which only depends on network structure and is called structure invariant. Importance measures are efficient tools to quantify and rank the impact of edges within a network. This study considers the K-terminal network with n edges and assumes that edges fail with an equal probability. The article focuses on investigating the importance measures of individual edge for the K-terminal network, including reliability achievement worth and reliability reduction worth, via the construction spectrum–based method. Generally, we establish the equations for reliability achievement worth and reliability reduction worth using the construction spectrum and determine the conditions under which the importance rankings generated by reliability achievement worth and reliability reduction worth only depend on the network structure through the construction spectrum. Similar results are obtained with reliability achievement worth and reliability reduction worth for pair of edges. A construction spectrum–based Monte-Carlo simulation is used to estimate reliability achievement worth and reliability reduction worth. Finally, a numerical example is presented to illustrate the application of these measures.

Keywords

Construction spectrum importance measure reliability achievement worth reliability reduction worth network reliability

Introduction

Networks play an important role in our daily activities. Consequently, their reliability and sensitivity analysis attracted much attention from different researchers. The network is composed of a collection of nodes and edges, in which some special nodes are named terminals. In practical engineering, the nodes denote road intersections, control centers, and communication/computer centers, while the edges denote the power lines, communications and supply channels, and road segments.

In the network of communication or transportation system, we are more concerned about the edge failure. For example, in a road network, the roads are denoted by the network edges and they may fail due to an earthquake. Thus, this article assumes that all the nodes are absolutely reliable, while all the edges are subjected to failure with identical probability. An edge failure implies that the edge is eliminated from the network. This fact may result in the down state for the network. The network is in down state if and only if there exists at least a pair of terminals such that they are disconnected. Conversely, the network is up if and only if any pair of terminals is connected by the edges in the working state. The network reliability is defined as the probability that the network is in the up state.^1,2

The network reliability analysis can discriminate the bottleneck in a network and quantify the effect of the edge failure on the network failure. To this aim, the concept of importance measure (IM) is proposed and applied. The IMs produce numerical indexes to determine which edges are more critical for network failure or more important with respect to network reliability improvement. Many different IMs are proposed and investigated by researchers, including Birnbaum IM,^3–5 Fussell–Vesely (FV) IM,^6–8 Bayesian IM,^9,10 reliability achievement worth (RAW),¹¹ and reliability reduction worth (RRW).¹² Furthermore, Page and Perry¹³ exploited the reliability polynomial to quantify the importance of individual edge based on its impact on network reliability. Hong and Lie¹⁴ established the joint IM of two edges, which considered the interaction of two edges in a network. As a result, the network edges can be ranked depending on their impact on network reliability according to a given IM.

From the definition of the above-mentioned IMs, the calculation of these measures relies on the reliability of network and sub-network. The network reliability evaluation has received considerable attention from many researchers. There are three elementary approaches to evaluate the network reliability. The first approach is to enumerate all the minimal paths (cuts) for the network, and then a probability computing is applied according to inclusion–exclusion method.^15–18 The second approach evaluates the network reliability using the factoring algorithm.^19–21 This algorithm chooses an edge of the network and decomposes the network into two sub-networks. For one, we assume that the edge is down, while for the other, we assume that the edge is up. Thus, the reliability evaluation of the original network boils down to the reliability evaluation of the two sub-networks. The third approach uses the binary decision diagrams (BDDs) to determine the network reliability.^22–25 The BDD structure gives a directed acyclic network based on Shannon’s decomposition and provides compact expressions of the Boolean expressions.

However, for general network structure, the evaluations of network reliability and IMs are NP-hard.^26,27 Therefore, there exists a significant distance between the theoretical analysis and the ability to compute them for moderate or large network. Thus, Monte-Carlo (MC) approaches are extensively applied to estimate the reliability and IMs for the K-terminal network.^28,29 Gertsbakh and Shpungin^30,31 and Vaisman et al.³² designed the MC method based on destruction spectrum (D-spectrum) to estimate the Birnbaum IM, FV IM, and joint IM for K-terminal network when the edges have common reliabilities.

The spectrum is usually classified into D-spectrum and construction spectrum (C-spectrum), which all depend only on the network structure and hence are called structure invariants.³² The D-spectrum is defined from the network destruction standpoint and is closely related to network cut. The C-spectrum is derived from the network construction standpoint and is closely related to network path. When considering the IM of K-terminal network, previous works have focused on using the method of the D-spectrum. However, for some K-terminal networks (e.g. a two-terminal network which is a parallel connection of some small networks), in contrast to D-spectrum, the C-spectrum is more easily obtained. Thus, an alternative method based on the C-spectrum should be adopted to investigate the IMs for K-terminal network. The contributions of this work include two aspects: (1) extend the traditional RRW and RAW to K-terminal network context and (2) provide a C-spectrum-based method to evaluate the RAW and RRW. Note that the RAW and RRW can be applied to evaluate the importance of pairs of edges.^33–35 Thus, the RAW and RRW of a pair of edges for K-terminal network are also investigated via the C-spectrum-based method in this article.

This article is structured as follows. Section “Basic notions and definitions” gives the basic definitions and notations, as well as some relationships between the C-spectrum and path. Section “Spectrum representation for network IMs” derives equations for RAW and RRW of individual edge via the C-spectrum and establishes some properties concerning the rankings under these measures. Moreover, a similar method is presented for RAW and RRW with a pair of edges. In section “Algorithm and example,” an algorithm and a numerical example are given to demonstrate the application of these measures. Finally, section “Conclusion” gives the conclusion. All proofs are given in Appendix 1.

Basic notions and definitions

Based on different network performance and reliability definitions, many types of networks have been investigated. This article considers the K-terminal network, which is an undirected graph, N(V, E, K), where V is the node set, E is the edge set, | E | = n, and K is the set of special nodes (which are called terminals, K ⊆ V). We consider binary network consisting of binary edges and assume that all the nodes are absolutely reliable, while all the edges are subjected to failure with identical failure probability. When an edge fails, it is in the down state and can be erased from the network. Otherwise, it is in the up state. The binary variable x_i = 1(0) denotes that the edge i is in up (down) state. The probability p_i is the reliability of edge i, that is, p_i = P(x_i = 1). The structure function $ϕ (x)$ determines the state of the network, where x = (x₁, x₂, …, x_n). The $ϕ (x) = 1 (0)$ denotes the up (down) state of the network. The network is up if and only if all the terminals are connected to each other by a path consisting of operational edges. The path is a set of operational edges which connects all terminals in K. The cut is a set of edges whose failures result in the down state for the network, that is, at least two terminals are disconnected in K. The reliability of the network is defined as the probability that the network is in the up state, that is, R = P(ϕ(x) = 1) = R(p₁, p₂, …, p_n).

This article investigates the K-terminal network and assumes that the edge failures are mutually independent with identical failure probability. For this simplified setting, the network reliability and IMs can be estimated through the combinatorial spectrum method. In the following sections, we will investigate the network IM based on the C-spectrum. Therefore, we focus on stating the definition of C-spectrum as follows.

Let π = (i₁, i₂, …, i_n) be a random permutation of edge number and assume that all edges are down in the beginning. Then, moving along π from left to right, we turn up the edge one by one. Let f_x denote the probability that the network is up by turning up the edge i_x (i.e. on the xth step for this construction process). The discrete probability vector f = (f₁, f₂, …, f_n) is called the C-spectrum. Let Y be the number of edges needed to be turned from down to up causing the network to be in the up state. Then, f_x = P(Y = x), and the cumulative C-spectrum is defined as F(x) = f₁ + f₂ +⋯+ f_x = P(Y ≤ x), where x = 1, 2, …, n. It was shown as³²

$B (x) = (\begin{matrix} n \\ x \end{matrix}) F (x)$ (1)

where B(x) is the number of paths of size x. Thus, F(x) can be interpreted as the probability that the network is up if exactly x randomly chosen edges are up.

To investigate the importance for individual edge i, B(x) can be split into two parts, as

$B (x) = B (x, 1_{i}) + B (x, 0_{i})$ (2)

where B(x, 1_i) is the number of paths that (1) exactly has x up edges and (2) edge i is among the up edges; B(x, 0_i) is the number of paths that (1) exactly has x up edges and (2) edge i is not among the up edges.

According to equations (1) and (2), F(x) can also be split into two parts, as

$F (x) = F (x, 1_{i}) + F (x, 0_{i})$ (3)

where

$F (x, 1_{i}) = B (x, 1_{i}) {(\begin{matrix} n \\ x \end{matrix})}^{- 1}$ (4)

and

$F (x, 0_{i}) = B (x, 0_{i}) {(\begin{matrix} n \\ x \end{matrix})}^{- 1}$ (5)

Hence, F(x, 1_i) can be explained as the probability that the network is up and edge i is up if x randomly chosen edges are up, while F(x, 0_i) is the probability that the network is up and edge i is down if x randomly chosen edges are up.

The individual edge IM does not tell the information about how the edges affect each other. To quantify the interaction between edges, the concept of IMs for a pair of edges has been introduced. According to the definitions of RRW and RAW, we introduce B(x, 1_i, 1_j) and B(x, 0_i, 0_j) for the pair of edges (i, j) as follows.

B(x, 1_i, 1_j) is the number of paths that (1) has exactly x up edges and (2) edges i and j are among the up edges. B(x, 0_i, 0_j) is the number of paths that (1) has exactly x up edges and (2) edges i and j are not among the up edges.

Similar to equations (4) and (5), let

$F (x, 1_{i}, 1_{j}) = B (x, 1_{i}, 1_{j}) {(\begin{matrix} n \\ x \end{matrix})}^{- 1}$ (6)

and

$F (x, 0_{i}, 0_{j}) = B (x, 0_{i}, 0_{j}) {(\begin{matrix} n \\ x \end{matrix})}^{- 1}$ (7)

Hence, F(x, 1_i, 1_j) can be explained as the probability that the network is up and the pair (i, j) is up if x randomly chosen edges are up from n edges. F(x, 0_i, 0_j) is the probability that the network is up and the pair (i, j) is down if x randomly chosen edges are up from n edges.

The following example illustrates the definitions of F(x), F(x, 1_i), F(x, 0_i), F(x, 1_i, 1_j), and F(x, 0_i, 0_j).

Example 1

Considering the network in Figure 1, the paths of size 3 are {1, 2, 3}, {1, 2, 4}, and {2, 3, 4}. Among these paths, the paths including edge 3 are {1, 2, 3} and {2, 3, 4}; the path including the edge pair (3, 4) is {2, 3, 4}. Thus, B(3) = 3, B(3, 1₃) = 2, B(3, 1₃, 1₄) = 1, and B(3, 0₃) = B(3) − B(3, 1₃) = 1. Hence, F(3) = 3/4, F(3, 1₃) = 2/4, F(3, 0₃) = 1/4, and F(3, 1₃, 1₄) = 1/4. Similarly, all the associated values are evaluated and presented in Tables 1 and 2, where (1_i, 1_j) is abbreviated for F(k, 1_i, 1_j).

Table 1.

Values of F(k), F(k, 1_i), and F(k, 0_i) for example 1.

k	F(k)	F(k, 1₁)	F(k, 1₂)	F(k, 1₃)	F(k, 1₄)	F(k, 0₁)	F(k, 0₃)	F(k, 0₄)
1	0	0	0	0	0	0	0	0
2	1/6	1/6	1/6	0	0	0	1/6	1/6
3	3/4	2/4	3/4	2/4	2/4	1/4	1/4	1/4
4	1	1	1	1	1	0	0	0

Table 2.

Values of F(k, 1_i, 1_j) for example 1.

k	(1₃, 1₄)	(1₂, 1₄)	(1₁, 1₂)	(1₁, 1₃)	(1₁, 1₄)	(1₂, 1₃)
1	0	0	0	0	0	0
2	0	0	1/6	0	0	0
3	1/4	2/4	2/4	1/4	1/4	2/4
4	1	1	1	1	1	1

Figure 1.

Example of network with four edges and two terminals {s, t}.

Finally, based on Figure 1, one sees that

$B (k, 0_{i}, 0_{j}) = {\begin{matrix} 1 & k = 2, i = 3, j = 4 \\ 0 & otherwise \end{matrix}$ (8)

Hence, we can write

$F (k, 0_{i}, 0_{j}) = {\begin{matrix} 1 / 6 & k = 2, i = 3, j = 4 \\ 0 & otherwise \end{matrix}$ (9)

Spectrum representation for network IMs

Suppose that all these edges in a network have independent and identically distributed reliability p (i.e. all the edges have identical failure probability q = 1 − p). This section establishes equations for network IM via the C-spectrum, including RAW and RRW for an individual edge and a pair of edges.

Spectrum representation for RAW and RRW of an individual edge

From the definition of B(k) and the law of total probability, we have

$P (ϕ = 1) = \sum_{k = 1}^{n} B (k) p^{k} q^{n - k}$ (10)

Similarly, based on the definitions B(k, 1_i) and B(k, 0_i), we can write

$P (ϕ = 1 | x_{i} = 1) = \sum_{k = 0}^{n - 1} B (k + 1, 1_{i}) p^{k} q^{n - k - 1}$ (11)

and

$P (ϕ = 1 | x_{i} = 0) = \sum_{k = 1}^{n - 1} B (k, 0_{i}) p^{k} q^{n - k - 1}$ (12)

In equation (11), since the state of a particular edge i is known in the up state, the summation for k is from 0 to n − 1. Then B(k, 1_i) should be substituted with B(k + 1, 1_i). Similarly, the summation for k is from 1 to n − 1 in equation (12) since the state of a particular edge i is known in the down state.

The RAW evaluates the percentage increase in system reliability generated by a given component. Mathematically, it can be written as

$RAW (i) = \frac{P (ϕ = 1 | x_{i} = 1)}{P (ϕ = 1)}$ (13)

In the context of K-terminal network reliability, from equations (10) and (11), we have

$RAW (i) = \frac{\sum_{k = 0}^{n - 1} B (k + 1, 1_{i}) p^{k} q^{n - k - 1}}{\sum_{k = 1}^{n} B (k) p^{k} q^{n - k}}$ (14)

Finally, based on equations (1) and (4), the spectrum representation for RAW(i) is obtained as

$RAW (i) = \frac{\sum_{k = 0}^{n - 1} (\begin{matrix} n \\ k + 1 \end{matrix}) F (k + 1, 1_{i}) p^{k} q^{n - k - 1}}{\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) F (k) p^{k} q^{n - k}}$ (15)

Comparing equation (15) for different edges i and j, we can establish the following proposition.

Proposition 1

Consider a network that has n edges. For two fixed edges i and j and the corresponding {F(k, 1_i), 1 ≤ k ≤ n} and {F(k, 1_j), 1 ≤ k ≤ n}, the following assertions hold:

If F(k, 1_i) ≥ F(k, 1_j) for all 1 ≤ k ≤ n, then RAW(i) ≥ RAW(j) for all 0 < p < 1.

Let m = max{k:F(k, 1_i) ≠ F(k, 1_j)}. Suppose F(m, 1_i) > F(m, 1_j). Then, there exists p₀ satisfying RAW(i) > RAW(j) for all p > p₀.

The Proposition 1 is illustrated by the following example.

Example 2

Let us compare the RAW of edges 1 and 2 in the network depicted in Figure 1. According to Table 1, we obtain m = max{k:F(k, 1₁) ≠ F(k, 1₂)} = 3 and F(3, 1₂) = 3/4 > F(3, 1₁) = 1/2. Thus, the result of RAW(2) > RAW(1) for sufficiently large p follows part 2 of Proposition 1. In fact, F(k, 1₂) ≥ F(k, 1₁) ≥ F(k, 1₃) ≥ F(k, 1₄) for all 1 ≤ k ≤ 4 in Table 1. Thus, by part 1 of Proposition 1, RAW(2) ≥ RAW(1) ≥RAW(3) ≥ RAW(4) for all the 0 < p < 1.

The RRW quantifies the potential damage caused to the system by a given component. Mathematically, it can be written as

$RRW (i) = \frac{P (ϕ = 1)}{P (ϕ = 1 | x_{i} = 1)}$ (16)

In the context of K-terminal network reliability, applying equations (10) and (12) to equation (16), we have

$RRW (i) = \frac{\sum_{k = 1}^{n} B (k) p^{k} q^{n - k}}{\sum_{k = 1}^{n - 1} B (k, 0_{i}) p^{k} q^{n - k - 1}}$ (17)

Finally, substituting equations (1) and (5) into equation (17), the spectrum representation for RRW(i) is derived as

$RRW (i) = \frac{\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) F (k) p^{k} q^{n - k}}{\sum_{k = 1}^{n - 1} (\begin{matrix} n \\ k \end{matrix}) F (k, 0_{i}) p^{k} q^{n - k - 1}}$ (18)

Based on equation (18), we can derive the following proposition.

Proposition 2

Consider a network with n edges. For two fixed edges i and j and the corresponding {F(k, 0_i), 1 ≤ k ≤ n − 1} and {F(k, 0_j), 1 ≤ k ≤ n − 1}, the following assertions hold:

If F(k, 0_j) ≥ F(k, 0_i) for all 1 ≤ k ≤ n − 1, then RRW(i) ≥ RRW(j) for all 0 < p < 1.

Let m = max{k:F(k, 0_i) ≠ F(k, 0_j)}. If F(m, 0_j) > F(m, 0_i), then there exists p₀ satisfying RRW(i) > RRW(j) for all p > p₀.

The following example demonstrates the application of Proposition 2.

Example 3

Consider the network depicted in Figure 1. Let us compare RRW of edges 1 and 3. According to Table 1, we have m = max{k:F(k, 0₁) ≠ F(k, 0₃)} = 2 and F(2, 0₃) = 1/6 > F(2, 0₁) = 0. Thus, the result of RRW(1) > RRW(3) for sufficiently large p follows part 2 of Proposition 2. In addition, we have F(k, 0₂) ≤ F(k, 0₁) ≤ F(k, 0₃) ≤ F(k, 0₄) for all 1 ≤ k ≤ 4 in Table 1. Thus, by part 1 of Proposition 2, RRW(2) ≥ RRW(1) ≥ RRW(3) ≥ RRW(4) for all 0 < p < 1.

Remark 1

Note that F(k, 1_i) = F(k) − F(k, 0_i) and F(k, 1_j) = F(k) − F(k, 0_j). Thus, F(k, 1_i) ≥ F(k, 1_j) for all k if and only if F(k, 0_i) ≤ F(k, 0_j) for all k. This is to say that the conditions of part 1 of Propositions 1 and 2 are equivalent. Hence, when one of the two conditions holds, the rankings generated by RAW and RRW are consistent for all ps.

Spectrum representation for RAW and RRW with pair of edges

The RAW(i, j) evaluates the importance for the pair of components i and j on the basis of their potential to improve the system reliability generated by the pair of components (i, j) as

$RAW (i, j) = \frac{P (ϕ = 1 | x_{i} = x_{j} = 1)}{P (ϕ = 1)}$ (19)

where P(ϕ = 1│x_i = x_j = 1) is the system reliability given that components i and j are up.

By the definition of B(k, 1_i, 1_j) and the law of total probability, for K-terminal network, we can write

$P (ϕ = 1 | x_{i} = x_{j} = 1) = \sum_{k = 0}^{n - 2} B (k + 2, 1_{i}, 1_{j}) p^{k} q^{n - k - 2}$ (20)

In equation (20), note that the state of the pair of edges (i, j) is known and they are up. Hence, the summation for k is from 0 to n − 2 and B(k + 2, 1_i, 1_j) will substitute for B(k, 1_i, 1_j). Moreover, in the context of K-terminal network reliability, by substituting equations (20) and (10) into equation (19), we can write

$RAW (i, j) = \frac{\sum_{k = 0}^{n - 2} B (k + 2, 1_{i}, 1_{j}) p^{k} q^{n - k - 2}}{\sum_{k = 1}^{n} B (k) p^{k} q^{n - k}}$ (21)

Finally, combining equations (6) and (1), the following equation is derived

$RAW (i, j) = \frac{\sum_{k = 0}^{n - 2} (\begin{matrix} n \\ k + 2 \end{matrix}) F (k + 2, 1_{i}, 1_{j}) p^{k} q^{n - k - 2}}{\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) F (k) p^{k} q^{n - k}}$ (22)

Considering equation (22), we have the following proposition.

Proposition 3

Consider a network with n edges. For the two pairs of edges (i, j), (h, s), and the corresponding {F(k, 1_i, 1_j), 2 ≤ k ≤ n} and {F(k, 1_h, 1_s), 2 ≤ k ≤ n}, the following assertions hold:

If F(k, 1_i, 1_j) ≥ F(k, 1_h, 1_s) for all 2 ≤ k ≤ n, then RAW(i, j) ≥ RAW(h, s) for all 0 < p < 1.

Let m = max{k:F(k, 1_i, 1_j) ≠ F(k, 1_h, 1_s)}. If F(m, 1_i, 1_j) > F(m, 1_h, 1_s), then there exists p₀ satisfying RAW(i, j) ≥ RAW(h, s) for all p > p₀.

Next, we will illustrate Proposition 3 with the following example.

Example 4

Considering the network depicted in Figure 1, let us calculate the RAW rankings applied to the pairs of edges. According to Table 2, one can see F(k, 1₁, 1₂) ≥ F(k, 1₂, 1₄) = F(k, 1₂, 1₃) ≥ F(k, 1₃, 1₄) ≥ F(k, 1₁, 1₃) ≥ F(k, 1₁, 1₄) for all 1 ≤ k ≤ 4. Thus, by part 1 of Proposition 3, RAW(1, 2) ≥ RAW(2, 4) ≥ RAW(2, 3) ≥ RAW(3, 4) = RAW(1, 3) = RAW(1, 4) for all 0 < p < 1.

RRW(i, j) evaluates the importance of the pair of components (i, j) in the light of their potential to reduce the system reliability caused by the pair of components (i, j). Mathematically, we have

$RRW (i, j) = \frac{P (ϕ = 1)}{P (ϕ = 1 | x_{i} = x_{j} = 0)}$ (23)

where P(φ = 1│x_i =x_j = 0) is the system reliability given that components i and j are down.

By the definition of B(k, 0_i, 0_j) and the law of total probability, for K-terminal network, we can write

$P (ϕ = 1 | x_{i} = x_{j} = 0) = \sum_{k = 1}^{n - 2} B (k, 0_{i}, 0_{j}) p^{k} q^{n - k - 2}$ (24)

In equation (24), since the state of the pair of edges (i, j) is known and they are down, the summation for k is from 1 to n − 2. Moreover, by substituting equations (10) and (24) into equation (23), under the context of K-terminal network reliability, we can get

$RRW (i, j) = = \frac{\sum_{k = 1}^{n} B (k) p^{k} q^{n - k}}{\sum_{k = 1}^{n - 2} B (k, 0_{i}, 0_{j}) p^{k} q^{n - k - 2}}$ (25)

Finally, applying equations (7) and (1) to equation (25), the following equation is derived

$RRW (i, j) = \frac{\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) F (k) p^{k} q^{n - k}}{\sum_{k = 1}^{n - 2} (\begin{matrix} n \\ k \end{matrix}) F (k, 0_{i}, 0_{j}) p^{k} q^{n - k - 2}}$ (26)

To compare the importance of the pair edges based on RAW(i, j), the following proposition is established.

Proposition 4

Consider a network with n edges. For the two pairs of edges (i, j), (h, s), and the corresponding values {F(k, 0_i, 0_j), 2 ≤ k ≤ n} and {F(k, 0_h, 0_s), 2 ≤ k ≤ n}, the following assertions hold:

If F(k, 0_h, 0_s) ≥ F(k, 0_i, 0_j) for all 2 ≤ k ≤ n, then RRW(i, j) ≥ RRW(h, s) for all 0 < p < 1.

Let m = max{k:F(k, 0_h, 0_s) ≠ F(k, 0_i, 0_j)}. If F(m, 0_h, 0_s) > F(m, 0_i, 0_j), then there exists p₀ satisfying RRW(i, j) ≥ RRW(h, s) for all p > p₀.

Proposition 4 is illustrated by the following example.

Example 5

Consider the network depicted in Figure 1. Let us consider the RRW rankings applied to the pairs of edges. According to Table 2, one can see F(k, 0₃, 0₄) ≥ F(k, 0₁, 0₂) = F(k, 0₂, 0₄) = F(k, 0₂, 0₃) = F(k, 0₁, 0₃) = F(k, 0₁, 0₄) for all 1 ≤ k ≤ 4 and strict inequality holds for k = 2. Thus, by part 1 of Proposition 4, RRW(1, 2) = RRW(2, 4) = RRW(2, 3) = RRW(1, 3) = RRW(1, 4) > RRW(3, 4) for all 0 < p < 1. Since {1, 2}, {2, 4}, {2, 3}, {1, 3}, and {1, 4} are cuts of size 2, RRW(1, 2) = RRW(2, 4) = RRW(2, 3) = RRW(1, 3) = RRW(1, 4) = ∞.

Remark 2

In the above four propositions, the conditions of part 1 imply that the rankings provided by these measures do not depend on edge reliability p. However, except for the networks with good structure, these conditions do not always hold (e.g. for some k, F(k, 0_h, 0_s) ≥ F(k, 0_i, 0_j); but F(k, 0_h, 0_s) ≤ F(k, 0_i, 0_j) for other k). Therefore, in general, these rankings depend on not only the network structure but also the edge reliability p. This fact will be illustrated in the numerical example in the next section. Furthermore, the conditions of part 2 in these propositions always hold and imply that these rankings are structural rankings when p is sufficiently large. (i.e. these rankings depend only on the network structure through the C-spectrum when p is large enough).

From the practical standpoint, the edge reliability is not easy to obtain if the sample size or testing time is limited. In real life, the edge reliability is usually regarded as high. But in the phase of network design, using the highly reliable edge may not produce a high level of network reliability. Thus, redundancy is commonly used in network design to enhance network reliability. Incorporating redundancy will result in the network with complex structure function. Propositions 1–4 can be applied to compare the edges of such network with complex structure and largely reliable edge. According to Propositions 1–4, there is no need to compute the RRW and RAW to compare the importance of the edges. We only need to compare theC-spectra of the corresponding edges. Thus, this fact contributes to the reduction of computing time.

Algorithm and example

This section gives an algorithm and an example to explain how we can rank the individual edge (the pair of edges) based on the RAW and RRW. These measures have been estimated with the MC approach based on C-spectrum.

Algorithm

Vaisman et al.³² have designed an MC algorithm for estimating the network C-spectrum as follows. Considering a network that has n edges, we first simulate M random edge permutations π = (i₁, i₂, …, i_n) for approximating F(x). Then, moving along an edge permutation from left to right, a sequential edge construction process is imitated. One counts the number N_j of edge permutations for which the network went into up state at the jth step of the construction process. Finally, we take $\hat{F} (x) = (N_{1} + N_{2} + \dots + N_{x}) / M$ as the estimation of F(x).

To estimate F(x, 1_j), one can revise the procedure which is described above. Specifically, the summation (N₁ + N₂ + ⋯ + N_x)/M = M(x) is divided into two terms as M(x, 1_j) + M(x, 0_j). The first term M(x, 1_j) is the number of edge permutations such that the network went to up state when the first x edges including edge j are up, while the second term M(x, 0_j) does not include edge j. We can write $\hat{F} (x, 1_{j}) = M (x, 1_{j}) / M$ and $\hat{F} (x, 0_{j}) = M (x, 0_{j}) / M$ as the estimation of F(x, 1_j) and F(x, 0_j) respectively.

Similarly, one counts the number of edge permutations (M(x, 1_i, 1_j) (M(x, 0_i, 0_j)) such that the network went to up state when the first x edges including (not) edges i and j are up. Thus, M(x, 1_i, 1_j)/M and M(x, 0_i, 0_j)/M are used to estimate F(x, 1_i, 1_j) and F(x, 0_i, 0_j)) respectively.

Examples

Consider the hypercube network H₃ depicted in Figure 2. All the edges are subjected to failure and independent with common reliability p. All the nodes are absolutely reliable and nodes 1, 3, and 6 are terminals. The network is in the up state if all the terminals are connected to each other. In computer networks, the hypercube network configurations have wide application.³⁶

Figure 2.

H ₃ network with terminals {1, 3, 6}.

Tables 3 and 4 present the estimations of F(k, 1_i) and F(k, 0_i) respectively. The rankings for the pairs of edges (2, j) (j = 1, 3, 4, …, 12) are presented in Tables 5 and 6 according to the RAW and RRW for various ps, respectively. The values of RAW and RRW are evaluated by equations (22) and (26), respectively. Moreover, F(k, 1_i), F(k, 0_i), F(k, 1_i, 1_j), and F(k, 0_i, 0_j) are estimated by the MC algorithm³² with M = 10,000.

Table 3.

Estimation of F(k, 1_i) for all the edges in the H₃ network.

k	F(k, 1₁)	F(k, 1₂)	F(k, 1₃)	F(k, 1₄)	F(k, 1₅)	F(k, 1₆)	F(k, 1₇)	F(k, 1₈)	F(k, 1₉)	F(k, 1₁₀)	F(k, 1₁₁)	F(k, 1₁₂)
1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0
3	0.0045	0	0	0.0045	0.0045	0	0	0	0	0	0	0
4	0.0263	0.0101	0.0101	0.0263	0.0263	0.0101	0.0101	0.0020	0.0101	0.0020	0.0101	0.0020
5	0.0846	0.0581	0.0581	0.0846	0.0846	0.0581	0.0581	0.0265	0.0581	0.0265	0.0581	0.0265
6	0.2154	0.1926	0.1926	0.2154	0.2154	0.1926	0.1926	0.1396	0.1926	0.1396	0.1926	0.1396
7	0.4419	0.4318	0.4318	0.4419	0.4419	0.4318	0.4318	0.3914	0.4318	0.3902	0.4318	0.3914
8	0.6202	0.6182	0.6182	0.6202	0.6202	0.6182	0.6182	0.6000	0.6182	0.6000	0.6182	0.6000
9	0.7409	0.7409	0.7409	0.7409	0.7409	0.7409	0.7409	0.7364	0.7409	0.7364	0.7409	0.7364
10	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333	0.8333
11	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167	0.9167
12	1	1	1	1	1	1	1	1	1	1	1	1

Table 4.

Estimation of F(k, 0_i) for all the edges in the H₃ network.

k	F(k, 0₁)	F(k, 0₂)	F(k, 0₃)	F(k, 0₄)	F(k, 0₅)	F(k, 0₆)	F(k, 0₇)	F(k, 0₈)	F(k, 0₉)	F(k, 0₁₀)	F(k, 0₁₁)	F(k, 0₁₂)
1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0.0045	0.0045	0	0	0.0045	0.0045	0.0045	0.0045	0.0045	0.0045	0.0045
4	0.0101	0.0263	0.0263	0.0101	0.0101	0.0263	0.0263	0.0343	0.0263	0.0343	0.0263	0.0343
5	0.0518	0.0783	0.0783	0.0518	0.0518	0.0783	0.0783	0.1098	0.0783	0.1098	0.0783	0.1098
6	0.1548	0.1775	0.1775	0.1548	0.1548	0.1775	0.1775	0.2305	0.1775	0.2305	0.1775	0.2305
7	0.2854	0.2955	0.2955	0.2854	0.2854	0.2955	0.2955	0.3359	0.2955	0.3371	0.2955	0.3359
8	0.3010	0.3030	0.3030	0.3010	0.3010	0.3030	0.3030	0.3212	0.3030	0.3212	0.3030	0.3212
9	0.2455	0.2455	0.2455	0.2455	0.2455	0.2455	0.2455	0.2500	0.2455	0.2500	0.2455	0.2500
10	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667	0.1667
11	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833	0.0833
12	0	0	0	0	0	0	0	0	0	0	0	0

Table 5.

Rankings of the pairs (2, j) for various ps based on RAW.

Rank	p = 0.1		p = 0.4		p = 0.5		p = 0.7		p = 0.9
	RAW	(2, j)	RAW	(2, j)	RAW	(2, j)	RAW	(2, j)	RAW	(2, j)
1	23.6568	(2, 6)	3.7983	(2, 6)	3.2454	(2, 6)	3.6931	(2, 6)	10.0282	(2, 6)
2	18.6680	(2, 5)	3.5343	(2, 5)	3.1252	(2, 5)	3.6752	(2, 5)	10.0279	(2, 5)
3	14.0241	(2, 4)	3.2556	(2, 4)	2.9917	(2, 11)	3.6498	(2, 11)	10.0270	(2, 7)
4	13.9357	(2, 1)	3.2415	(2, 11)	2.9783	(2, 4)	3.6491	(2, 7)	10.0270	(2, 9)
5	10.7401	(2, 11)	3.2086	(2, 7)	2.9783	(2, 7)	3.6491	(2, 9)	10.0269	(2, 11)
6	10.3702	(2, 7)	3.2086	(2, 9)	2.9783	(2, 9)	3.6393	(2, 4)	10.0261	(2, 4)
7	10.3702	(2, 9)	3.1767	(2, 1)	2.9115	(2, 1)	3.5994	(2, 1)	10.0182	(2, 1)
8	9.7451	(2, 3)	2.9862	(2, 3)	2.8180	(2, 3)	3.5790	(2, 3)	10.0173	(2, 3)
9	4.9357	(2, 8)	2.7585	(2, 8)	2.7112	(2, 8)	3.5653	(2, 12)	10.0171	(2, 12)
10	4.5454	(2, 12)	2.7380	(2, 12)	2.7112	(2, 12)	3.5582	(2, 8)	10.0164	(2, 8)
11	4.0088	(2, 10)	2.5945	(2, 10)	2.6177	(2, 10)	3.5351	(2, 10)	10.0154	(2, 10)

Table 6.

Rankings of the pairs (2, j) for various ps based on RRW.

Rank	p = 0.1		p = 0.4		p = 0.5		p = 0.7		p = 0.9
	RRW	(2, j)	RRW	(2, j)	RRW	(2, j)	RRW	(2, j)	RRW	(2, j)
1	7.3978	(2, 1)	1.9121	(2, 1)	1.2763	(2, 1)	0.4919	(2, 1)	0.1128	(2, 1)
2	7.3386	(2, 4)	1.7920	(2, 4)	1.1760	(2, 4)	0.4696	(2, 3)	0.1126	(2, 3)
3	5.1653	(2, 5)	1.4665	(2, 5)	1.0448	(2, 3)	0.4444	(2, 4)	0.1052	(2, 4)
4	1.4421	(2, 3)	1.3474	(2, 3)	1.0028	(2, 5)	0.4089	(2, 5)	0.1036	(2, 5)
5	1.4255	(2, 7)	1.1837	(2, 7)	0.8914	(2, 7)	0.3976	(2, 7)	0.1035	(2, 11)
6	1.4255	(2, 9)	1.1837	(2, 9)	0.8914	(2, 9)	0.3976	(2, 9)	0.1035	(2, 7)
7	1.4170	(2, 11)	1.1687	(2, 11)	0.8844	(2, 11)	0.3976	(2, 11)	0.1035	(2, 9)
8	1.1713	(2, 10)	0.9707	(2, 10)	0.7746	(2, 10)	0.3809	(2, 10)	0.1033	(2, 10)
9	1.1623	(2, 12)	0.9141	(2, 12)	0.7223	(2, 6)	0.3635	(2, 6)	0.1024	(2, 6)
10	1.1558	(2, 6)	0.9065	(2, 6)	0.7223	(2, 8)	0.3635	(2, 8)	0.1024	(2, 8)
11	1.1558	(2, 8)	0.9065	(2, 8)	0.7223	(2, 12)	0.3585	(2, 12)	0.1017	(2, 12)

Note that for RAW (RRW) rankings, it is only needed to compare the C-spectra of the corresponding edges according to propositions 1–2. We can observe from Table 3 that, F(k, 1₁) = F(k, 1₄) = F(k, 1₅) ≥ F(k, 1₂) = F(k, 1₃) = F(k, 1₆) = F(k, 1₇) = F(k, 1₉) = F(k, 1₁₁) ≥ F(k, 1₈) = F(k, 1₁₀) = F(k, 1₁₂). Thus, we arrive at RAW(1)=RAW(4)=RAW(5)≥RAW(2)=RAW(3) =RAW(6) = RAW(7)=RAW(9)=RAW(11)≥RAW (8)≥ RAW(10) = RAW(12) for all ps. Similarly, from Table 4 and Proposition 2, we can find that the rankings produced by RRW and RAW are consistent. This consistency is associated with the equivalent of the conditions of part 1 of Propositions 1 and 2, as discussed in Remark 1.

However, by comparing Tables 5 and 6, the rankings generated by RAW and RRW for the pairs of edges are not consistent. For example, the edge pair (2, 6) is the most important according to the RAW for all ps. However, based on the RRW, the edge pair (2, 1) is the most important for all ps. This fact is related to the different importance of perspectives. The greatest improvement to the network reliability is given by the pair (2, 6) for all various ps, which is measured by RAW. However, the greatest damage to the network reliability is caused by the pair (2, 1) for all ps, which is measured by RRW.

According to Table 5, the edge pair (2, 6) is the most important pair of edges regardless of the edge reliability p based on the RAW. However, in general, the rankings generated by RAW depend on the network structure and edge reliability p. For example, according to the RAW, the pair (2, 4) is more important than the pair (2, 7) for small p (p = 0.1), whereas for large p (p = 0.9), the pair (2, 7) is more important than the pair (2, 4). Similar results can be found based on the RRW for the pairs of edges in Table 6.

From Tables 3 and 5, based on the RAW, it is interesting to note that edge 1 is more important than edge 6 for all ps, whereas the pair (2, 6) is more important than the pair (2, 1) for all ps. This result illustrates that the measure RAW(i, j) is not directly related to the measures at the individual edge level of RAW(i) and RAW(j). Similar observation can be made for the measure RRW(i, j), which also cannot be directly related to the individual edge level of RRW(i) and RRW(j) by comparing Tables 4 and 6.

Conclusion

This article considers binary K-terminal network consisting of binary edges. Under the assumption that all the edges in the K-terminal network have identical failure probability, we develop equations expressing RAW and RRW for individual edges based on the C-spectrum. When the network has special structure or the edge reliability is high enough, it is shown that the rankings provided by these measures only depend on network structure through the C-spectrum, regardless of the failure probability of edges. Similar results are obtained for RAW and RRW with a pair of edges. An MC simulation based on the C-spectrum is applied for computing the RAW and RRW. Experimental results show that the RAW and RRW can effectively quantify the impact of edges with respect to K-terminal network reliability. Our results provide more information for understanding the K-terminal network and can serve as a basis for optimal design of K-terminal network.

Footnotes

Handling Editor: Zhaojun Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This research was financially supported by the National Natural Science Foundation of China (nos 71471147 and 71871181),the Basic Research Project of Natural Science in Shaanxi Province (no. 2018JM7009),the 111 Project (no. B13044),and the Top International University Visiting Program for Outstanding Young Scholars of Northwestern Polytechnical University.

ORCID iDs

Zhenggeng Ye

Zhiqiang Cai

References

Gertsbakh

Shpungin

Models of network reliability: analysis, combinatorics, and Monte Carlo. Boca Raton, FL: CRC Press, 2009.

Kroese

Taimre

Botev

ZI.

Handbook of Monte Carlo methods. Hoboken, NJ: John Wiley & Sons, 2013.

Zhu

Yuan

et al . Birnbaum importance based heuristics for multi-type component assignment problems. Reliab Eng Syst Safe 2017; 165: 209–221.

Shen

Cui

Birnbaum importance for linear consecutive-k-out-of-n systems with sparse d. IEEE T Reliab 2015; 64: 359–375.

Birnbaum

. On the importance of different components in a multicomponent system. In: Krishnaiah

(ed.) Multivariate analysis II. New York: Academic Press, 1969, pp.581–592.

Vesely

WE.

A time-dependent methodology for fault tree evaluation. Nucl Eng Des 1970; 13: 337–360.

Fussell

JB.

How to hand-calculate system reliability and safety characteristics. IEEE T Reliab 1975; 24: 169–174.

Meng

FC.

Comparing the importance of system components by some structural characteristics. IEEE T Reliab 1996; 45: 59–65.

Singpurwalla

ND.

Reliability and risk: a Bayesian perspective. Chichester: John Wiley & Sons, 2006.

10.

Bhattacharya

Roychowdhury

Bayesian importance measure-based approach for optimal redundancy assignment. Am J Math: S 2016; 35: 335–344.

11.

Vasseur

Llory

International survey on PSA figures of merit. Reliab Eng Syst Safe 1999; 66: 261–274.

12.

Levitin

Podofillini

Zio

Generalised importance measures for multi-state elements based on performance level restrictions. Reliab Eng Syst Safe 2003; 82: 287–298.

13.

Page

Perry

JE.

Reliability polynomials and link importance in networks. IEEE T Reliab 1994; 43: 51–58.

14.

Hong

Lie

CH.

Joint reliability-importance of two edges in an undirected network. IEEE T Reliab 1993; 42: 17–23.

15.

Colbourn

CJ.

The combinatorics of network reliability. New York: Oxford University Press, 1987.

16.

Hariri

Raghavendra

CS.

SYREL: a symbolic reliability algorithm based on path and cutset methods. IEEE T Comput 1987; C-36: 1224–1232.

17.

Locks

MO.

A minimizing algorithm for sum of disjoint products. IEEE T Reliab 1987; 36: 445–453.

18.

Ahmad

SH.

Simple enumeration of minimal cutsets of acyclic directed graph. IEEE T Reliab 1988; 37: 484–487.

19.

Satyanarayana

Chang

MK.

Network reliability and the factoring theorem. Networks 1983; 13: 107–120.

20.

Wood

RK.

A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability. Networks 1985; 15: 173–190.

21.

Page

Perry

JE.

A practical implementation of the factoring theorem for network reliability. IEEE T Reliab 1988; 37: 259–267.

22.

Yeh

Kuo

SY.

OBDD-based evaluation of k-terminal network reliability. IEEE T Reliab 2002; 51: 443–451.

23.

Imai

Serine

Imai

Computational investigations of all-terminal network reliability via BDDs. IEICE T Fund Electr 1999; 82: 714–721.

24.

Zang

Sun

Trivedi

KS.

A BDD-based algorithm for reliability graph analysis. Technical report, Department of Electrical Engineering, Duke University, Durham, NC, 2000.

25.

Hardy

Lucet

Limnios

K-terminal network reliability measures with binary decision diagrams. IEEE T Reliab 2007; 56: 506–515.

26.

Valiant

LG.

The complexity of enumeration and reliability problems. SIAM J Comput 1979; 8: 410–421.

27.

Karger

DR.

A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J Comput 1999; 29: 492–514.

28.

L’Ecuyer

Rubino

Saggadi

et al . Approximate zero-variance importance sampling for static network reliability estimation. IEEE T Reliab 2011; 60: 590–604.

29.

Botev

L’Ecuyer

Rubino

et al . Static network reliability estimation via generalized splitting. INFORMS J Comput 2013; 25: 56–71.

30.

Gertsbakh

Shpungin

Network reliability importance measures: combinatories and Monte Carlo based computations. WSEAS T Comput 2008; 7: 216–227.

31.

Gertsbakh

Shpungin

Combinatorial approach to computing component importance indexes in coherent systems. Probab Eng Inform Sc 2012; 26: 117–128.

32.

Vaisman

Kroese

Gertsbakh

IB.

Improved sampling plans for combinatorial invariants of coherent systems. IEEE T Reliab 2016; 65: 410–424.

33.

Cheok

Parry

Sherry

RR.

Use of importance measures in risk-informed regulatory applications. Reliab Eng Syst Safe 1998; 60: 213–226.

34.

Zio

Podofillini

Accounting for components interactions in the differential importance measure. Reliab Eng Syst Safe 2006; 91: 1163–1174.

35.

Kuo

Zhu

Some recent advances on importance measures in reliability. IEEE T Reliab 2012; 61: 344–360.

36.

Mitzenmacher

Upfal

Probability and computing: randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press, 2005.

k	F(k)	F(k, 1₁)	F(k, 1₂)	F(k, 1₃)	F(k, 1₄)	F(k, 0₁)	F(k, 0₃)	F(k, 0₄)
1	0	0	0	0	0	0	0	0
2	1/6	1/6	1/6	0	0	0	1/6	1/6
3	3/4	2/4	3/4	2/4	2/4	1/4	1/4	1/4
4	1	1	1	1	1	0	0	0

k	F(k)	F(k, 1₁)	F(k, 1₂)	F(k, 1₃)	F(k, 1₄)	F(k, 0₁)	F(k, 0₃)	F(k, 0₄)
1	0	0	0	0	0	0	0	0
2	1/6	1/6	1/6	0	0	0	1/6	1/6
3	3/4	2/4	3/4	2/4	2/4	1/4	1/4	1/4
4	1	1	1	1	1	0	0	0

k	F(k)	F(k, 1₁)	F(k, 1₂)	F(k, 1₃)	F(k, 1₄)	F(k, 0₁)	F(k, 0₃)	F(k, 0₄)
1	0	0	0	0	0	0	0	0
2	1/6	1/6	1/6	0	0	0	1/6	1/6
3	3/4	2/4	3/4	2/4	2/4	1/4	1/4	1/4
4	1	1	1	1	1	0	0	0