# Analysis of Road Traffic Network Cascade Failures with Coupled Map Lattice Method

Authors: Yanan Zhang; Yingrong Lu; Guangquan Lu; Peng Chen; Chuan Ding
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In recent years, there is growing literature concerning the cascading failure of network characteristics. The object of this paper is to investigate the cascade failures on road traffic network, considering the aeolotropism of road traffic network topology and road congestion dissipation in traffic flow. An improved coupled map lattice (CML) model is proposed. Furthermore, in order to match the congestion dissipation, a recovery mechanism is put forward in this paper. With a real urban road traffic network in Beijing, the cascading failures are tested using different attack strategies, coupling strengths, external perturbations, and attacked road segment numbers. The impacts of different aspects on road traffic network are evaluated based on the simulation results. The findings confirmed the important roles that these characteristics played in the cascading failure propagation and dissipation on road traffic network. We hope these findings are helpful to find out the optimal road network topology and avoid cascading failure on road network.


---

## Body

## 1. Introduction

In many large-scale networks, the failure of a node or edge would make the other nodes fail and lead to a chain reaction due to the coupling relationships among nodes. This phenomenon is known as network cascading failure. Cascading failure problems may take place on many natural or artificial networks, such as the Internet [1, 2], power grids [3–6], and traffic networks [7–11]. The effects from large destruction may be caused by cascading failures on the entire networks. Many cities have suffered from serious traffic paralysis that brought great inconvenience to people’s normal life (e.g., Beijing urban traffic was shut down completely due to the rainstorm on July 21, 2012). Therefore, it is essential to understand the cascading failure on traffic network to prevent or reduce the influences of large-scale failure.Many scholars have studied the impacts of network topology [7, 12], network connectivity [13], different attack strategies [4, 14, 15], and network robustness [16–18] on cascading failure. To describe the cascading failure, coupled map lattice (CML) model has been widely applied in previous literatures. For example, using the basic CML method, Xu and Wang [12] studied the cascading failures in different network topologies. Based on the proposed edge-based CML method, Di et al. [19] investigated the cascading failure on random networks and scale-free networks. Though most studies paid attention to the artificial network on cascading failure, the research that applies CML model to investigate the natural road traffic network on cascading failure is limited.Because the properties of natural road traffic network are different from artificial networks, the particular road traffic network properties need to be concerned when we use CML model. One of the particular properties is aeolotropism. Due to the fact that there are one-way and two-way streets in the city, the road traffic network is supposed to be described as directed graphs. Another particular property is restorability, which means that road congestions can dissipate over a certain range. The road traffic network consists of intersections and road segments. Vehicles travel on the network and form the distributed traffic flow. If traffic congestions occur in one or some road segments, congestions can be gradually dissipated after a period of time due to the redistribution of traffic flow. These two particular properties may lead to unique cascading failures rules in road traffic network.Considering the above particular properties, the original CML model will be improved for analyzing cascading failures of road traffic network. The improved CML model is expected to express the aeolotropism of road traffic network topology, which will be proposed in the following section. Besides, in order to match the pattern of road congestion dissipation, a recovery mechanism has been put forward in the next part. For the purpose of deliberating cascading failures roundly, an empirical network in Beijing is tested to investigate the impacts of different attack strategies, coupling strengths, external perturbations, and attacked road segment numbers on road traffic network.The remainder of this paper is organized as follows. The next section will introduce the improved CML model and the recovery mechanism. Then, the simulations based on the empirical network are conducted. Finally, the highlights of this paper are concluded.


## 2. Road Traffic Network Cascading Failures Model Based on CML

The original CML model is formulated as follows [12]:(1)xit+1=1-εfxit+ε∑j=1,i≠jNai,jfxjtki,where xi(t) is the state of the ith node at the tth time step. ε∈0,1 is defined as the coupled strength. N is the sum of all nodes. k(i) represents the degree of the ith node. Adjacency matrix A=(aij)N×N is used to represent the topology of the network. If there is an edge between node i and node j, then aij=aji=1; otherwise, aij=aji=0. Chaotic Logistic map f(x)=μx(1-x) with μ∈(0,4] is used to denote dynamic behaviors of nodes. μ is closer to 4; the value of f(x) is more evenly distributed throughout the region of 0 to 1. Therefore, it is always set to be μ=4. The absolute value notation is used in (1) for ensuring nonnegative saturation state of each node.To describe the aeolotropism of road traffic network, an improved CML model is proposed to investigate the cascading failures on road traffic network. In the original CML model,xi(t) means the state of ith node at the tth time step, while, for road traffic network, it is expressed by road saturation:(2)xit+1=1-ε1-ε2fxit+ε2∑i=1,i≠jN1bijfxjtk-i+ε1∑j=1,i≠jN2bjifxitk+ii,j=1,2,…,n.In (2), xi(t) means the road saturation of the ith road segment at the tth time step. bij is the value of adjacency matrix B=(bij)N×N of the road traffic network. If there is an edge from node i to node j, then bij=1; otherwise, bij=0. ε1∈0,1 and ε2∈(0,1) delegate the coupled strengths of the start point and endpoints, respectively. N1 is the sum of all nodes’ out-degree, and N2 is that of in-degree. k+(i) and k-(i), respectively, represent the in-degree and out-degree of the ith node which means the number of downstream segments and upstream segments for the road traffic network.Cascading failure on road traffic network may be triggered by some internal and external factors (e.g., traffic congestion or crash) that lead to the failure of one or more roads. To describe this situation, an external perturbationR≥1 is added to the node k at the (m+1)th time as follows:(3)xkm+1>1=1-ε1-ε2fxkm+ε2∑k=1,k≠jN1bkjfxjmk-k+ε1∑j=1,k≠jN2bjkfxkmk+k+Ri,j=1,2,…,n.If0<xk(t)<1 when t≤m, the node k is in a normal state; if xk(m+1)≥1, the node k is defined to be failed at the (m+1)th time step. For the situation when the node k fails at the (m+1)th time step, xk(t)≡0 with t>m+1 is defined in previous studies [12, 19]. However, with regard to the road traffic network, the failure state could not continue all the time due to the fact that traffic congestion will gradually dissipate with the redistribution of traffic flow. A recovery mechanism to fit with road traffic characteristics is proposed in this study as follows.If an external perturbationR is added to the node k at the (m+1)th time step, xk(m+1)>1 means that road segment k has been in a blocked state at (m+1)th time step. If the upstream vehicles cannot enter, coupled strength of upstream segments and road segment k is set to be 0 (i.e., ε2=0). The saturation state of the kth node from (m+2)th step to (m+n+1)th step can be represented by (4). If xk(m+n+1)<1 after n steps, the saturation state of the kth node returns to normal, represented by (2). The recovery mechanism of the road traffic network on cascading failure is shown in Figure 1.Figure 1
Recovery mechanism of road traffic network on cascading failure.Consider(4)xit+1=1-ε1fxit+ε1∑j=1,i≠jN2bjifxitk+ii,j=1,2,…,n.The proportion of failed nodes at each time step is used to characterize road cascading failure process as shown in (5) and I is applied to represent the final P(t) to describe the size of cascading failure in the end:(5)Pt=N′tN.


## 3. Simulation Test and Analysis

To detail the computational experiment of cascading failure on road traffic network, the real road network of Liuliqiao area in Beijing (total road segments numberN=1004) is selected as the empirical network in this study, as shown in Figure 2(a). This area of more than 22 km2 contains the largest train station in Beijing and is considered a typical region showing transition between free flow and congestions. For the road network, nodes represent the intersections and edges represent the road segments between two intersections as shown in Figure 2(b). Using the proposed model, cascading failure on road traffic network is tested based on different attack strategies, coupling strengths, external perturbations, and attacked road segment numbers.Figure 2
(a) Map of Liuliqiao area in Beijing. (b) Network topology of Liuliqiao area in Beijing.
(a)
(b)


### 3.1. Different Attack Strategies

Different attack strategies would lead to different cascading failure on the network. In this study, to obtain the influences of different cascading failure, four kinds of attack strategies are tested: the deliberate attack based on betweenness (BA), the deliberate attack based on saturation (SA), the deliberate attack based on combination of betweenness and saturation (BSA), and the random attack (RA).Parameterλ is used to characterize the three attack strategies (BA, SA, and BSA) as follows:(6)fit=λxit+1-λbit,where λ(0≤λ≤1) is a weight coefficient. xi(t) is the saturation state and bi(t) is the betweenness of the ith node at the mth time step. fi(t) is the combination of betweenness and saturation of the ith node with a fixed value λ. λ=0 represents BA and the initial failure nodes are deleted in turn according to betweenness. If multiple maximum betweenness nodes exist, we choose the node being attacked in a random manner and λ=1 refers to SA which means that the nodes are attacked gradually with saturation. Similarly, the node is randomly selected to be attacked when maximum saturation nodes exist. For BSA, each attack selects the node with maximum combination of degree and betweenness, while the value of λ equals 0.5. RA means that the node to be attacked randomly.For BA, SA, and BSA, external perturbationR=1.5 is added to a node with the largest value of fi (corresponding to different values of λ). For RA, R=1.5 is added to a randomly chosen node. Figure 3 shows the results of four kinds of attacking strategies with ε1=ε2=0.6.Figure 3
P
(
t
) based on different attack strategies.Figure3 shows the occurrence of failure and the process of recovery. This phenomenon is in conformity with the actual road traffic flow. Figure 3 also shows that BA triggers cascading failures more easily than SA. The scale of failure recovery time under BA is longer than SA. This phenomenon implies that betweenness has more destructive impacts on cascading failures than saturation. As shown in Figure 3, RA is least likely to trigger cascading failures and the failures recovery time is also the shortest. It is reasonable for that the node being randomly attacked is usually not that node which has deteriorated impact on network cascading failure. Interestingly, comparing to other three attacks, BSA has the most serious impacts on network, including the largest number of failed nodes, the fastest propagation rate of failure, and the longest recovery time. This implies that those road segments, which have the largest value of combination of betweenness and saturation, are the key nodes causing large-scale cascading failures once attacked. These findings give the guidance on daily traffic control that the potential cascading failures could be avoided by supervising the key road segments and their adjacent segments.


### 3.2. Different Coupling Strength

The deficiency of giving the coupled strength a fixed value subjectively [19] is overcome in this study. In the case of different values of ε1 and ε2, cascading failures are triggered by adding the same external perturbation R=1.5 on one node with RA. The simulation results are shown in Figure 4. Figure 4(a) plots the proportion of failed nodes P(t) versus time step t with fixed value of coupling strength ε2(ε2=0.6) and varying values of ε1(ε1=0.1,0.2,…,0.9). Oppositely, Figure 4(b) presents the time series of P(t) with fixed value of coupling strength ε1(ε1=0.6) and varying values of ε2(ε2=0.1,0.2,…,0.9).Figure 4
P
(
t
) based on different coupled strength.
(a)
(b)According to Figures4(a) and 4(b), when the value of ε1 or ε2 is below 0.5, road traffic network cascading failures hardly occur. As the value of the coupling strength increases, especially larger than 0.6, the number of failed nodes and the failure recovery time increase sharply.Figure5 shows coupled strength against ratio of total failed nodes number I for the different attack strategies. Road traffic network cascading failures are triggered by external perturbation R=1.5. We can see that the size of cascading failures increases as the value of the coupling strength increases. This is consistent with the findings from Figure 4. Figure 5 also shows that there is a threshold for each attack strategy. Only when the value of coupling strength is larger than the threshold, the cascading failures occur. For example, the BA curve shows that the cascading failures occur when ε1 is larger than 0.4 in Figure 5(b). Comparing four attacks, the threshold of BSA is the smallest. This illustrates that the deliberate attack based on combination of betweenness and saturation is likely to cause cascading failures even under the low coupling strength.Figure 5
I based on different coupled strength and attack strategies.
(a)
(b)Comparing Figure5(a) with Figure 5(b), the curves of RA and SA present a different trend. In Figure 5(a), if the value of coupling strength ε2 is less than 0.6, the size of cascading failure with RA is smaller than SA. When the value of ε2 is larger than 0.7, the size of cascading failure with SA is smaller than RA. In Figure 5(b), SA is always larger than RA. This phenomenon may be due to the fact that random attack might select the noncritical nodes or the critical nodes, leading to different results.


### 3.3. Different External PerturbationR

The impact of different external perturbationR on the cascading failure on road traffic network is analyzed by adding varying external perturbation R on a fixed node. Figure 6 shows that the proportion of failed nodes Pt varies with the time step t in the case of different value of R with ε1=ε2=0.6. The inset of Figure 6 shows the time series of Pt for the value of R between 1 and 2 (R=1,1.2,1.4,1.6,1.8,2).Figure 6
P
(
t
) based on different value of R.According to Figure6, with the increase of R value, the number of failed nodes and failure recovery time increase. There is a threshold Rc for R. Only when the value of R is larger than the Rc, the large-scale cascading failures occur seriously. The inset of Figure 6 shows that Rc value is between 1 and 2. There are a few failed nodes (less than 1% of N) in the road traffic network when the value of R is smaller than 1.2. The finding is useful that we could prevent the occurrence of large-scale failures by controlling the value of R less than the threshold.Figure7 shows that the ratio of total failed nodes I is positively correlated to the external perturbation R and the results are highly dependent on the attack strategies. BSA is the most likely to trigger cascading failures even under small value of external perturbation R.Figure 7
I based on different external perturbation R and attack strategies.


### 3.4. Different Number of Road Segments Being Attacked

To confirm the number of nodes being attacked causing large-scale cascading failure, the simulation based on different number of road segments is conducted. Figure8 shows P(t) based on different value of n (percentage of segments being attack) and different attack strategies. Figure 9 indicates n against the proportion of total failed nodes I with different attack strategies. The simulation parameters are set to be ε1=ε2=0.6 and R=1.5.Figure 8
P
(
t
) based on different value of n.
(a)
(b)
(c)
(d)Figure 9
I based on different attack strategies.In Figure8, for the same n value, the destruction impacts under four kinds of attack strategies are different. This is consistent with the previous analysis. However, in this section’s numerical simulation, the whole network might totally become failed, which means that the size of cascades is equal to the size N of the network (I=1). Figure 8 clearly shows that the network can be restored when the number of nodes being attacked is small, while as n increases to a certain value, all of the nodes in the network will be ineffective and difficult to recover. The certain value is the critical value nc. We should pay more attention to the critical value nc to avoid the devastating failure. In our simulations, for the RA strategy (i.e., Figure 8(d)), we find that nc=4.5%. In Figure 8(b), the nc for BSA is 3%. The values of nc under different attack strategies are various and the descending order is as follows: RA, SA, BA, and BSA. This implies that the large-scale failure most likely happens under BSA.According to Figure9, the more the nodes being attacked are, the larger the size of cascading failure will be. The simulations also express that, for the same n, the scale of the network cascading failures under BSA is the largest. nc for each attack strategy can be seen more obviously in Figure 9. For the road traffic network of Liuliqiao area, all values of nc under four attacks are smaller than 5%, which illustrates that out-road traffic network’s invulnerability is low. Therefore, we should take measures to ensure the reliability of the network and control the number of nodes being attacked to be less than the critical value nc.


## 3.1. Different Attack Strategies

Different attack strategies would lead to different cascading failure on the network. In this study, to obtain the influences of different cascading failure, four kinds of attack strategies are tested: the deliberate attack based on betweenness (BA), the deliberate attack based on saturation (SA), the deliberate attack based on combination of betweenness and saturation (BSA), and the random attack (RA).Parameterλ is used to characterize the three attack strategies (BA, SA, and BSA) as follows:(6)fit=λxit+1-λbit,where λ(0≤λ≤1) is a weight coefficient. xi(t) is the saturation state and bi(t) is the betweenness of the ith node at the mth time step. fi(t) is the combination of betweenness and saturation of the ith node with a fixed value λ. λ=0 represents BA and the initial failure nodes are deleted in turn according to betweenness. If multiple maximum betweenness nodes exist, we choose the node being attacked in a random manner and λ=1 refers to SA which means that the nodes are attacked gradually with saturation. Similarly, the node is randomly selected to be attacked when maximum saturation nodes exist. For BSA, each attack selects the node with maximum combination of degree and betweenness, while the value of λ equals 0.5. RA means that the node to be attacked randomly.For BA, SA, and BSA, external perturbationR=1.5 is added to a node with the largest value of fi (corresponding to different values of λ). For RA, R=1.5 is added to a randomly chosen node. Figure 3 shows the results of four kinds of attacking strategies with ε1=ε2=0.6.Figure 3
P
(
t
) based on different attack strategies.Figure3 shows the occurrence of failure and the process of recovery. This phenomenon is in conformity with the actual road traffic flow. Figure 3 also shows that BA triggers cascading failures more easily than SA. The scale of failure recovery time under BA is longer than SA. This phenomenon implies that betweenness has more destructive impacts on cascading failures than saturation. As shown in Figure 3, RA is least likely to trigger cascading failures and the failures recovery time is also the shortest. It is reasonable for that the node being randomly attacked is usually not that node which has deteriorated impact on network cascading failure. Interestingly, comparing to other three attacks, BSA has the most serious impacts on network, including the largest number of failed nodes, the fastest propagation rate of failure, and the longest recovery time. This implies that those road segments, which have the largest value of combination of betweenness and saturation, are the key nodes causing large-scale cascading failures once attacked. These findings give the guidance on daily traffic control that the potential cascading failures could be avoided by supervising the key road segments and their adjacent segments.


## 3.2. Different Coupling Strength

The deficiency of giving the coupled strength a fixed value subjectively [19] is overcome in this study. In the case of different values of ε1 and ε2, cascading failures are triggered by adding the same external perturbation R=1.5 on one node with RA. The simulation results are shown in Figure 4. Figure 4(a) plots the proportion of failed nodes P(t) versus time step t with fixed value of coupling strength ε2(ε2=0.6) and varying values of ε1(ε1=0.1,0.2,…,0.9). Oppositely, Figure 4(b) presents the time series of P(t) with fixed value of coupling strength ε1(ε1=0.6) and varying values of ε2(ε2=0.1,0.2,…,0.9).Figure 4
P
(
t
) based on different coupled strength.
(a)
(b)According to Figures4(a) and 4(b), when the value of ε1 or ε2 is below 0.5, road traffic network cascading failures hardly occur. As the value of the coupling strength increases, especially larger than 0.6, the number of failed nodes and the failure recovery time increase sharply.Figure5 shows coupled strength against ratio of total failed nodes number I for the different attack strategies. Road traffic network cascading failures are triggered by external perturbation R=1.5. We can see that the size of cascading failures increases as the value of the coupling strength increases. This is consistent with the findings from Figure 4. Figure 5 also shows that there is a threshold for each attack strategy. Only when the value of coupling strength is larger than the threshold, the cascading failures occur. For example, the BA curve shows that the cascading failures occur when ε1 is larger than 0.4 in Figure 5(b). Comparing four attacks, the threshold of BSA is the smallest. This illustrates that the deliberate attack based on combination of betweenness and saturation is likely to cause cascading failures even under the low coupling strength.Figure 5
I based on different coupled strength and attack strategies.
(a)
(b)Comparing Figure5(a) with Figure 5(b), the curves of RA and SA present a different trend. In Figure 5(a), if the value of coupling strength ε2 is less than 0.6, the size of cascading failure with RA is smaller than SA. When the value of ε2 is larger than 0.7, the size of cascading failure with SA is smaller than RA. In Figure 5(b), SA is always larger than RA. This phenomenon may be due to the fact that random attack might select the noncritical nodes or the critical nodes, leading to different results.


## 3.3. Different External PerturbationR

The impact of different external perturbationR on the cascading failure on road traffic network is analyzed by adding varying external perturbation R on a fixed node. Figure 6 shows that the proportion of failed nodes Pt varies with the time step t in the case of different value of R with ε1=ε2=0.6. The inset of Figure 6 shows the time series of Pt for the value of R between 1 and 2 (R=1,1.2,1.4,1.6,1.8,2).Figure 6
P
(
t
) based on different value of R.According to Figure6, with the increase of R value, the number of failed nodes and failure recovery time increase. There is a threshold Rc for R. Only when the value of R is larger than the Rc, the large-scale cascading failures occur seriously. The inset of Figure 6 shows that Rc value is between 1 and 2. There are a few failed nodes (less than 1% of N) in the road traffic network when the value of R is smaller than 1.2. The finding is useful that we could prevent the occurrence of large-scale failures by controlling the value of R less than the threshold.Figure7 shows that the ratio of total failed nodes I is positively correlated to the external perturbation R and the results are highly dependent on the attack strategies. BSA is the most likely to trigger cascading failures even under small value of external perturbation R.Figure 7
I based on different external perturbation R and attack strategies.


## 3.4. Different Number of Road Segments Being Attacked

To confirm the number of nodes being attacked causing large-scale cascading failure, the simulation based on different number of road segments is conducted. Figure8 shows P(t) based on different value of n (percentage of segments being attack) and different attack strategies. Figure 9 indicates n against the proportion of total failed nodes I with different attack strategies. The simulation parameters are set to be ε1=ε2=0.6 and R=1.5.Figure 8
P
(
t
) based on different value of n.
(a)
(b)
(c)
(d)Figure 9
I based on different attack strategies.In Figure8, for the same n value, the destruction impacts under four kinds of attack strategies are different. This is consistent with the previous analysis. However, in this section’s numerical simulation, the whole network might totally become failed, which means that the size of cascades is equal to the size N of the network (I=1). Figure 8 clearly shows that the network can be restored when the number of nodes being attacked is small, while as n increases to a certain value, all of the nodes in the network will be ineffective and difficult to recover. The certain value is the critical value nc. We should pay more attention to the critical value nc to avoid the devastating failure. In our simulations, for the RA strategy (i.e., Figure 8(d)), we find that nc=4.5%. In Figure 8(b), the nc for BSA is 3%. The values of nc under different attack strategies are various and the descending order is as follows: RA, SA, BA, and BSA. This implies that the large-scale failure most likely happens under BSA.According to Figure9, the more the nodes being attacked are, the larger the size of cascading failure will be. The simulations also express that, for the same n, the scale of the network cascading failures under BSA is the largest. nc for each attack strategy can be seen more obviously in Figure 9. For the road traffic network of Liuliqiao area, all values of nc under four attacks are smaller than 5%, which illustrates that out-road traffic network’s invulnerability is low. Therefore, we should take measures to ensure the reliability of the network and control the number of nodes being attacked to be less than the critical value nc.


## 4. Conclusion

This paper investigated the cascading failures based on the improved CML model. The improvements of CML model depended on the study of particular road traffic network properties, which are the aeolotropism of road traffic network topology and road congestion dissipation in traffic flow. With a real urban road traffic network in Beijing, the cascading failures are tested using different attack strategies, coupling strengths, external perturbations, and attacked road segment numbers; we found the following:(1) the aeolotropism and congestion dissipation for the road traffic network topology should be considered; (2) BSA leads to the largest number of failed nodes, of which the propagation rate of failure is the fastest and the failure recovery time is also the longest; (3) as the value of the coupling strength increases, the scale of the network cascading failure increases, and the scale of cascading failures is highly dependent on different attacks; (4) only when the value of external perturbation R is larger than the corresponding threshold of Rc, the large-scale cascading failures would occur, and the number of failed nodes and failure recovery time increase with the increase of R value; (5) the more the nodes being attacked are, the larger the size of cascading failure will be. If the number of nodes being attacked is larger than threshold of nc, the entire network failure would happen. The road traffic network of Liuliqiao area’s invulnerability is very low because the values of nc for different attacks are very small. The above findings might be useful in avoiding or alleviating large-scale failures of road traffic network.



---

*Source: 101059-2015-10-25.xml*