# Measuring Component Importance for Network System Using Cellular Automata

Authors: Li He; Qiyan Cao; Fengjun Shang
Journal: Complexity
 (2019)

---

## Abstract

This paper concentrates on the component importance measure of a network whose arc failure rates are not deterministic and imprecise ones. Conventionally, a computing method of component importance and a measure method of reliability stability are proposed. Three metrics are analyzed first: Birnbaum measurement, component importance, and component risk growth factor. Based on them, the latter can measure the impact of the component importance on the reliability stability of a system. Examples in some typical structures illustrate how to calculate component importance and reliability stability, including uncertain random series, parallel, parallel-series, series-parallel, and bridge systems. The comprehensive numerical experiments demonstrate that both of these methods can efficiently and accurately evaluate the impact of an arc failure on the reliability of a network system.


---

## Body

## 1. Introduction

As a quantitative measure, reliability can be broadly interpreted as the ability of a system to perform its intended function. During the past ten years, a significant amount of research has been conducted to address reliability evaluation. Network reliability can be estimated using Bayesian approach [1], Monte Carlo simulation [2, 3], genetic algorithm [4], fault-tree analysis [5], etc. Obviously, all those methods apply numerical reliability or boundary value to indicate the reliability of network systems. However, two main questions must be answered for designing a network system. Question 1: Which component is the most important? Question 2: How does the importance of component impact the system reliability stability? For answering such questions, component importance measures must show the effect and rank in system design and preventive maintenance.Determining the importance of components in complexity networks is crucial. Several importance measure methods have been introduced in [6, 7], including Birnbaum measure, criticality importance, improvement potential, risk achievement worth, and risk reduction worth. Based on the fundamental component importance theory initially proposed by Birnbaum [6], there have been a number of approaches used to show component importance. Generally speaking, the traditional component importance evaluation methods are classified into two kinds, one is on the components failure rates, and the other is without taking components characteristic into account. The first category method is mainly based on the graph theory, including reliability Boolean polynomial [7], minimum trees and their number [8], and minimal cut set. In [9], criticality importance measures for components with respect to system failure intensity and the total system failure count are presented. To evaluate reliability importance of components in a network system, Zio et al. [10] present generalized importance measures based on Monte Carlo simulation. Meanwhile, Wang et al. [11] introduce the failure critically index, restoring critical index and operational index. In [12], importance measures with respect to system failure intensity are developed and it also points out that the Barlow [11] importance only measures the contribution of a component as the last failure in a minimal cut set, not the total contribution. Contini et al. [13] also evaluate network system importance with respect to the system failure. However, an obvious shortcoming is that the impact of the component characteristic on the failure rate of network is not considered. Some examples, including the reliability of Boolean polynomial [7], minimum spanning tree [14, 15], minimum cut set and minimum path set [16], and fault-tree analysis [9], attempting to incorporate more features of network topology consisting of multiple terminals and dependency between topology are researched. Meanwhile, simulation based on Monte Carlo method [10] often depends more on the convergence of probability than the number of network components; statistical error during reliability analysis may result in slow convergence for achieving acceptable accuracy in low probability estimations. Therefore, these methods depend on the model to decompose the network topology and calculate the reliability of network. And the complexity of calculation will increase by index level as the size of network grows. Although these methods have adequately considered the characteristic of component in network system, how to improve the efficiency of calculation to strength the practical of importance measurements is still a focus.Recently, importance measure to estimate the effect of a component residing at certain states on the performance is proposed in [17]. Importance measure of components when the system may be reconfigured is designed [18]. Liu [19] presents a chance theory, which contains some basic concepts including chance measure, uncertain random variable, and chance distribution. Then, Gao and Yao [20] research the importance index of components in uncertain random systems; a concept of importance index on a component in uncertain random variable and Boolean system is proposed. At the same time, link component importance is analyzed in [21]. Component maintenance priority is used to select component for preventive maintenance. And a Monte Carlo-based method to generate probability distributions of the two metrics for all of the components of the network is proposed and a stochastic ranking approach based on the Copeland’s pairwise aggregation is used to rank components importance in [22]. In addition, a strategy for solving the component placement problem by maximizing the information gain in terms of users’ choices in [23] is proposed. At last, Zhu et al. [24] present a nonlinear binary programming model, which focuses on embedding the Birnbaum importance in heuristics and the method of dealing with more than one type of components.However, to the best of our knowledge, none of the exiting classical importance methods based on Cellular Automata are directly applied to measure the impact of the component importance on the reliability of system. The Birnbaum importance, risk growth factor, and reliability stability to measure the importance of a component or a group of components are defined. A computing method of component importance (NEA) based on Cellular Automata is designed; in addition, a new measure method of reliability stability (NSA) is proposed in this paper. At last, the validities of NSA and NEA are proved by experiments. And it is also proved that the proposed algorithm NSA is more accurate in calculating the importance of the system components compared to the classical algorithm in [25].The main contributions are as follows:(i)
defining the Birnbaum importance, risk growth factor, and reliability stability;(ii)
designing a model for measuring the network system component importance;(iii)
designing a method for measuring the reliability stability of network system.The rest of this paper is organized as follows. Three metrics of component importance are introduced in Section2, and the validity of these measurements is verified in this section. In Section 3, we put forward our system models. In Section 4, we evaluate the component importance and describe our algorithms. In Section 5, the parameters of experiment are given and the performance of the algorithms is analyzed. The conclusion is drawn in Section 6.


## 2. Preliminaries

LetG=(V,E) be a network system, where V is the set of n nodes, V={vi∣i=1,2,⋯,n}. E⊆V×V is the set of m arcs, E={ei∣i=1,2,⋯,m}. G is a directed, connected, acyclic graph which contains an initial node s and a terminal node t. In order to study the issue of this paper, there are some assumptions.(i)
The state of each node and arc is statistically independent.(ii)
The evaluation of network reliabilityR is considered so that the probability of the initial node s successfully connects to the terminal node t.


### 2.1. Birnbaum Measure

The significance of network system component importance is the influence degree of network system components (nodes or links) on network system connectivity, which can be expressed by the Birnbaum measure [9], denoting the importance of network system decided by the reliability of network system and component. The nature of this definition mathematically denotes the partial derivative on the reliability of component to the reliability of network system; that is, when the component reliability is changed, the network system reliability will be accordingly changed. For a network system with m components, its Birnbaum measure can be defined as (1)IiBt=∂Ft∂Fit,1≤i≤m.Here F(t) is the function of network system failure, Fi(t) is the failure function of network system component i, and the relation of failure function and reliability function is F(t)=1-R(t).Theorem 1.
For a network system withm components, the mathematical expression of Birnbaum measure is (2)IiBt=1-∂Rt1-∂Rit=∂Rt∂Rit,1≤i≤m.Here, IiB(t) is the Birnbaum measure of component i, R(t) is the function of network system reliability, and Ri(t) is the reliability function of component i. If IiB(t) is larger, the impact on network system reliability R(t) is greater when the reliability of component i is changed.
Equation (2) shows the changes of network system reliability in the case of component i from normal state to failure state. Thus, Birnbaum measure can be defined as(3)IiBt=∂Rt∂Rit=PrRei=1t-PrRei=0t,1≤i≤m.Here Rei=1(t) is the network system reliability when component i is normal and Rei=0(t) is the network system reliability when component i is failure.


### 2.2. Critical Importance

In network system, the failure rate of each component is different, so Lambert [9] proposes a critical importance to describe the probability of network system failure caused by network system component i. It can also be functioned as(4)IiCMFt=∂Ft∂Fit×∂Fit∂Ft,1≤i≤m.From the perspective of the whole system, (4) can be further converted to the following one:(5)IiCMFt=IiBt×∂Fit∂Ft,1≤i≤m.Equation (5) shows that the reliability of network system is the product of the Birnbaum measure of component i and the ratio of system failure rate, when the state of component i is from the normal to failure.


### 2.3. Network System Reliability Stability

Assuming that a network systemG contains m components, the risk growth factor [26] of component i can be defined as(6)RGIit=Fei=0t-Ft=1-Rei=0t-1-Rt=Rt-Rei=0t.Here Fei=0(t) is the network system failure rate when component i is in malfunction. This formula describes the impact of the failure of component i on system reliability. In addition, based on (6), the other two reliability metrics, average risk and reliability stability, can be concluded, which measure the impact of single component malfunction on network reliability. The average risk growth factor can be expressed as follows by its own definition:(7)ARGIt=∑i=1mRGIitn=∑i=1mRt-Rei=0tn,where is the average impact of all components failure individually on the network system reliability. On the basis of (7), the network reliability stability [26] can be formulated as(8)RSt=Rt-ARGItRt.It can be known, by the definition of network system reliability stability, that the network system reliability stability and network system reliability are greatly related to the network system average risk growth factor. When RS(t)→1, the network system component failure has little impact on the network system reliability, and vice versa.


### 2.4. Experimental Analysis

For any network system, it is noted that the complexity of network topology can make network components decomposed as combination of series and parallel system, and the complexity needed by optimal solution grows exponentially with the network size [27]. Next we will verify the validity of the previous measurements for different network structures using typical data recommended by [5, 14].(1) Series System.Assuming that a system has m components connected in series configuration, the system will operate as long as all components are working. For Figure 1(a), the failure rates of components 1, 2, 3 in the network are f1≐0.001,f2≐0.003,f3≐0.004. When t=50, their reliabilities are, respectively, R1=0.95,R2=0.86, and R3=0.82. By [27], the reliability of network system is R(t)=R1×R2×R3=0.6703, so the Birnbaum measurements of three components are as follows.(9)I1Bt=∂R∂R1=R2×R3=0.7046I2Bt=∂R∂R2=R1×R3=0.7788I3Bt=∂R∂R3=R1×R2=0.8187Obviously, I1B(t)<I2B(t)<I3B(t). Component 1 has more impact on the system. Increasing or decreasing the failure of component 3 will be the biggest change to the reliability of the system, so component 3 is the most important component of the system. In addition, the critical importance of components can be computed based on the Birnbaum measurements and (5).(10)I1CMFt=I1Bt×1-∂R1t1-∂Rt=I1Bt×1-R11-R=0.1407I2CMFt=I2Bt×1-∂R2t1-∂Rt=I2Bt×1-R21-R=0.3636I3CMFt=I3Bt×1-∂R3t1-∂Rt=I3Bt×1-R31-R=0.4501By I1CMF(t)<I2CMF(t)<I3CMF(t) and the definition of critical importance, the probability of component 3 leads to the malfunction when the system is failure.Figure 1
Series system and parallel system.Based on (6), the risk growth fact of each component in system can be computed.(11)RGI1t=Rt-Re1=0t=Rt=0.6703RGI2t=Rt-Re2=0t=Rt=0.6703RGI3t=Rt-Re3=0t=Rt=0.6703The reliability stability depends on the risk growth fact of component, so the reliability stability can be calculated.(12)RSt=Rt-RGI1t+RGI2t+RGI3t/3Rt=0The result of risk growth fact is not the same as Birnbaum measurement. For each component, RGI1(t)=RGI2(t)=RGI3(t). According to physical significance, the failure of any network component in the series network system will lead to the failure of the network system, so the normal operation of series network requires no failure of all components. However, the reliability stability of network system is 0; on the basis of the definition of reliability stability, when RS(t)→0, the failure of component has an increasing influence on the reliability of network system. therefore, if there is a single component failure, the network must be failure.(2) Parallel System.For Figure 1(b), the failure rates of components 1, 2, 3 in the network are f1=0.001,f2=0.003,f3=0.004. When t=50, their reliabilities are, respectively, R1=0.95,R2=0.86, and R3=0.82. Based on [14], the reliability of network system is R(t)=1-(1-R1)×(1-R2)×(1-R3)=0.9892, so the Birnbaum measurements of three components are as follows.(13)I1Bt=∂R∂R1=1-R2×1-R3=0.0252I2Bt=∂R∂R2=1-R1×1-R3=0.0088I3Bt=∂R∂R3=1-R1×1-R2=0.0067Obviously,I1B(t)>I2B(t)>I3B(t). Component 1 has more impact on the system. Increasing or decreasing the failure of component 1 will be the biggest change to the reliability of the system, so component 1 is the most important component in the system. In addition, the critical importance of components can be computed based on the Birnbaum measurements and (5).(14)I1CMFt=I1Bt×1-∂R1t1-∂Rt=I1Bt×1-R11-R1×1-R2×1-R3=0.9907I2CMFt=I2Bt×1-∂R2t1-∂Rt=I2Bt×1-R21-R1×1-R2×1-R3=0.9923I3CMFt=I3Bt×1-∂R3t1-∂Rt=I3Bt×1-R31-R1×1-R2×1-R3=0.9945Based on I1CMF(t)>I2CMF(t)>I3CMF(t) and the definition of critical importance, if network system is failure, the probability of component 3 leading to the failure of system is the biggest.According to (6), the risk growth facts of components are as follows.(15)RGI1t=Rt-Re1=0t=R1×1-R2×1-R3=0.0240RGI2t=Rt-Re2=0t=R2×1-R1×1-R3=0.0076RGI3t=Rt-Re3=0t=R3×1-R1×1-R2=0.0055However, the reliability stability depends on the risk growth fact of each component, so the reliability stability of the system is as follows.(16)RSt=Rt-RGI1t+RGI2t+RGI3t/3Rt=0.9875The result of risk growth fact is not the same as Birnbaum measurement; for each component, RGI1(t)=RGI2(t)=RGI3(t). According to physical significance, the failure of any network component in the parallel network system has little influence on the reliability of network system. However, the reliability stability of network system is 0.9875; on the basis of the definition of reliability stability, when RS(t)→1, the failure of component has less and less influence on network system reliability. Therefore, in the parallel network, the probability of the failure of single component leading to system’s failure is very small, so the parallel network is more stable than the serial network.


## 2.1. Birnbaum Measure

The significance of network system component importance is the influence degree of network system components (nodes or links) on network system connectivity, which can be expressed by the Birnbaum measure [9], denoting the importance of network system decided by the reliability of network system and component. The nature of this definition mathematically denotes the partial derivative on the reliability of component to the reliability of network system; that is, when the component reliability is changed, the network system reliability will be accordingly changed. For a network system with m components, its Birnbaum measure can be defined as (1)IiBt=∂Ft∂Fit,1≤i≤m.Here F(t) is the function of network system failure, Fi(t) is the failure function of network system component i, and the relation of failure function and reliability function is F(t)=1-R(t).Theorem 1.
For a network system withm components, the mathematical expression of Birnbaum measure is (2)IiBt=1-∂Rt1-∂Rit=∂Rt∂Rit,1≤i≤m.Here, IiB(t) is the Birnbaum measure of component i, R(t) is the function of network system reliability, and Ri(t) is the reliability function of component i. If IiB(t) is larger, the impact on network system reliability R(t) is greater when the reliability of component i is changed.
Equation (2) shows the changes of network system reliability in the case of component i from normal state to failure state. Thus, Birnbaum measure can be defined as(3)IiBt=∂Rt∂Rit=PrRei=1t-PrRei=0t,1≤i≤m.Here Rei=1(t) is the network system reliability when component i is normal and Rei=0(t) is the network system reliability when component i is failure.


## 2.2. Critical Importance

In network system, the failure rate of each component is different, so Lambert [9] proposes a critical importance to describe the probability of network system failure caused by network system component i. It can also be functioned as(4)IiCMFt=∂Ft∂Fit×∂Fit∂Ft,1≤i≤m.From the perspective of the whole system, (4) can be further converted to the following one:(5)IiCMFt=IiBt×∂Fit∂Ft,1≤i≤m.Equation (5) shows that the reliability of network system is the product of the Birnbaum measure of component i and the ratio of system failure rate, when the state of component i is from the normal to failure.


## 2.3. Network System Reliability Stability

Assuming that a network systemG contains m components, the risk growth factor [26] of component i can be defined as(6)RGIit=Fei=0t-Ft=1-Rei=0t-1-Rt=Rt-Rei=0t.Here Fei=0(t) is the network system failure rate when component i is in malfunction. This formula describes the impact of the failure of component i on system reliability. In addition, based on (6), the other two reliability metrics, average risk and reliability stability, can be concluded, which measure the impact of single component malfunction on network reliability. The average risk growth factor can be expressed as follows by its own definition:(7)ARGIt=∑i=1mRGIitn=∑i=1mRt-Rei=0tn,where is the average impact of all components failure individually on the network system reliability. On the basis of (7), the network reliability stability [26] can be formulated as(8)RSt=Rt-ARGItRt.It can be known, by the definition of network system reliability stability, that the network system reliability stability and network system reliability are greatly related to the network system average risk growth factor. When RS(t)→1, the network system component failure has little impact on the network system reliability, and vice versa.


## 2.4. Experimental Analysis

For any network system, it is noted that the complexity of network topology can make network components decomposed as combination of series and parallel system, and the complexity needed by optimal solution grows exponentially with the network size [27]. Next we will verify the validity of the previous measurements for different network structures using typical data recommended by [5, 14].(1) Series System.Assuming that a system has m components connected in series configuration, the system will operate as long as all components are working. For Figure 1(a), the failure rates of components 1, 2, 3 in the network are f1≐0.001,f2≐0.003,f3≐0.004. When t=50, their reliabilities are, respectively, R1=0.95,R2=0.86, and R3=0.82. By [27], the reliability of network system is R(t)=R1×R2×R3=0.6703, so the Birnbaum measurements of three components are as follows.(9)I1Bt=∂R∂R1=R2×R3=0.7046I2Bt=∂R∂R2=R1×R3=0.7788I3Bt=∂R∂R3=R1×R2=0.8187Obviously, I1B(t)<I2B(t)<I3B(t). Component 1 has more impact on the system. Increasing or decreasing the failure of component 3 will be the biggest change to the reliability of the system, so component 3 is the most important component of the system. In addition, the critical importance of components can be computed based on the Birnbaum measurements and (5).(10)I1CMFt=I1Bt×1-∂R1t1-∂Rt=I1Bt×1-R11-R=0.1407I2CMFt=I2Bt×1-∂R2t1-∂Rt=I2Bt×1-R21-R=0.3636I3CMFt=I3Bt×1-∂R3t1-∂Rt=I3Bt×1-R31-R=0.4501By I1CMF(t)<I2CMF(t)<I3CMF(t) and the definition of critical importance, the probability of component 3 leads to the malfunction when the system is failure.Figure 1
Series system and parallel system.Based on (6), the risk growth fact of each component in system can be computed.(11)RGI1t=Rt-Re1=0t=Rt=0.6703RGI2t=Rt-Re2=0t=Rt=0.6703RGI3t=Rt-Re3=0t=Rt=0.6703The reliability stability depends on the risk growth fact of component, so the reliability stability can be calculated.(12)RSt=Rt-RGI1t+RGI2t+RGI3t/3Rt=0The result of risk growth fact is not the same as Birnbaum measurement. For each component, RGI1(t)=RGI2(t)=RGI3(t). According to physical significance, the failure of any network component in the series network system will lead to the failure of the network system, so the normal operation of series network requires no failure of all components. However, the reliability stability of network system is 0; on the basis of the definition of reliability stability, when RS(t)→0, the failure of component has an increasing influence on the reliability of network system. therefore, if there is a single component failure, the network must be failure.(2) Parallel System.For Figure 1(b), the failure rates of components 1, 2, 3 in the network are f1=0.001,f2=0.003,f3=0.004. When t=50, their reliabilities are, respectively, R1=0.95,R2=0.86, and R3=0.82. Based on [14], the reliability of network system is R(t)=1-(1-R1)×(1-R2)×(1-R3)=0.9892, so the Birnbaum measurements of three components are as follows.(13)I1Bt=∂R∂R1=1-R2×1-R3=0.0252I2Bt=∂R∂R2=1-R1×1-R3=0.0088I3Bt=∂R∂R3=1-R1×1-R2=0.0067Obviously,I1B(t)>I2B(t)>I3B(t). Component 1 has more impact on the system. Increasing or decreasing the failure of component 1 will be the biggest change to the reliability of the system, so component 1 is the most important component in the system. In addition, the critical importance of components can be computed based on the Birnbaum measurements and (5).(14)I1CMFt=I1Bt×1-∂R1t1-∂Rt=I1Bt×1-R11-R1×1-R2×1-R3=0.9907I2CMFt=I2Bt×1-∂R2t1-∂Rt=I2Bt×1-R21-R1×1-R2×1-R3=0.9923I3CMFt=I3Bt×1-∂R3t1-∂Rt=I3Bt×1-R31-R1×1-R2×1-R3=0.9945Based on I1CMF(t)>I2CMF(t)>I3CMF(t) and the definition of critical importance, if network system is failure, the probability of component 3 leading to the failure of system is the biggest.According to (6), the risk growth facts of components are as follows.(15)RGI1t=Rt-Re1=0t=R1×1-R2×1-R3=0.0240RGI2t=Rt-Re2=0t=R2×1-R1×1-R3=0.0076RGI3t=Rt-Re3=0t=R3×1-R1×1-R2=0.0055However, the reliability stability depends on the risk growth fact of each component, so the reliability stability of the system is as follows.(16)RSt=Rt-RGI1t+RGI2t+RGI3t/3Rt=0.9875The result of risk growth fact is not the same as Birnbaum measurement; for each component, RGI1(t)=RGI2(t)=RGI3(t). According to physical significance, the failure of any network component in the parallel network system has little influence on the reliability of network system. However, the reliability stability of network system is 0.9875; on the basis of the definition of reliability stability, when RS(t)→1, the failure of component has less and less influence on network system reliability. Therefore, in the parallel network, the probability of the failure of single component leading to system’s failure is very small, so the parallel network is more stable than the serial network.


## 3. Network Topology Decomposing Model Based on Cellular Automata

For large-scale network system, decomposing algorithm makes it simpler subsystems from scratch. In this paper, we use DB-CA algorithm based on cellular automaton (CA) to decompose network in [2]. In network G, let IVi and OVi be neighborhood of node i, with each node i mapping to a cell whose neighborhood is represented by two sets of nodes connected to it by its input arcs and output arcs, respectively. IVi={ej∣ej=vk,vi,j∈(1,m),vk∈V,ej∈E}, OVi={ej∣ej=vi,vk,j∈(1,m),vk∈V,ej∈E}. The state of each node at time ts is represented by a set ISi(ts). The elements appearing in set ISi(ts) can be expressed as ei1∗ei2∗⋯eik∗, eij∗∈{1,eij,e¯ij},j=1,2,⋯,k. Let eij∗1=1eij∗=eij∗.Theorem 2 (see [2]).
For anypi,pj∈SP, there exists item ek, such that both Pi and Pj contain the same items, and the items in Pi and Pj are complementary; then Pi and Pj are disjoint. Otherwise Pi will intersect with Pj.
Collecting all output paths generated by Algorithm1, path set SP of the network is obtained, it is clear from Algorithm 1 and Theorem 2 that SP is a disjoint path set. Let p is the number of items in SP, P be the items constituting the SP, and c be the number of arcs in Pi. By using Theorem 2 together with (5) in [2], the network fuzzy reliability expression at time t takes the following form:(17)R~t=1-∏i-1p1-∏j=1cRijwhereRij=e-h~kt,ifeij⋆=ek;Rij=1-e-hkt,ifeij⋆=ek¯.Algorithm 1:DB-CA.
Input: a network G(V,E) with source node s and terminal node t are represented by node v1 and vn respectively; Output: decomposed path set SP; ( 1 ) Let IS1(ts)={1}, ts=0; ( 2 )  forvi∈V and vi≠v1  do ( 3 )  I S i ( t s ) = ∅; ( 4 )  end for ( 5 )  forvi∈V and vi≠vn  do ( 6 )  I S i ( t s + 1 ) = ∅, ∀m∈ISi(ts), call Enumeration Procedure (m)[2]; ( 7 )  end for ( 8 )  if  ∃vi∈V, vi≠vn and ISi(ts+1)≠∅  then ( 9 )  ts=ts+1, go to (5); ( 10 )  end if ( 11 )   S P = ⋃ i = 0 t s ( I S n ( i ) ); ( 12 )  return  SP;


## 4. Component Importance Estimation

### 4.1. Component Importance Evaluation Model Based on DB-CA

To simplify the importance evaluation method discussed in Section3, an importance measure model based on two hypotheses is proposed; the network node reliability and the link failures are independent of each other.Theorem 3.
For a networkG with m components, the importance evaluation index of its any component i is as follows:importance:IiB(t)=∂R(t)/∂Rit=Pr(fei=1(G)=1)-Pr(fei=1(G)=0);critical importance:IiCMF(t)=IiB(t)×Fit/Ft;risk growth factor:RGIi(t)=Fei=0(t)-F(t)=R(t)-Rei=0(t).
Herefei=1(G) denotes the reliability function of G when network component i is normal and fei=0(G) represents the reliability function of G when network component i is failure.Lemma 4.
In a networkG, the Birnbaum measure of any component i in the network can be obtained by the following recursion formula:(18)IiBt=Prfei=1G=1-Prfei=0G=1j=i,Prej≐1×Prfei=1G=1-Prej≐0×Prfei=1G=1j≠i.Lemma 5.
The network topology decomposing method based on Cellular Automata in Section3 decomposes network G, a disjoint set denoted as DB(G) can be calculated, and the Birnbaum measure of any component i in the network can be obtained by the following recursion formula:(19)IiBt=RelDBG,i=+RelDBGei=1,ij=i-1×RelDBGei=0,ij=i+Prej=1×RelDBGei=1,ij≠i-1×Prej=0×RelDBGei=0,ij≠iwhere DBGei=1 is the remaining links in a path when component i works normally, DBGei=0 is the remaining links in a path when component i is failure. If DBGei=1 does not contain component i, then Rel(DBGei=1,i)=1; if DBGei=0 contains component i, then Rel(DBGei=0,i)=0.Consequently, the network system component importance algorithm (NEA) can be designed as in Algorithm2.Algorithm 2:NEA.
Input: Network G with source node s and terminal node t; Ouput:  Rel(DB(G),i) and Rel(DB(G)); ( 1 ) Use DB-CA to decompose network G; ( 2 ) Let Rel(DB(G),i)=0; ( 3 ) Assume DBi(G)=∅ and Rel(DB(G))=0; ( 4 ) Let Rel(pj)=1 for any pj in DB(G); ( 5 )  for  any path k in Pj,  do ( 6 )  R e l ( p j ) = R e l ( p j ) × P r ( e l ),where l∈[1,k]; ( 7 )  if  i == k,   then ( 8 ) put path pj into DBi(G); ( 9 )  end if ( 10 )   end for ( 11 ) Let Rel(DB(G))=Rel(DB(G))+Rel(pj), ( 12 )   if  there are any path not been precessed  then ( 13 ) go to (5); ( 14 )  end if ( 15 )  return  DB(G) and Rel(DB(G)); ( 16 )  for  any path pj in DBi(G), Rel(pj)=1  do ( 17 )  while  k≠i  do ( 18 )  R e l ( p j ) = P r ( e k = S t a t e ) × R e l ( p j ∣ e k = S t a t e ),where State∈{0,1}; ( 19 )  end while ( 20 )  while  k==i  do ( 21 )  R e l ( p j ) = P r ( e k ) × R e l ( p j ∣ e k ); ( 22 )  if  ek=0  then ( 23 )  R e l ( p j ) = - 1 × R e l ( p j ); ( 24 )  else  {ek=0} ( 25 )  R e l ( p j ) = 1 × R e l ( p j ); ( 26 )  end if ( 27 )  end while ( 28 ) end for ( 29 ) Let Rel(DB(G),i)=Rel(DB(G),i)+Rel(pj) ( 30 ) if  there are any path in DB(G) not given processed  then ( 31 ) go to (16) ( 32 ) end if ( 33 ) return  Rel(DB(G),i) and Rel(DB(G)).


### 4.2. Network System Reliability Stability Evaluation Based on DB-CA

The stability describes the impact of component failure on the reliability of network system: the greater the stability value is, the less the impact of component failure on the reliability of network system is; otherwise the impact will be greater.Lemma 6.
For the networkG with m components, the reliability stability can be expressed as follows.(20)RSt=1/m×∑j=1mRelDBGej=0RelDBGProof.
By (8), the following result is(21)RSt=Rt-ARGItRt=1-ARGItRelDBGand based on (7)(22)ARGIt=∑i=1mRt-Rei=0tn=n×RelDBG-∑j=1mRelDBGej=0mso(23)RSt=1/m×∑j=1mRelDBGej=0RelDBG
and this is the end of the proof.Lemma 7.
With Theorem1, the risk growth factor is RGIi(t)=R(t)-Rei=0(t) for any component i. Thus the risk growth factor of component i and the network reliability are related to the network reliability when component i is failure; the network reliability and the network reliability when component i fails must be calculated. The computing process of network system is as follows.(24)RSt=RelDBG=+Prei=1×RelDBGej=11≤j≤n-1×Prei=0×RelDBGej=01≤j≤nBased on Lemma 5, the recurrence formula of network system reliability under component i failure can be proposed.(25)Rei=0t=RelDBGei=0,i=+0×RelDBGei=1,ij=i-1×RelDBGei=0,ij=i+Prei=1×RelDBGei=1,ij≠i-1×Prei=0×RelDBGei=0,ij≠iOn the basis of this, the evaluation algorithm of reliability stability evaluation algorithm is as shown in Algorithm 3.Algorithm 3:NSA.
Input: Network G with source node s and terminal node t; Output:  Rel(DB(G),i) and Rel(DB(G),i); ( 1 ) Use DB-CA to decompose network G; ( 2 ) Let Rel(DBGej=0)=0; ( 3 )  for  any not been processed path Pj in DB(G),   do ( 4 )  R e l ( p j ) = 1; ( 5 )  for  any not been processed link ek in pj,   do ( 6 )  R e l ( p j ) = R e l ( p j ) × P r ( e l ),where l∈[1,k],l≠i ( 7 )  if  l = i,   then ( 8 )  R e l ( p j e l = 1 ) = 0 or  Rel(pjel=0)=1×Rel(pj) ( 9 )  end if ( 10 )  end for ( 11 ) end for ( 12 ) if there are any link in pj not been precessed  then ( 13 ) go to (5); ( 14 ) end if ( 15 ) Let Rel(DBGej=0)=Rel(DBGej=0)+Rel(pj), ( 16 ) if there are any path not been precessed  then ( 17 ) go to (3); ( 18 ) end if ( 19 ) return  Rel(DBGej=0); ( 20 ) if  component c is present in the network G,its Rel(pjec=0) is not been computed,   then ( 21 ) go to (2); ( 22 )  end if ( 23 ) return  Rel(DB(G)) and Rel(DBGej=0), j=1,2,…,m.


## 4.1. Component Importance Evaluation Model Based on DB-CA

To simplify the importance evaluation method discussed in Section3, an importance measure model based on two hypotheses is proposed; the network node reliability and the link failures are independent of each other.Theorem 3.
For a networkG with m components, the importance evaluation index of its any component i is as follows:importance:IiB(t)=∂R(t)/∂Rit=Pr(fei=1(G)=1)-Pr(fei=1(G)=0);critical importance:IiCMF(t)=IiB(t)×Fit/Ft;risk growth factor:RGIi(t)=Fei=0(t)-F(t)=R(t)-Rei=0(t).
Herefei=1(G) denotes the reliability function of G when network component i is normal and fei=0(G) represents the reliability function of G when network component i is failure.Lemma 4.
In a networkG, the Birnbaum measure of any component i in the network can be obtained by the following recursion formula:(18)IiBt=Prfei=1G=1-Prfei=0G=1j=i,Prej≐1×Prfei=1G=1-Prej≐0×Prfei=1G=1j≠i.Lemma 5.
The network topology decomposing method based on Cellular Automata in Section3 decomposes network G, a disjoint set denoted as DB(G) can be calculated, and the Birnbaum measure of any component i in the network can be obtained by the following recursion formula:(19)IiBt=RelDBG,i=+RelDBGei=1,ij=i-1×RelDBGei=0,ij=i+Prej=1×RelDBGei=1,ij≠i-1×Prej=0×RelDBGei=0,ij≠iwhere DBGei=1 is the remaining links in a path when component i works normally, DBGei=0 is the remaining links in a path when component i is failure. If DBGei=1 does not contain component i, then Rel(DBGei=1,i)=1; if DBGei=0 contains component i, then Rel(DBGei=0,i)=0.Consequently, the network system component importance algorithm (NEA) can be designed as in Algorithm2.Algorithm 2:NEA.
Input: Network G with source node s and terminal node t; Ouput:  Rel(DB(G),i) and Rel(DB(G)); ( 1 ) Use DB-CA to decompose network G; ( 2 ) Let Rel(DB(G),i)=0; ( 3 ) Assume DBi(G)=∅ and Rel(DB(G))=0; ( 4 ) Let Rel(pj)=1 for any pj in DB(G); ( 5 )  for  any path k in Pj,  do ( 6 )  R e l ( p j ) = R e l ( p j ) × P r ( e l ),where l∈[1,k]; ( 7 )  if  i == k,   then ( 8 ) put path pj into DBi(G); ( 9 )  end if ( 10 )   end for ( 11 ) Let Rel(DB(G))=Rel(DB(G))+Rel(pj), ( 12 )   if  there are any path not been precessed  then ( 13 ) go to (5); ( 14 )  end if ( 15 )  return  DB(G) and Rel(DB(G)); ( 16 )  for  any path pj in DBi(G), Rel(pj)=1  do ( 17 )  while  k≠i  do ( 18 )  R e l ( p j ) = P r ( e k = S t a t e ) × R e l ( p j ∣ e k = S t a t e ),where State∈{0,1}; ( 19 )  end while ( 20 )  while  k==i  do ( 21 )  R e l ( p j ) = P r ( e k ) × R e l ( p j ∣ e k ); ( 22 )  if  ek=0  then ( 23 )  R e l ( p j ) = - 1 × R e l ( p j ); ( 24 )  else  {ek=0} ( 25 )  R e l ( p j ) = 1 × R e l ( p j ); ( 26 )  end if ( 27 )  end while ( 28 ) end for ( 29 ) Let Rel(DB(G),i)=Rel(DB(G),i)+Rel(pj) ( 30 ) if  there are any path in DB(G) not given processed  then ( 31 ) go to (16) ( 32 ) end if ( 33 ) return  Rel(DB(G),i) and Rel(DB(G)).


## 4.2. Network System Reliability Stability Evaluation Based on DB-CA

The stability describes the impact of component failure on the reliability of network system: the greater the stability value is, the less the impact of component failure on the reliability of network system is; otherwise the impact will be greater.Lemma 6.
For the networkG with m components, the reliability stability can be expressed as follows.(20)RSt=1/m×∑j=1mRelDBGej=0RelDBGProof.
By (8), the following result is(21)RSt=Rt-ARGItRt=1-ARGItRelDBGand based on (7)(22)ARGIt=∑i=1mRt-Rei=0tn=n×RelDBG-∑j=1mRelDBGej=0mso(23)RSt=1/m×∑j=1mRelDBGej=0RelDBG
and this is the end of the proof.Lemma 7.
With Theorem1, the risk growth factor is RGIi(t)=R(t)-Rei=0(t) for any component i. Thus the risk growth factor of component i and the network reliability are related to the network reliability when component i is failure; the network reliability and the network reliability when component i fails must be calculated. The computing process of network system is as follows.(24)RSt=RelDBG=+Prei=1×RelDBGej=11≤j≤n-1×Prei=0×RelDBGej=01≤j≤nBased on Lemma 5, the recurrence formula of network system reliability under component i failure can be proposed.(25)Rei=0t=RelDBGei=0,i=+0×RelDBGei=1,ij=i-1×RelDBGei=0,ij=i+Prei=1×RelDBGei=1,ij≠i-1×Prei=0×RelDBGei=0,ij≠iOn the basis of this, the evaluation algorithm of reliability stability evaluation algorithm is as shown in Algorithm 3.Algorithm 3:NSA.
Input: Network G with source node s and terminal node t; Output:  Rel(DB(G),i) and Rel(DB(G),i); ( 1 ) Use DB-CA to decompose network G; ( 2 ) Let Rel(DBGej=0)=0; ( 3 )  for  any not been processed path Pj in DB(G),   do ( 4 )  R e l ( p j ) = 1; ( 5 )  for  any not been processed link ek in pj,   do ( 6 )  R e l ( p j ) = R e l ( p j ) × P r ( e l ),where l∈[1,k],l≠i ( 7 )  if  l = i,   then ( 8 )  R e l ( p j e l = 1 ) = 0 or  Rel(pjel=0)=1×Rel(pj) ( 9 )  end if ( 10 )  end for ( 11 ) end for ( 12 ) if there are any link in pj not been precessed  then ( 13 ) go to (5); ( 14 ) end if ( 15 ) Let Rel(DBGej=0)=Rel(DBGej=0)+Rel(pj), ( 16 ) if there are any path not been precessed  then ( 17 ) go to (3); ( 18 ) end if ( 19 ) return  Rel(DBGej=0); ( 20 ) if  component c is present in the network G,its Rel(pjec=0) is not been computed,   then ( 21 ) go to (2); ( 22 )  end if ( 23 ) return  Rel(DB(G)) and Rel(DBGej=0), j=1,2,…,m.


## 5. Numerical Examples

In this section, NEA and NSA will be applied to the sample networks, shown in Figure2; thus the Birnbaum measure of component and network reliability stability of each sample network can be calculated. By comparing the importance of the components in some network systems with different network topologies in Figure 1, the correctness of algorithms can be verified.Figure 2
Network topology.
(a)
Sample network 1 (b)
Sample network 2 (c)
Sample network 3 (d)
Sample network 4For all the sample networks in Figure2, assuming that the failure rate of each component recommended by [5, 14] is 0.003 and t=50, by DB-CA, the disjoint paths set of each sample network is obtained as follows:SP1=aed,a¯fcd,ae¯bcd,abe¯fcd;SP2=bf,b¯acg,bf¯dcg,b¯acg¯ef,bfd¯acg;SP3={a¯fg,abc,ab¯dg,a¯fg¯ec,ab¯dg¯ec,abc¯eg,abd¯fg, abd¯fg¯ec,abce¯dg,abcde¯fg};SP4={af,achf¯,abecf¯bg,ahcef¯bg,ahbcf¯de, ahbcef¯dg,ahf¯bg; abhf¯dg,a¯hc,ac¯beh,ace¯bgh,ah¯bg}.As a result, the corresponding components Birnbaum measure and risk growth factor RGI of all sample networks in Figure1 are shown in Table 1. And according to (1), the results are as follows:(i)
the network reliability of sample network 1 is 0.7496, and the network reliability stability is 0.7038;(ii)
the network reliability of sample network 2 is 0.9273, and the network reliability stability is 0.8683;(iii)
the network reliability of sample network 3 is 0.9550, and the network reliability stability is 0.9132;(iv)
the network reliability of sample network 4 is 0.9892, and the network reliability stability is 0.9759.Table 1
Birnbaum measure and risk growth factor RGI.
link Sample Network 1 Sample Network 2 Sample Network 3 Sample Network 4 Birnbaum Measure RGI Birnbaum Measure RGI Birnbaum Measure RGI Birnbaum Measure RGI a 0.3115 0.2749 0.1108 0.1101 0.1457 0.1254 0.0511 0.0440 b 0.0131 0.0098 0.2758 0.2133 0.0301 0.0259 0.0370 0.0318 c 0.1125 0.0959 0.1916 0.1865 0.1333 0.1148 0.0226 0.0195 d 0.9388 0.7496 0.0062 0.0106 0.0178 0.0153 0.0039 0.0034 e 0.1492 0.1384 0.0292 0.0106 0.0301 0.0259 0.0039 0.0034 f 0.0907 0.0632 0.4210 0.2133 0.1520 0.1308 0.0226 0.0195 g − − 0.1308 0.1101 0.1644 0.1415 0.0370 0.0318 h − − − − − − 0.0511 0.0440


### 5.1. Test Analysis I

Through the study of all sample networks in Figure2, with corresponding components Birnbaum measure and risk growth factor RGI, the importance of link d in Figure 2(a) is 0.9388, which is higher than those of link f, g in Figure 2(b). Combining with the topology of Figure 2(a) and Figure 2(b), we can conclude that the fewer the links to a node, the more the importance to the reliability of the node. Correspondingly, the same results can be concluded from the Birnbaum measures of link c, g in Figure 2(c) and link f, g, h in Figure 2(d)).Analyzing the importance of network system components, the next step is reliability calculation. Therefore, the computing time can be used as an important factor to evaluate the efficiency of algorithm. Accordingly, we compare the computational efficiency of network system component importance analysis method based on Cellular Automata (NSA) proposed in this paper and importance analysis method based on Monte Carlo (MCC) [27]. Since the MCC will spend more time on the sample collection process to calculate the reliability and component importance, the time of MCC is almost twice as much as that of NSA for the sample networks 1, 2, 3, 4. Thus, the efficiency of NSA proposed in this paper is better. From the time cost of each sample network in Table 2, combined with its own topology, we can conclude that, for the same number of nodes, the network topology is more complex and the rise of the computing time cost is almost doubled, which is related to the time cost increasing with the complexity of network when the network topology is decomposed by DB-CA.Table 2
Comparative experiment.
Sample Network NSA MCC reliability stability Computingtime/s reliability stability Computingtime/s 1 0.7496 0.7038 0.853 0.7550 0.6996 1.429 2 0.9273 0.8683 1.235 0.9342 0.8635 2.013 3 0.9550 0.9132 1.573 0.9597 0.9106 2.987 4 0.9892 0.9759 1.823 0.9206 0.9699 3.581


### 5.2. Test Analysis II

In all sample networks in Figure2, we assume that the failure rate of each component in networks recommended by [5, 14] is 0.003 and the interval time t=50; the reliability of each sample network and the corresponding network reliability stability are shown in Figure 3. Firstly, we compare sample network 1 and sample network 2 with 5 nodes, and in sample network 1, there is a single link to a node; based on practical engineering experience, compared with sample network 2 the impact on the network reliability is more serious when the link is failure in sample network 1, which conforms to the result shown in Figure 3. Next, the sample network 2 and sample network 4 with 5 nodes are compared; the reliability and reliability stability of sample network 4 are higher than those of sample network 2. Because, with the same nodes, when some link fails in a network, the one with more links has more choices to achieve network connectivity, the survivability of the network is also improved. Finally, the sample network 2 and sample network 3 with 5 nodes and 7 links are compared; the reliability and reliability stability of sample network 3 are higher than those of sample network 2, because of the difference of network topology. In the case where origin node 1 and destination node 5 are connected, sample network 2 has longer path, which increases the failure probability of path and leads the reliability and reliability stability of sample network 2 to be lower than those of sample network 3. Through the above comparison results, it will be found that network survivability can be described by the network reliability stability in the case of the random failure of network system components.Figure 3
The reliability stability of sample networks.In the sample network in Figure2(b), according to the measure method of link importance proposed in the literature [25], the Hash map is as shown in Figure 4. The comparison of the Birnbaum measure of sample network 2 in Table 1 and the Hash map can be concluded: the most important component of sample network 2 by 2 methods is link b; when the network link importance is calculated by NSA, the partial order relationship of Birnbaum measures and the Hash map of each link are consistent, which proves the correctness of the methods proposed in the paper.Figure 4
The topology of a network system.However, it is found that the importance on some links cannot be ordered, by analysis in Hash map, for example, linkb and f, link a and g, and link d and e in sample network 2. However, based on proposed methods in this paper, it can be concluded that the importance of link f is higher than that of link b, the importance of link g is higher than that of link a, and the importance of link e is higher than that of link d.


## 5.1. Test Analysis I

Through the study of all sample networks in Figure2, with corresponding components Birnbaum measure and risk growth factor RGI, the importance of link d in Figure 2(a) is 0.9388, which is higher than those of link f, g in Figure 2(b). Combining with the topology of Figure 2(a) and Figure 2(b), we can conclude that the fewer the links to a node, the more the importance to the reliability of the node. Correspondingly, the same results can be concluded from the Birnbaum measures of link c, g in Figure 2(c) and link f, g, h in Figure 2(d)).Analyzing the importance of network system components, the next step is reliability calculation. Therefore, the computing time can be used as an important factor to evaluate the efficiency of algorithm. Accordingly, we compare the computational efficiency of network system component importance analysis method based on Cellular Automata (NSA) proposed in this paper and importance analysis method based on Monte Carlo (MCC) [27]. Since the MCC will spend more time on the sample collection process to calculate the reliability and component importance, the time of MCC is almost twice as much as that of NSA for the sample networks 1, 2, 3, 4. Thus, the efficiency of NSA proposed in this paper is better. From the time cost of each sample network in Table 2, combined with its own topology, we can conclude that, for the same number of nodes, the network topology is more complex and the rise of the computing time cost is almost doubled, which is related to the time cost increasing with the complexity of network when the network topology is decomposed by DB-CA.Table 2
Comparative experiment.
Sample Network NSA MCC reliability stability Computingtime/s reliability stability Computingtime/s 1 0.7496 0.7038 0.853 0.7550 0.6996 1.429 2 0.9273 0.8683 1.235 0.9342 0.8635 2.013 3 0.9550 0.9132 1.573 0.9597 0.9106 2.987 4 0.9892 0.9759 1.823 0.9206 0.9699 3.581


## 5.2. Test Analysis II

In all sample networks in Figure2, we assume that the failure rate of each component in networks recommended by [5, 14] is 0.003 and the interval time t=50; the reliability of each sample network and the corresponding network reliability stability are shown in Figure 3. Firstly, we compare sample network 1 and sample network 2 with 5 nodes, and in sample network 1, there is a single link to a node; based on practical engineering experience, compared with sample network 2 the impact on the network reliability is more serious when the link is failure in sample network 1, which conforms to the result shown in Figure 3. Next, the sample network 2 and sample network 4 with 5 nodes are compared; the reliability and reliability stability of sample network 4 are higher than those of sample network 2. Because, with the same nodes, when some link fails in a network, the one with more links has more choices to achieve network connectivity, the survivability of the network is also improved. Finally, the sample network 2 and sample network 3 with 5 nodes and 7 links are compared; the reliability and reliability stability of sample network 3 are higher than those of sample network 2, because of the difference of network topology. In the case where origin node 1 and destination node 5 are connected, sample network 2 has longer path, which increases the failure probability of path and leads the reliability and reliability stability of sample network 2 to be lower than those of sample network 3. Through the above comparison results, it will be found that network survivability can be described by the network reliability stability in the case of the random failure of network system components.Figure 3
The reliability stability of sample networks.In the sample network in Figure2(b), according to the measure method of link importance proposed in the literature [25], the Hash map is as shown in Figure 4. The comparison of the Birnbaum measure of sample network 2 in Table 1 and the Hash map can be concluded: the most important component of sample network 2 by 2 methods is link b; when the network link importance is calculated by NSA, the partial order relationship of Birnbaum measures and the Hash map of each link are consistent, which proves the correctness of the methods proposed in the paper.Figure 4
The topology of a network system.However, it is found that the importance on some links cannot be ordered, by analysis in Hash map, for example, linkb and f, link a and g, and link d and e in sample network 2. However, based on proposed methods in this paper, it can be concluded that the importance of link f is higher than that of link b, the importance of link g is higher than that of link a, and the importance of link e is higher than that of link d.


## 6. Conclusion

Evaluating the importance of components for complex networks is of great significance to the research of survivability and robusticity of networks. A component importance algorithm (NSA) and a reliability stability measure algorithm (NEA) based on DB-CA are proposed in this paper. NSA can well identify the importance of component with lower computational complexity, NEA can evaluate the influence of component failure on the reliability of network system, and the impact value can mostly affect the reliability of network system. The experimental results show that the proposed methods can effectively and precisely evaluate the impact of an arc failure in a network system. Future work is to implement our methods in various types of real network systems, for example, cloud computing system, social network system, and traffic network system. In particular, thek-out-of-n system will be the next topic, in addition to correspondingly perfect and optimized measure methods according to system usage pattern.



---

*Source: 3971597-2019-05-02.xml*