About the Authors:
Zhe-Ming Lu
Contributed equally to this work with: Zhe-Ming Lu, Xin-Feng Li
* E-mail: [email protected]
Affiliation: School of Aeronautics and Astronautics, Zhejiang University, Hangzhou, P. R. China
Xin-Feng Li
Contributed equally to this work with: Zhe-Ming Lu, Xin-Feng Li
Affiliation: School of Aeronautics and Astronautics, Zhejiang University, Hangzhou, P. R. China
Introduction
Complex networks are ubiquitous in nature and society describing various systems [1–3], the dynamics taking place on them has become one of the most popular research fields in the past decades [4–6]. Most previous works have been focused on dynamics such as epidemic spreading [7, 8], synchronization [6, 9, 10], random walk [11, 12], opinion formation [13, 14], and so on. However, our ultimate goal of studying complex networks is to develop the capacity to control them [15]. That is, driving the network from any initial state to any desired final state in finite time [15–18]. Although great efforts [19–24] have been devoted to understanding the controllability of networks, the results are less than satisfactory. Recently, Liu et al. [15] made a significant breakthrough, they applied the structural control theory [25] to directed networks and proved that the minimal number of nodes needed to fully control a network is determined by its ‘maximum matching’ [26]. Following this seminal work, some intensive and extensive issues have been carefully addressed, such as controlling linear edge dynamics [27], effects of topological characteristics on controllability [28], energy needed for control [29], control centrality [30] and controllability optimization [31]. Besides, given the limitation that the structural controllability framework is only applicable to directed networks, Yuan et al. [32] presented the exact controllability framework to explore the controllability of arbitrary networks, especially for undirected networks and networks with exact link weights.
Most of the existing works assume that networks are in a relatively safe environment. However, the real-world networks are always confronting with random or intentional node or edge attacks. For example, in the computer networks [33], node attacking can be interpreted as breakdowns of servers by malicious hackers while edge attacking may correspond to the cutting-off of communication cables. In power grids [34], attacks on nodes can be interpreted as substation failures while attacks on edges may correspond to the cases that the connections of subsections are cut off so the power cannot be transmitted from one substation to another. Previous studies have shown that random failures and intentional attacks can easily damage network functions such as connectivity [35] and synchronization [36]. Therefore, it is natural and interesting to ask how the attacks will affect the controllability of networks. Liu et al. [15] first addressed this problem using core percolation, pointing out that the robustness of network controllability is closely related to its core. Pu et al. [37] investigated the robustness of control under node-based cascade failures and found that even if a small range of node failures can trigger great harm to the network controllability. Inspired by Pu et al.’s work, Nie et al. [38] studied edge-based cascade failures and showed that the larger scale of cascades in scale-free networks does not mean that there will be more increments of driver nodes.
In addition to cascade attacks [39], prominence based attacks, especially degree and betweenness based attacks, are the most common attacks in practice [35]. For example, it has been shown that even if 1% of the most highly connected routers were incapacitated, the average performance of Internet would drop 50% [40]. Therefore, it is of practical significance to study the robustness of network controllability subject to this kind of attacks. In this paper, we systematically investigate the attack vulnerability of network controllability for the canonical model networks as well as the real-world networks subject to degree and betweenness based attacks on nodes and edges. For each case of attacks, five different strategies are employed and the network controllability is quantitatively measured by the fraction of driver nodes. Furthermore, we also investigate the control robustness of 25 real-world networks.
The rest of the paper is organized as follows. Section II gives a brief review of network controllability. Section III introduces our methods, including definitions, attack strategies and benchmark networks. Our main results and discussions are presented in Section IV. Finally, Section V concludes the whole paper.
Network Controllability
In this section, we briefly review the controllability of complex networks, both the structural controllability framework [15] and the exact controllability framework [32] are introduced. The former is only applicable to directed networks whereas the latter can treat arbitrary networks without any limitations [32].
Structural Controllability
Consider a network of N nodes governed by the following linear time invariant dynamics [15]:(1)where x(t) = (x1(t), …, xN(t))T stands for the states of nodes at time t, the N × N matrix A denotes the coupling strength between N nodes, where the element aij gives the strength or weight that node-j can affect node-i. u(t) = (u1(t), u2(t), …, uM(t))T is the vector of input signals and the N × M (M ≤ N) matrix B is called input matrix which defines how input signals are connected to the nodes in the network, which are often called ‘driver nodes’.
According to the classic Kalman rank condition [16, 41], the system described by Eq (1) is controllable if and only if(2)where C = [B, AB, A2B, …, AN − 1B] is called controllability matrix. Since the matrix A is fixed for a given network, in order to make the network fully controllable, one need to choose a suitable matrix B having the minimal number of driver nodes to satisfy the Kalman rank condition. However, the practical difficulty lies in that there are 2N − 1 possible combinations of selecting driver nodes. To say the least, even one can enumerate all the combinations efficiently, the link weights (aij) are often not known for real-world networks. In order to overcome the inherently incomplete information of link weights, Liu et al. [15] introduced the concept of ‘structural controllability’ [25] to complex networks. The structural controllability can ensure that a network is controllable for almost all weight combinations except for some pathological cases [15]. The authors also developed the minimum input theory to avoid brute-force searching, which states that the minimal number of driver nodes needed to fully control a network, ND, is determined by the maximum matching [26] in the network [15], where the unmatched nodes are exactly driver nodes. This theory allows one to find the driver nodes within rather than O(2N) time, where L denotes the number of links [15].
Liu et al.’s work also showed that a network’s controllability is mainly determined by its underlying degree distribution, networks that are sparse and heterogeneous are more difficult to control [15]. Let nD = ND/N denote the density of driver nodes, for Erdős-Rényi (ER) networks [42] with mean degree ⟨k⟩, Liu et al. give nD analytically as [15](3)While for scale-free networks [2] with mean degree ⟨k⟩ and degree exponent γ = γin = γout, nD is given by [15](4)
Exact Controllability
The exact controllability framework was proposed by Yuan et al. [32] to overcome the limitation that the structural controllability framework can only treat directed networks. As an alternative, the new paradigm can be applied to arbitrary network structures and link weights without any limitations [32].
Instead of empolying the Kalman rank condition, the exact controllability framework is based on the equivalent Popov-Belevitch-Hautus (PBH) rank condition [43], which stipulates that the system (Eq (1)) is controllable, if and only if(5)holds for any complex number ψ, where IN is the N × N identify matrix. It can be further proved that full control can be guaranteed if and only if all the eigenvalues λ of A satisfy Eq (5) [32]. From the perspective of matrix, the minimal number of driver nodes, ND, is defined by matrix B with ND = min{rank(B)}. Equivalently, Yuan et al. proved that for any network with arbitrary matrix A, ND is actually determined by the maximum geometric multiplicity μ(λi) of the eigenvalue λi of A [32], i.e.(6)where λi(i = 1, …, l) is the nonidentical eigenvalues of A and μ(λi) = N−rank(λiIN−A) is the geometric multiplicity of λi. In particular, for undirected networks, ND is simply determined by the maximum algebraic multiplicity δ(λi) of λi [32], i.e.(7)
For large sparse networks, ND can be dramatically simplified in terms of rank(A) [32], i.e.(8)
Methods
In this section, we introduce our experimental methods, which include definitions, attack strategies and benchmark networks.
Definitions
In this paper, we allow the existence of self loops in the network but multiple (parallel) edges are not allowed. We also denote the number of nodes as N and the number of edges as L.
The measure of controllability nD, or simply controllability, of a network is defined as the ratio of the minimum number of driver nodes ND to the network size N [15], i.e.(9)
The degree kv of a node v is defined as the number of its direct connections to other nodes. The degree ke of an edge e is defined as(10)where e connects nodes u and v with degrees ku and kv.
The betweenness centrality of a node v is defined as(11)where σst is the total number of shortest paths from node s to node t and σst(v) is the number of those paths that pass through v. Similarly, the edge betweenness centrality of an edge e is defined as(12)where σst(e) is the number of shortest paths from node s to node t that include the edge e. Throughout the present paper, we call CB(v) and CB(e) the node betweenness and the edge betweenness for brevity.
Attack Strategies
Here we consider five different attack strategies for nodes and edges. The nodes are removed in the descending order of degree or betweenness centrality calculated for either the initial network or the current network during the removal procedure. Random attack (also called random failure) is taken as a comparison. The five node attack strategies are described as follows:
* Random Attack (RA): to remove node one by one randomly.
* Initial Degree Attack (ID): to remove node one by one in the descending order of degree using the degree distribution of the initial network.
* Initial Betweenness Attack (IB): to remove node one by one in the descending order of betweenness using the betweenness distribution of the initial network.
* Recalculated Degree Attack (RD): to remove node one by one in the descending order of degree using the recalculated degree distribution at every removal step.
* Recalculated Betweenness Attack (RB): to remove node one by one in the descending order of betweenness using the recalculated betweenness distribution at every removal step.
Note that the degree-based attacks (ID and RD) are local strategies, whereas the betweenness-based attacks (IB and RB) are global strategies. Another significant difference is that the former concentrate on reducing the total edges as fast as possible whereas the latter concentrate on destroying as many as the shortest paths as possible.
The above strategies can also be applied to edge attacks by simply replacing node degree and betweenness with edge degree and betweenness. The attack vulnerability of network controllability subject to such edge attacks is also investigated in this paper.
Networks
We select four canonical model networks as well as two real networks as benchmarks to study the robustness of network controllability. All the six networks are undirected and in the following experiments the exact controllability framework [32] will be adopted to calculate their controllability.
The ER model [42] is a classic random network with a Poisson-type degree distribution P(k) = e−⟨k⟩⟨k⟩k/k!, a logarithmically increasing average path length and a small clustering coefficient close to zero. The Watts-Strogatz (WS) model [1] and Newman-Watts (NW) model [44] are classic small world networks, which have short average path lengths (∼ln N) and high clustering coefficients. Both of them are constructed from a regular ring lattice with each node linking to its left and right K/2 nearest neighbors, the only difference is that the former rewires edges with probability p whereas the latter adds edges with probability p. The shape of their degree distribution is similar to that of ER, having a pronounced peak at k = K and decaying exponentially for large |k − K|. The Barabási-Albert (BA) model [2] is a representative scale free network with the power-law degree distribution P(k)∼k − 3.
The two real-world networks are the USAir97 network and the Erdos971 network. The USAir97 [45] is a network formed by the direct air route between the American airports in 1997. It has 332 nodes and 2126 edges as shown in Fig 1(a). Each node stands for an airport and each directed edge represents an airline from one airport to another. The weight of an edge represents the number of seats available on the scheduled flights. USAir97 exhibits an approximate power-law degree distribution as shown in Fig 1(b). The airports with less connections to/from other airports follow more closely with the fitting curve whereas the airports with more connections show a slight deviation.
[Figure omitted. See PDF.]
Fig 1. The USAir97 network.
(a) Its topology, in which the darkness of node color is proportional to its degree. (b) Its degree distribution, where the points represent the frequency distribution of degree, the red line denotes the fitting curve with equation P(k) = 0.1948k−0.6959−0.01029, the goodness of fit is 0.9198.
https://doi.org/10.1371/journal.pone.0162289.g001
The Erdos971 [45] is a scientific collaboration network where each node represents an scientist who co-authored at least one paper with Paul Erdős [42], and two scientists are joined by an edge if they co-authored a paper. Note that the node corresponding to Paul Erdős himself and all the isolated components have been removed throughout the paper, the truncated network contains 429 nodes and 1312 edges. Its topology and degree distribution are displayed in Fig 2(a) and 2(b), respectively.
[Figure omitted. See PDF.]
Fig 2. The Erdos971 network.
(a) Its topology, in which the darkness of node color is proportional to its degree. (b) Its degree distribution, where the points represent the frequency distribution of degree, the red line denotes the fitting curve with equation P(k) = 0.2727k−0.4256−0.06745, the goodness of fit is 0.9434.
https://doi.org/10.1371/journal.pone.0162289.g002
The parameter settings and summaries of the benchmark networks are shown in Table 1.
[Figure omitted. See PDF.]
Table 1. The summaries of benchmark networks used in this paper.
https://doi.org/10.1371/journal.pone.0162289.t001
Results and Discussions
Node Attack
Firstly, we investigate the control robustness of the ER random network under node attacks and show the results in Fig 3. It can be seen that for all the attacks, nD increases with the removal fraction f, indicating that we need constantly increase driver nodes to fully control the network, i.e., the network’s controllability is decreasing. The intentional attacks (ID, RD, IB and RB) are much more harmful than RA as their nD increases much faster. For the former attacks, the difference among them is not significant in the early stage of removals (), which can be attributed to the high degree-betweenness correlation (high degree nodes tend to have high betweenness) [35] and the negligible redistribution of degree and betweenness information for small f. However, as the removals proceed (f > 0.07), they gradually separate by harming the network controllability in the order RD > RB ≃ ID > IB (the inequality RD > RB means that RD is more harmful than RB), revealing that degree-based attacks are more harmful than betweenness-based attacks (RD > RB and ID > IB) and the attacks based on recalculated information are, as expected, more harmful than their counterparts based on initial information (RD > ID and RB > IB), which confirms the previous conclusions that network controllability is mainly determined by degree distribution [15] but distance based measures such as betweenness can also affect the controllability [46].
[Figure omitted. See PDF.]
Fig 3. The density of driver nodes nD as a function of removal fraction f for ER network under different node attacks.
The black and blue dashed lines are theoretical results obtained from Eqs (24) and (26), respectively. The numerical results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g003
For RA and ID attacks, we can give the analytical results of nD by employing the cavity method [15]. The ER network follows a Possion degree distribution P(k) = e−⟨k⟩⟨k⟩k/k!, indicating that most nodes have almost the same degree close to ⟨k⟩0, the average degree of the original network. Therefore, for RA it is reasonable to assume that every removed node has degree ⟨k⟩0, then the average degree after removals is(13)According to Liu et al.’s work [15], for networks where in-degrees and out-degrees share the similar distribution, nD can be obtained by(14)where is the predefined generating function, w1 and w2 can be derived from the following equations:(15) (16)where with Q(k) = kP(k)/⟨k⟩ [31].
For RA, since the removal fraction is small (f ≤ 0.2), we assume that the degree distribution P(k) is not significantly affected. By plugging into P(k) and P(k) into G(x), one has(17)Similarly, by plugging P(k) into Q(k) and Q(k) into H(x), one has(18)
From Eqs (15) and (16) and the monotonicity of H(x), one can easily check that w1 = H(w2) and w2 = 1 − H(1 − w1). Substituting H(x) gives(19) (20)where w1 can be further reduced by substituting w2 into Eq (19), as follows(21)
Now nD can be simplified as(22)For k ≫ 1, one has w1 ∼ e−⟨k⟩0(1 − f), , and thus(23)Ignoring the higher order term in Eq (23) gives the final nD as(24)
For ID attack, let kmax denote the maximum degree after removing Nf high degree nodes, then . The average degree after removals, , can be derived as follows(25)For simplicity, let where α is a constant coefficient, we have . Using the similar method, nD can be approximated as(26)where the specific α can be obtained by curve fitting. From Fig 3 we can see that the theoretical results of Eqs (24) and (26) agree well with their corresponding numerical results.
Next, we compare the two small world model networks, WS and NW, both of which have exponential cutoffs in the degree distribution. From Fig 4, we can see that the two networks exhibit very similar vulnerability behavior: nD increases as the removals proceed, RB harm the controllability most, followed by the degree-base attacks and IB, RA is the least harmful strategy (RB > ID, RD > IB > RA). This phenomenon is mainly due to their similar construction method that both are generated from the one dimensional regular ring lattice. The most interesting and unexpected behavior is that for both networks, RB proves to be the most harmful strategy and the superiority even becomes more obvious for large f (f > 0.1 for WS, for NW), which is beyond our expectation that degree-based attacks (at least RD) should be more harmful than betweenness-based ones due to the decisive role of degree distribution to network controllability.
[Figure omitted. See PDF.]
Fig 4. nD as a function of the removal fraction f under different node attacks for (a) WS network and (b) NW network.
The results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g004
To explain this behavior, we explore the correlation between the node betweenness CB and the node degree k as shown in Fig 5a, from which we can see that the correlation is quite weak, which excludes the possibility that degree helps to contribute the effects of RB. Recall that the two prominent characteristics of small world networks are the short average path length (APL) and the high clustering. Since recent study [28] has shown that clustering has no discernible impact on network controllability, thus the effectiveness of RB can only be attributed to the small APL, which again confirms that betweenness also affects network’s controllability [46]. Our results clearly show that RB is the most efficient way to destroy the controllability of small world networks rather than RD.
[Figure omitted. See PDF.]
Fig 5.
(a) Correlation between the node betweenness CB and the node degree k for WS and NW networks. (b) The degree distribution of WS, NW and ER network.
https://doi.org/10.1371/journal.pone.0162289.g005
From Fig 4, we can also see that the degree-based attacks on WS and NW networks behave quite differently from those on the ER network. The nD value of the former has a clear slowdown trend for large f whereas the latter does not. For WS network, both RD and ID harm the network controllability equally in the interval 0 ≤ f ≤ p, after that ID prevails RD but with less and less superiority, finally coincides with the latter at f = 0.2. The emergence of watershed (f ≈ p = 0.1) can be explained since when f exceeds p, the original WS topology is lost, the network degenerates into a regular ring lattice. It is worth noting that WS is the only case where a procedure based on recalculated information is less harmful than its counterpart based on the initial configuration (RD < ID). For NW network, RD retains as harmful as RB for , then slows down for f > 0.14, the emergence of the turning point (f ≈ 0.14) occurs later than that of WS (f ≈ 0.1) due to its longer tail of degree distribution as shown in Fig 5b resulting from adding instead of rewiring edges.
The BA model is in focus in the first study of the control vulnerability of scale-free networks. From Fig 6, we can see that all the attacks except RA harm the network controllability equally for , after that the degree-based strategies prevail the betweenness-based ones with negligible advantages. This coincidence should not be attributed to the short APL like the WS and NW network but the high correlation between the node betweenness and degree as shown in Fig 7a. It can also be seen that nD rises from 0.01 to about 0.19 (ΔnD ≈ 0.18), which is much more significant than that of the ER (ΔnD ≈ 0.10), WS (ΔnD ≈ 0.07) and NW (ΔnD ≈ 0.07) network, indicating that the scale free networks are more control vulnerable than both the ER random and small world networks, which is due to the existence of hub nodes resulting from the power-law degree distribution as shown in Fig 7b. Another notable finding is that though Liu et al. have shown that driver nodes tend to avoid to be hub nodes [15], here we show that attacking the hub nodes is still the most efficient way to harm the controllability of scale free networks.
[Figure omitted. See PDF.]
Fig 6. nD as a function of removal fraction f under different node attacks for the BA scale-free network.
The simulation results are averaged over 100 independent realizations, the analytical result of RA is obtained by Eq (27).
https://doi.org/10.1371/journal.pone.0162289.g006
[Figure omitted. See PDF.]
Fig 7.
(a) Node betweenness-degree correlation of the BA network. (b) The degree distribution of the BA network.
https://doi.org/10.1371/journal.pone.0162289.g007
The analytical result of nD for the RA attack can be obtained by employing the cavity method [15]. The BA network follows a power-law degree distribution with P(k)∼2m2 k−3 [2], since the removal fraction f is small, we assume that the degree distribution P(k) is not significantly affected, which gives us [15](27)where ⟨k⟩0 and γ0 = −3 are the average degree and degree exponent of the original network, respectively. From Fig 6 we can see that the theoretical prediction agrees well with the numerical result with negligible difference.
The two real-world networks, USAir97 and Erdos971, display very similar vulnerable behaviors like the BA scale-free network for the intentional attacks as shown Fig 8, which is mainly due to their power-law degree distributions as shown Figs 1b and 2b. Nevertheless, the differences between them are significant. For USAir97, it can be seen that the intentional attacks harm the network controllability almost equally in the early stage of removal (), which is due to the strong betweenness-degree correlation in the region of high degrees as shown in Fig 9a, after that the strategies based on recalculated information prevail those based on initial configuration (RB, RD > IB, ID) owing to the redistribution of degree and betweenness information. Besides, the betweenness-based strategies outperform those degree-based ones (RB > RD and IB > ID) with very slight superiorities. The most confusing and unexpected behavior is that nD decreases with f for RA, which means that we need less and less driver nodes to maintain the full control of network, i.e., the network controllability is indeed increasing, this abnormal phenomenon has not been observed in other cases and the reason behind is not clear and needs further research.
[Figure omitted. See PDF.]
Fig 8. nD as a function of removal fraction f under different node attacks for the (a) USAir97 and (b) Erdos971 network.
The results are averaged over 100 independent runs.
https://doi.org/10.1371/journal.pone.0162289.g008
[Figure omitted. See PDF.]
Fig 9. The node betweenness-degree correlation for the (a) USAir97 and (b) Erdos971 network.
https://doi.org/10.1371/journal.pone.0162289.g009
Erdos971 exhibits much similar behaviors like USAir97 as shown in Fig 8b. The intentional attacks ID, IB, RD and RB coincide in the early stage of removal () due to the strong betweenness-degree correlation in the region of high degrees as shown in Fig 9b; these attacks also deviate in the last stage of removal () in the approximate order RD > RB > IB > ID. The remarkable difference occurs in the interval , where RD prevails RB with less and less advantages and finally coincides with the latter at f ≈ 0.17, so does IB with ID. The recalculated strategies RD and RB are, as expected, more harmful than their counterparts ID and IB. Like the BA scale-free network, RD proves to be the most efficient way to harm the network’s controllability.
Edge Attack
In this subsection, we study the attack vulnerability of network controllability against various edge attacks (see Sec. III for details of the edge attack strategies). Generally speaking, the edge attacks may be not as efficient as the node attacks since after removing Ef edges (Nf nodes), the former only removes N⟨k⟩f/2 edges whereas the latter can at most remove Nf⟨k⟩ edges. It should also be noted that the study presented here is different from that of Ref. [38], in which cascading edge failure is assumed and the removal of one edge may trigger cascading removals of other edges, here we do not make such assumption and the removal of one edge does not affect other edges’ removals at all.
Fig 10 shows the numerical results of the control robustness of the ER random network subject to edge strategies. We can see that the edge strategies are indeed less efficient than those node ones: ΔnD ≈ 0.03 for the former compared with ΔnD ≈ 0.11 for the latter (compare Figs 10 and 3). The RB procedure turns out to be the most destructive strategy, even so, it is just a little bit better than RA with very slight superiority (nD(RBA) − nD(RA) ≈ 0.003). nDs of others attacks (IB, ID and RD) are even inferior to that of RA with growing gaps, indicating that these strategies are even less efficient than random failures. Moreover, we can see that the degree-based attacks, ID and RD, can hardly harm the controllability at all as evident from the almost constant nD shown in Fig 10.
[Figure omitted. See PDF.]
Fig 10. nD as a function of the removal fraction fe under different edge attacks for the ER random network.
The results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g010
These phenomena may seem difficult to understand at first glance, however, they can be explained by carefully analyzing the structural characteristics of ER. The ER random network has a short APL (∼ln N/ln⟨k⟩) due to its high proportion of shortcuts, such edges are removed by RB for their high betweenness and also have a great chance to be removed by RA. Therefore both RB and RA remove almost the same set of edges, resulting in almost the same damage to network controllability. This result may suggest that the distance measures like edge betweenness also affect the networks controllability. Given the importance of shortcuts in small-world networks, we infer that the edge betweenness-based strategies IB and RB, especially RB, will be more harmful in WS and NW. In addition, the difference between RB and IB is caused by the redistribution of edge betweenness, which is easy to understand, since as the removals proceed, the less shortcuts have to bear the same amount of shortest paths.
The degree-based attacks, ID and RD, tend to preferentially remove edges that connect two high degree nodes (Eq (10)), which will weaken the degree of hub nodes and thus increase the number of medium degree nodes, resulting in a more centralized degree distribution as confirmed in Fig 11. This implies that the more homogeneous network may contribute to the results. To confirm this observation, we define the network heterogeneity as the standard deviation of degree distribution, i.e., H = [∑(ki−⟨k⟩)2/N]1/2. We then calculate the average degree ⟨k⟩, the degree heterogeneity H and the average betweenness centrality ⟨B⟩ under different fe subject to ID attack and IB attack (as a comparison), the results are shown in Table 2. As ⟨k⟩ behaves identically for all the edge attacks, it does not require much elaboration. From Table 2, we can see that H decays with fe whereas ⟨B⟩ increases with fe for ID attack. Note that ⟨B⟩ exhibits almost the same behaviors for IB attack, which excludes the impact of ⟨B⟩ on the experimental results. In contrast, the declining speed of H for ID attack is much faster than that for IB attack, suggesting the homogeneous degree distribution is the key factor that contributes to such results. Liu et al. have pointed out that the degree heterogeneity affects network controllability and the homogeneous networks are easier to control [15]. As the degree-based attacks always make the network more homogeneous and thus easier to control (smaller nD), we infer that the two strategies are not efficient to attack the network controllability, especially for scale-free networks with biased degree structure. One thing to note is that the edge-based attacks also make ⟨k⟩ smaller, resulting in larger nD according to Eq (3), which compensates for the decrease of nD, thus nD stays almost unchanged.
[Figure omitted. See PDF.]
Fig 11. The degree distribution P(k) of the ER random network under different edge removal fraction fe subject to the ID attack.
fe = 0 denotes the initial degree distribution.
https://doi.org/10.1371/journal.pone.0162289.g011
[Figure omitted. See PDF.]
Table 2. The structural characteristics of ER random network, including average degree ⟨k⟩, degree heterogeneity H and average betweenness centrality ⟨B⟩, vary with fe subject to ID and IB attacks.
https://doi.org/10.1371/journal.pone.0162289.t002
The controllability of two small-world networks, WS and NW, again displays quite similar vulnerability against edge attacks as shown in Fig 12. nD retains almost constant in the early stage of attack ( for WS and for NW), indicating that the network controllability is almost not affected, however, after that the attacks harm the network controllability in the order RB > IB > ID ≈ RD > RA. The betweenness-based strategies prove to be the most efficient way to damage the network controllability, which lives up to our previous conjecture. The reason for this is that the shortcuts in small-world networks play an important role in forming the so-called “small world” phenomenon, which shorten the distance between nodes that would otherwise be much farther. As such, these shortcuts usually have higher edge betweenness than ordinary edges and become the prior targets of the betweenness-based attacks. The removals of such shortcuts make the network lose most resemblance to the original topology and quickly degenerate into the one dimensional regular lattice with much larger APL, making the network harder to control. The difference between RB and IB is due to the redistribution of edge betweenness information: the less shortcuts have to bear the same number of shortest paths as the removals proceed. It should be noted that though RB and IB attack the same set of shortcuts, RB is still more efficient than IB, suggesting that the distance-based measures like edge betweenness indeed affect network’s controllability.
[Figure omitted. See PDF.]
Fig 12. nD as a function of removal fraction fe subject to different edge attacks for (a) WS network and (b) NW network.
The results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g012
In contrast, the two edge degree-based attacks are much less harmful than the betweenness-based ones and just comparable to random attack as seen in Fig 12. This is mainly because the degree-based strategies make the network more homogeneous and thus easier to control as has been analyzed previously. However, the real situation is slightly different. In Fig 13, we plot the degree distribution under different fe subject to IDA for both networks, it can be seen that the peak of the curve continues to shift to left as the removal goes on, revealing that the network average degree is decreasing, while the network heterogeneity seems to be increasing judging from the more dispersed degree distribution. The more accurate numerical results in Table 3 show that the network heterogeneity, in fact, first decreases for small fe ( for WS and for NW) then increases until the end. This explains the behavior of nD: for small fe it stays constant due to the opposite effects of ⟨k⟩ and H, after that it starts to increase quickly as both factors make the network more difficult to control.
[Figure omitted. See PDF.]
Fig 13. The degree distribution under different fe subject to the ID attack for (a) WS network and (b) NW network.
https://doi.org/10.1371/journal.pone.0162289.g013
[Figure omitted. See PDF.]
Table 3. The average degree ⟨k⟩ and degree heterogeneity H under different fe subject to IDA for WS and NW network.
https://doi.org/10.1371/journal.pone.0162289.t003
Compared with the node attacks, the BA scale-free network for edge attacks exhibits strikingly different behaviors as shown in Fig 14. The random attack proves to be the most harmful strategy whereas the other attacks are far less efficient with broad range coincidence: nD for ID, RD and IB stays constant throughout the removal; nD for RB also changes little for , thereafter it starts to increase, but the growth is quite insignificant (ΔnD ≈ 0.012) compared with that of RA. Since all the strategies affect the network degree equally, the difference must result from other factors. In Fig 15, we explore the variations of related structural characteristics of the BA scale-free network as the removal procedure proceeds. It can be seen that the network heterogeneity H under the deliberate attacks decays much faster than that of RA, which is easy to understand since both the degree-based and betweenness-based strategies preferentially remove edges that connect hub nodes, which weakens the high degree nodes and makes the network become more homogeneous and thus easier to control (smaller nD), resulting in the inferior performance of the deliberate attacks compared with that of RA. The difference between RB and the other deliberate attacks can be attributed to the distance-based measures as shown in Fig 15b and 15c, where both the APL and the average betweenness centrality ⟨B⟩ for RB prevail other attacks with increasing advantages for , which also explains the sudden increase of its nD at fe ≈ 0.1.
[Figure omitted. See PDF.]
Fig 14. nD as a function of fe under different edge attacks for the BA scale-free network.
The results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g014
[Figure omitted. See PDF.]
Fig 15. The structural characteristics of BA network vary with the edge removal fraction fe.
The characteristics include (a) the degree heterogeneity H, (b) APL and (c) the average betweenness centrality ⟨B⟩.
https://doi.org/10.1371/journal.pone.0162289.g015
The two real-world networks, USAir97 and Erdos971, display again quite similar control vulnerability under edge attacks as shown in Fig 16. The degree-based strategies still have little effects on nD whereas RA continues to harm the controllability steadily as usual. The notable difference is the behaviors of two betweenness-based strategies. For USAir97, both IB and RB prevail RA with more and more advantages; while for Erdos971, the order is reversed—RA remains prevailing over IB and RB for , thereafter IB starts to damage the controllability drastically and becomes the most harmful strategy. Once again these behaviors can be mainly attributed to the distanced-based measures like betweenness centrality. Nevertheless, the behaviors cannot match any of the model networks, implying that there may be other factors contributing to the network controllability.
[Figure omitted. See PDF.]
Fig 16. nD as a function of fe subject to different edge attacks for (a) USAir97 network and (b) Erdos971 network.
The results are averaged over 100 independent realizations.
https://doi.org/10.1371/journal.pone.0162289.g016
More Results
Despite that the canonical model networks can reveal general concepts of control robustness, our ultimate goal is to understand the control robustness of real-world networks. Therefore, we further investigate the attack vulnerability of network controllability for 25 real networks subject to different node and edge attacks using the same strategies, the results are shown in Tables 4 and 5.
[Figure omitted. See PDF.]
Table 4. The node attack vulnerability of the real networks analyzed in this paper.
https://doi.org/10.1371/journal.pone.0162289.t004
[Figure omitted. See PDF.]
Table 5. The edge attack vulnerability of real networks analyzed in this paper.
https://doi.org/10.1371/journal.pone.0162289.t005
From Table 4, we can see that the regulatory networks such as the transcriptional regulatory network of Saccharomyces cerevisiae (TRN-Yeast-1 [48], TRN-Yeast-2 [49]) and Echerichia coli (TRN-EC-2 [49]) and the ownership network of US telecommunications and media corporations (Ownership-USCrop [50]) exhibit strikingly control robust under attacks: nD decreases instead of increases throughout the removal for all the five strategies, meaning that we need ever less and less driver nodes to control the whole network and the network controllability is, in fact, increasing. This phenomenon has not been observed before our work and clearly shows that the control robustness of regulatory networks are more than good enough. The other class of networks with great control robustness is the case of the intra-organizational networks [51, 52], in which nD stays constant for all five attacks, indicating that the attacking cannot affect the network controllability at all. One exception is the university network [52], which can only resist some attacks (ID, RD, RB) for small fe ≤ 10%. The control robustness of other networks can be, more or less, grasped from the model networks. The betweenness-based attacks and the degree-based attacks are almost equal harmful for the food web networks [53–55] and the metabolic networks [56]. However, for most other networks, the former are usually more harmful than the latter and so are the strategies based on recalculated information than those based on initial information. The last interesting observation is that most of the real-world networks seem to have a decreasing or constant nD for RA, indicating that the real-world networks tend to be control robust against random node failures.
In Table 5, we display the attack vulnerability of real-world networks subject to edge attacks. It can be seen that the edge degree-based attacks (both ID and RD) still cannot damage the network controllability at all as observed in the model networks, which, as has been explained, is because of the fact that such strategies make networks become more homogenous and thus easier to control. Our conclusion is that the edge degree defined as Eq (10) is not a good quantity to measure the importance of an edge in terms of network controllability. Another significant difference is the behaviors of the random edge failures. Here only the intra-organizational networks [51, 52] show good control robustness against random edge failures while other networks do not. The rest cases are very similar. In general, RB is the most harmful strategy, followed by IB, and RA is the least one. Two exceptions are the trust networks [57–59] in which IB are more efficient than RB and the metabolic networks [56] in which RA suppresses both IB and RB with slight advantage.
In summary, the real world networks display rather diverse control robust behaviors, which may suggest that one should really choose the attack strategies carefully before harming the controllability of real networks as it may affect the results to a very large extent.
Summary and Conclusions
In this paper, we have systematically investigate the attack vulnerability of network controllability for the canonical model networks as well as the real-world networks subject to five different strategies on the basis of nodes and edges. The strategies are chosen based on degree and betweenness centralities evaluated with the initial information as well as the recalculated information, among which random failure is as a comparison. We found that for node attacks, the ER random network is more control vulnerable to the degree-based attacks (RD and ID) with ΔnD ≈ 0.12 while the small-world networks (WS and NW) are more vulnerable to the betweenness-based attack (RB) with ΔnD ≈ 0.07. The BA scale-free model network with an exponential degree distribution, which is one of the most important characteristics in real-world networks [60–63], turns out to be the most vulnerable network (ΔnD ≈ 0.19) due to the existence of hub nodes and the high correlation between node degree and betweenness. The similar vulnerability is also observed in the two real-world networks, USAir97 and Erdos971. For edge attacks, the strategies are not as that efficient as the node-based ones. For example, both RD and ID can hardly harm the controllability at all for all the tested networks, and even the most harmful strategy RB only damages the ER random network with ΔnD ≈ 0.033 and the small-world networks with ΔnD ≈ 0.065. The notable difference is the BA scale-free network, which, out of our expectation, exhibits great control robustness to all the intentional attacks with almost constant nD. The two real-world networks, USAir97 and Erdos971, display complicated behaviors different from any of the model networks with ΔnD ≈ 0.09 for the former and ΔnD ≈ 0.18 for the latter, which suggests that there may be other factors contributing to the controllability.
We also investigate the control robustness of 25 real-world networks and find that the control vulnerability of real-world networks is much different from that of model networks. For example, most of the real-world networks exhibit good control robustness against random node failures, which are not observed in the model networks. The regulatory networks are even excessively robust to all the node attacks with decreasing nDs (ΔnD ≤ 0), followed by the intra-organizational networks with constant nDs (ΔnD = 0). For other networks subject to node attacks, the betweenness-based strategies are more harmful than the degree-based ones, and so are the strategies based recalculated information than their counterparts. In contrast, for edge attacks, only the intra-organizational networks are robust to random edge failures whereas other networks are harmed by the attacks in the order RB > IB > RA. In addition, we find that edge degree is not a good quantity to measure the importance of an edge in terms of network controllability.
Our results raise several questions to answer to help us better understand the attack vulnerability of network controllability. For example, we have shown that besides the degree distribution, there are other factors affecting the network controllability, what are the factors and how do they affect the controllability? Besides, the real-world networks usually have certain defence against attacks and failures, so how about the attack vulnerability of network controllability with defence?
Supporting Information
[Figure omitted. See PDF.]
S1 Table. Real networks analyzed in this paper.
https://doi.org/10.1371/journal.pone.0162289.s001
(PDF)
Acknowledgments
The authors would like to thank Prof. Tamas Vicsek and Dr. Tamas Nepusz for providing some of the network data and an anonymous referee for insightful suggestions.
Author Contributions
1. Conceived and designed the experiments: ZML XFL.
2. Performed the experiments: XFL.
3. Analyzed the data: ZML XFL.
4. Contributed reagents/materials/analysis tools: ZML XFL.
5. Wrote the paper: ZML XFL.
Citation: Lu Z-M, Li X-F (2016) Attack Vulnerability of Network Controllability. PLoS ONE 11(9): e0162289. https://doi.org/10.1371/journal.pone.0162289
1. Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’networks. nature. 1998;393(6684):440–442. pmid:9623998
2. Barabási AL, Albert R. Emergence of scaling in random networks. science. 1999;286(5439):509–512. pmid:10521342
3. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU. Complex networks: Structure and dynamics. Physics reports. 2006;424(4):175–308.
4. May RM, Lloyd AL. Infection dynamics on scale-free networks. Physical Review E. 2001;64(6):066112.
5. Moreno Y, Nekovee M, Pacheco AF. Dynamics of rumor spreading in complex networks. Physical Review E. 2004;69(6):066130.
6. Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C. Synchronization in complex networks. Physics Reports. 2008;469(3):93–153.
7. Pastor-Satorras R, Vespignani A. Epidemic dynamics and endemic states in complex networks. Physical Review E. 2001;63(6):066117.
8. Boguná M, Pastor-Satorras R. Epidemic spreading in correlated complex networks. Physical Review E. 2002;66(4):047104.
9. Motter AE, Zhou C, Kurths J. Network synchronization, diffusion, and the paradox of heterogeneity. Physical Review E. 2005;71(1):016116.
10. Motter AE, Zhou C, Kurths J. Enhancing complex-network synchronization. EPL (Europhysics Letters). 2005;69(3):334.
11. Noh JD, Rieger H. Random walks on complex networks. Physical review letters. 2004;92(11):118701. pmid:15089179
12. Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences. 2008;105(4):1118–1123.
13. Sznajd-Weron K, Sznajd J. Opinion evolution in closed community. International Journal of Modern Physics C. 2000;11(06):1157–1165.
14. Gonzalez M, Sousa A, Herrmann H. Opinion formation on a deterministic pseudo-fractal network. International journal of modern physics C. 2004;15(01):45–57.
15. Liu YY, Slotine JJ, Barabási AL. Controllability of complex networks. Nature. 2011;473(7346):167–173. pmid:21562557
16. Kalman RE. Mathematical description of linear dynamical systems. Journal of the Society for Industrial & Applied Mathematics, Series A: Control. 1963;1(2):152–192.
17. Luenberger D. Introduction to dynamic systems: theory, models, and applications. 1979;.
18. Slotine JJE, Li W, et al. Applied nonlinear control. vol. 199. Prentice-hall Englewood Cliffs, NJ; 1991.
19. Bechhoefer J. Feedback for physicists: A tutorial essay on control. Reviews of Modern Physics. 2005;77(3):783.
20. Lombardi A, Hörnquist M. Controllability analysis of networks. Physical Review E. 2007;75(5):056110.
21. Porfiri M, Fiorilli F. Experiments on node-to-node pinning control of Chua’s circuits. Physica D: Nonlinear Phenomena. 2010;239(8):454–464.
22. Shmulevich I, Dougherty ER. Probabilistic Boolean networks: the modeling and control of gene regulatory networks. siam; 2010.
23. Liu B, Chu T, Wang L, Xie G. Controllability of a leader–follower dynamic network with switching topology. Automatic Control, IEEE Transactions on. 2008;53(4):1009–1013.
24. Rahmani A, Ji M, Mesbahi M, Egerstedt M. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM Journal on Control and Optimization. 2009;48(1):162–186.
25. Lin CT. Structural controllability. Automatic Control, IEEE Transactions on. 1974;19(3):201–208.
26. Gabow HN. An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. Journal of the ACM (JACM). 1976;23(2):221–234.
27. Nepusz T, Vicsek T. Controlling edge dynamics in complex networks. Nature Physics. 2012;8(7):568–573.
28. Pósfai M, Liu YY, Slotine JJ, Barabási AL. Effect of correlations on network controllability. Scientific reports. 2013;3. pmid:23323210
29. Yan G, Ren J, Lai YC, Lai CH, Li B. Controlling complex networks: How much energy is needed? Physical review letters. 2012;108(21):218703. pmid:23003312
30. Liu Y, Slotine J, Barabási A. Control centrality and hierarchical structure in complex networks. PloS one. 2011;7(9):e44459–e44459.
31. Wang WX, Ni X, Lai YC, Grebogi C. Optimizing controllability of complex networks by minimum structural perturbations. Physical Review E. 2012;85(2):026115.
32. Yuan Z, Zhao C, Di Z, Wang WX, Lai YC. Exact controllability of complex networks. Nature communications. 2013;4.
33. Barabási AL, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A: Statistical Mechanics and its Applications. 1999;272(1):173–187.
34. Solé RV, Rosas-Casals M, Corominas-Murtra B, Valverde S. Robustness of the European power grids under intentional attack. Physical Review E. 2008;77(2):026102.
35. Holme P, Kim BJ, Yoon CN, Han SK. Attack vulnerability of complex networks. Physical Review E. 2002;65(5):056109.
36. Wang XF, Chen G. Synchronization in scale-free dynamical networks: robustness and fragility. Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on. 2002;49(1):54–62.
37. Pu CL, Pei WJ, Michaelson A. Robustness analysis of network controllability. Physica A: Statistical Mechanics and its Applications. 2012;391(18):4420–4425.
38. Nie S, Wang X, Zhang H, Li Q, Wang B. Robustness of controllability for networks based on edge-attack. PloS one. 2014;9(2):e89066. pmid:24586507
39. Motter AE, Lai YC. Cascade-based attacks on complex networks. Physical Review E. 2002;66(6):065102.
40. Tu Y. How robust is the Internet? Nature. 2000;406(6794):353–354. pmid:10935616
41. Rugh WJ. Linear system theory. vol. 2. prentice hall Upper Saddle River, NJ; 1996.
42. Erd6s P, Rényi A. On the evolution of random graphs. Publ Math Inst Hungar Acad Sci. 1960;5:17–61.
43. Hautus M. Controllability and observability conditions of linear autonomous systems. PROCEEDINGS OF THE KONINKLIJKE NEDERLANDSE AKADEMIE VAN WETENSCHAPPEN SERIES A-MATHEMATICAL SCIENCES. 1969;72(5):443.
44. Newman ME, Watts DJ. Renormalization group analysis of the small-world network model. Physics Letters A. 1999;263(4):341–346.
45. Batagelj V, Mrvar A. Pajek datasets; 2006.
46. Banerjee SJ, Roy S. Key to network controllability. arXiv preprint arXiv:12093737. 2012;.
47. Brandes U, Pich C. Centrality estimation in large networks. International Journal of Bifurcation and Chaos. 2007;17(07):2303–2318.
48. Balaji S, Babu MM, Iyer LM, Luscombe NM, Aravind L. Comprehensive analysis of combinatorial regulation using the transcriptional regulatory network of yeast. Journal of molecular biology. 2006;360(1):213–227. pmid:16762362
49. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002;298(5594):824–827. pmid:12399590
50. Norlen K, Lucas G, Gebbie M, Chuang J. EVA: Extraction, visualization and analysis of the telecommunications and media ownership network. In: Proceedings of International Telecommunications Society 14th Biennial Conference (ITS2002), Seoul Korea. Citeseer; 2002.
51. Cross R, Parker A, Christensen CM, Anthony SD, Roth EA. The hidden power of social networks. Audio-Tech Business Book Summaries, Incorporated; 2004.
52. Nepusz T, Petróczi A, Négyessy L, Bazsó F. Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E. 2008;77(1):016107.
53. Dunne JA, Williams RJ, Martinez ND. Food-web structure and network theory: the role of connectance and size. Proceedings of the National Academy of Sciences. 2002;99(20):12917–12922.
54. Martinez ND. Artifacts or attributes? Effects of resolution on the Little Rock Lake food web. Ecological Monographs. 1991; p. 367–392.
55. Christian RR, Luczkovich JJ. Organizing and understanding a winter’s seagrass foodweb network through effective trophic levels. Ecological Modelling. 1999;117(1):99–124.
56. Jeong H, Tombor B, Albert R, Oltvai ZN, Barabási AL. The large-scale organization of metabolic networks. Nature. 2000;407(6804):651–654. pmid:11034217
57. Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, et al. Superfamilies of evolved and designed networks. Science. 2004;303(5663):1538–1542. pmid:15001784
58. Van Duijn MA, Zeggelink EP, Huisman M, Stokman FN, Wasseur FW. Evolution of sociology freshmen into a friendship network. Journal of Mathematical Sociology. 2003;27(2-3):153–191.
59. Leskovec J, Huttenlocher D, Kleinberg J. Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM; 2010. p. 1361–1370.
60. Dorogovtsev SN, Mendes JF. Evolution of networks: From biological nets to the Internet and WWW. Oxford University Press; 2013.
61. Newman M, Barabasi AL, Watts DJ. The structure and dynamics of networks. Princeton University Press; 2006.
62. Caldarelli G. Scale-free networks: complex webs in nature and technology. OUP Catalogue. 2007;.
63. Albert R, Barabási AL. Statistical mechanics of complex networks. Reviews of modern physics. 2002;74(1):47.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2016 Lu, Li. This is an open access article distributed under the terms of the Creative Commons Attribution License: http://creativecommons.org/licenses/by/4.0/ (the “License”), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Abstract
Controllability of complex networks has attracted much attention, and understanding the robustness of network controllability against potential attacks and failures is of practical significance. In this paper, we systematically investigate the attack vulnerability of network controllability for the canonical model networks as well as the real-world networks subject to attacks on nodes and edges. The attack strategies are selected based on degree and betweenness centralities calculated for either the initial network or the current network during the removal, among which random failure is as a comparison. It is found that the node-based strategies are often more harmful to the network controllability than the edge-based ones, and so are the recalculated strategies than their counterparts. The Barabási-Albert scale-free model, which has a highly biased structure, proves to be the most vulnerable of the tested model networks. In contrast, the Erdős-Rényi random model, which lacks structural bias, exhibits much better robustness to both node-based and edge-based attacks. We also survey the control robustness of 25 real-world networks, and the numerical results show that most real networks are control robust to random node failures, which has not been observed in the model networks. And the recalculated betweenness-based strategy is the most efficient way to harm the controllability of real-world networks. Besides, we find that the edge degree is not a good quantity to measure the importance of an edge in terms of network controllability.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer