Skip to main content

Research Article

Enhancing Controllability Robustness of -Snapback Networks through Redirecting Edges

Yang Lou1, Lin Wang2, and Guanrong Chen1

1City University of Hong Kong, Hong Kong
2Shanghai Jiao Tong University, Shanghai 200240, China
Correspondence should be addressed to Guanrong Chen; kh.ude.uytic@nehcgee

Abstract

The well-known small-world network model was established by randomly rewiring edges, aiming to enhance the synchronizability of an undirected nearest-neighbor regular network. This paper demonstrates via extensive numerical simulations that randomly redirecting edges could enhance the robustness of the network controllability for directed snapback networks against both random and intentional node-removal and edge-removal attacks.

1. Introduction

Network science has seen rapid development since the late 1990s and has gained popularity in recent years. With the idea of randomly connecting edges between nodes developed in the classical random-graph theory [1], the small-world network model [2] was established by randomly rewiring edges, aiming to enhance the synchronizability of an undirected nearest-neighbor regular network. Thereafter, another splash was made by the proposal of a scale-free network model [3] based on randomly attaching edges with preference. This paper suggests a modified q-snapback network model by randomly redirecting edges of the original q-snapback networks [4] and further studies its robustness of the network controllability against both random and intentional node-removal and edge-removal attacks.

Recently, the network controllability has become a focal topic in network science investigation [513], where the controllability means the ability of the network in changing its state from any initial position to any targeted position under a certain control input within a finite duration of time. Meanwhile, malicious attacks on complex networks are another concerned issue in network science studies [1418]. Reportedly, intentional degree-based node attacks are more effective than random attacks on network structural controllability over directed random-graph (RG) networks and directed scale-free (SF) networks [19]. Both random and intentional edge-removal attacks have been studied by many. In [20], it was pointed out that intentional edge-removal attack by removing highly-loaded edges is very effective in reducing the network controllability. It is also observed (e.g., in [21]) that intentional edge-based attacks are usually able to trigger cascading failures in SF networks, but not necessarily in RG networks. These motivated some recent in-depth studies of the robustness of network controllability [4]. In this regard, both random and intentional attacks as well as both node-removal and edge-removal attacks were investigated. In particular, it was observed that redundant edges, which are not included in any of the maximum matchings, can be rewired or redirected so as to possibly enlarge a maximum matching such that the needed number of control driver nodes is reduced [22, 23].

The present paper continues the currently active study on the robustness of network controllability against both random and intentional attacks based on either node-removal or edge-removal strategy. In doing so, a modified q-snapback network model based on the original q-snapback networks [4] is proposed. Under the new framework, a new approach of randomly redirecting edges of the modified q-snapback network is formulated and evaluated. It is found that for all modified q-snapback networks with different numbers of redirecting edges, the one with is overall the best, which is also better than other comparable complex network models such as random-graph networks [24], multiplex congruence networks [25], random triangle networks [26], and random rectangle networks (to be formulated in this paper). By examining closely the structures of the modified q-snapback networks, it is found that they contain many 3-rings and 4-rings, which are beneficial for enhancing the robustness of the network controllability, consistent with the observation reported in [4].

The rest of the paper is organized as follows. In Section 2, some preliminaries are given, including a brief description of the q-snapback network model and the proposed strategy of redirecting edges in such a network. Section 3 reports the main experimental results of the paper, describes various attack methods, defines a robustness measure, introduces the modified q-snapback network model, and presents detailed numerical simulation results with thorough comparisons. It also discusses the effects of degree distributions on the controllability robustness. Finally, Section 4 concludes the investigation.

2. Preliminaries

2.1. The q-Snapback Network Model

Resembling to the industrial assembly-line automation, as illustrated by Figure 1, the q-snapback network (QSN) model is established based on a backbone chain, with snapback edges determined by a probability , which generates a directed network with multiring structure [4].

Figure 1

Alt text
[4] Schematic of industrial assembly-line automation, where represents a plant and a feedback controller.

Briefly, the -snapback network is constructed as follows. Start from a directed chain with nodes . Introduce a process index , and build the network with the following steps. For each node , it connects backward to the previously appeared nodes ( ), with the same probability . For , every node connects forward to node , and meanwhile, it connects backward to all previously appeared nodes , with the same probability . Then, the same process is repeated for , where it connects backward to the previously appeared nodes , with , according to the same probability uniformly. The construction continues for , until it cannot be processed any further. The resulting network is the -snapback multiplex network of size . Self-loops and multiple edges are naturally avoided in this generation method. It was shown [4] that the robustness of both state controllability and structural controllability of the -snapback network model, against targeted and random node- and edge-removal attacks, is stronger than both the multiplex congruence network [25] and the generic scale-free network [27], due to its advantageous structure with many inherent chain- and loop-motifs. This is consistent with the observation that motifs are main components of communities in complex networks of many kinds [28].

2.2. Redirecting Edges

The proposed new network model is based on edge redirecting operations, as detailed in this subsection.

Each snapback edge is reversed with a probability ( ), irrelative to the generating probability , while the edges in the backbone chain are unchanged. When , it is the original QSN [25]; when , the result is a feedforward network.

As shown by the example in Figure 2, a few loops may be destroyed by such redirecting operations, but more new loops are formed, resulting in a network with more loops in the end. As illustrated later, this is exactly the main reason why the new model has better robustness of controllability than the original QSN model. It should be noted that the edges of the backbone chain will not be affected by the redirecting operation since none of them will be redirected. Here, the probability is calculated by the number of redirected edges divided by the total number of snapback edges in the original QSN. For example, in Figure 2(a), the total number of snapback edges (black edges) is 8; when a redirecting operation with is applied, 4 (red) edges might be redirected as illustrated by Figure 2(b).

Figure 2

Alt text
An example of QSN: (a) a randomly generated QSN with 9 nodes and 16 edges ( ); (b) QSN generated with , where the 4 redirected edges are colored red. For 3-ring motifs: in (a), there are two 3-rings, namely, 1-2-3 and 7-8-9. By redirecting edges, the original local rings are destroyed, but three new 3-rings are generated, namely, 2-7-9, 3-7-9, and 6-7-9.

QSN is constructed based on a backbone chain, where the nodes directly connected in the backbone chain are considered as local connected nodes, while the nodes connected by long distance snapback edges are nonlocal. In the QSN shown in Figure 2(a), there are two local 3-rings, namely, 1-2-3 and 7-8-9. Note that in the QSN model, due to its generation mechanism, only local rings can be formed. Notably, by randomly redirecting some edges (as shown in Figure 2(b)), these two local 3-rings will be broken down, but three new 3-rings will be formed: 2-7-9, 3-7-9, and 6-7-9. Thus, by performing redirecting, not only the number of 3-rings increases from two to three, but also the diversity of motifs increases, in the sense that nonlocal motifs are formed. This gives another reason why the new model has better robustness of controllability than the original QSN model, as further discussed in Section 3.

2.3. Expected Degree of Each Node

For a single layer (the th layer, ) in a QSN, the expected outdegree (i.e., number of outgoing edges) and indegree (i.e., number of incoming edges) of each node can be calculated as follows:where represents the expected outdegree of node , and is the floor function that returns the greatest integer less than or equal to , andwhere represents the expected indegree of node .

An illustrative example of the expected outdegree and indegree, calculated by (1) and (2), respectively, and the statistical outdegree and indegree averaged from 1000 QSNs, are given in the Supplementary Information (SI). As for a multiplex QSN, the expected outdegree and indegree can be calculated, respectively, byandwhere and represent the expected outdegree and indegree of node in the multiplex QSN. Note that an edge could appear on different layers of a multiplex QSN. The probability that edge exists on at least one layer, i.e., the probability of the existence of edge , is given bywhere , satisfying , with being prime numbers, and represents the probability that edge does not exist on any layer of the multiplex network. Here, means .

3. Experimental Studies

An extensive experimental study is carried out to verify the effectiveness of the above-described edge redirecting operations in improving the robustness of network controllability. Firstly, QSN networks with different redirecting probabilities are compared. Then, the QSN generated with redirecting probability , which is the overall best-performing network among all the QSN variants, is evaluated and compared to other 4 typical network topologies.

3.1. Attack Methods

Attack methods used in simulation include node-removal and edge-removal. Node-removal attack removes the nodes one after another, until there is only one single node left. When a node is removed, all of its connected edges are removed together. In an edge-removal attack, edges are removed one after another, while no node is removed even if a node has become isolated. Thus, when the edge-removal attack is terminated, there are isolated nodes left.

A total of 6 types of attacks are performed in simulations, as are summarized in Table 1. Here, the edge-degree is calculated by taking the geometric mean of the node-degrees of the two end nodes of an edge [15]. Thus, for a directed edge , its edge-degree is , where is the indegree of node and is the outdegree of node .

Table 1

Attack methods in simulations.
Alt text

For all the intentional attacks listed in Table 1, the target (node or edge) with the largest betweenness or largest degree is updated after each node- or edge-removal. Here, as a common centrality measure in graph theory and network science, betweenness of a node or an edge is the sum of the shortest path-lengths that pass through the node or the edge.

3.2. Robustness Measure

The network controllability is measured by the density of the control-nodes , defined bywhere is the number of external controllers (also called driver nodes) needed to retain the network controllability after the network had been attacked, and is the network size. Note that does not change during an edge-removal attack, but it would be reduced by a node-removal attack. Under this measure, the smaller the is, the more robust the network controllability will be.

On the other hand, recall from computational network science that a network is considered to be sparse if the number of edges (i.e., the number of nonzero elements of the adjacency matrix) is much smaller than the possible maximum number of edges, (for a directed network, ). Practically, if , then it is considered a sparse network.

For state controllability, if the adjacency matrix of the network is sparse, the number of driver nodes can be calculated by [29]

As for structural controllability, the number of driver nodes is determined by the number of elements in the maximum matching [5]:where is the cardinal number of elements in the maximum matching . A maximum matching of a network is a matching that contains the largest possible number of edges, which cannot be further extended in the network.

For measuring the robustness of both state and structural controllabilities, the value of is calculated according to (6) and recorded after each node or edge is removed.

The quantitative measure of controllability robustness [30] is used for comparison among different network topologies. It is a comparative measure that gives a comparison rank of multiple networks, which takes into account of each node- or edge-removal through the whole process.

Since a smaller value of the density of the driver nodes represents a better network controllability, the controllabilities of the simulated networks are ranked ordinally. Then, the overall average rank is taken, denoted by , which is the quantitative and comparative measure of the robustness of the network controllability. Here, the ordinal number is taken for comparison instead of the cardinal number, because at each step when a portion of nodes or edges have been removed from the network, one can focus more on the comparison to find which network requires a smaller number of driver nodes, while ignoring precisely how many drivers nodes are needed by each network. An example of such a quantitative measure is shown in Figures 3 and 4, where 3 networks are compared.

Figure 3

Alt text
Three networks (A, B, and C) under a node-removal attack. The node-removal order for each network is based on the outdegrees, descending from large to small. When there is more than one node having the maximum outdegree, it randomly picks one among them. For networks A and B, the node-removal order is 1, 2, and 3; for network C, the order is 3, 4, and 1. The density of driver-nodes ( ), the number of nodes ( ), and the number of minimal driver-nodes needed ( ) are also presented. The corresponding comparison is shown in Figure 4.

Figure 4

Alt text
Density of driver-nodes ( ), as a function of the proportion of the removed nodes ( ). Initially, when no node has been removed ( ), both networks A and C require only 1 driver-node, while network B requires 2. When , meaning that 3 out of 4 nodes are removed, each network has only one node remaining, so the required number of driver nodes is also 1 for each network. The ordinal ranks are calculated and marked at each value, where represents the rank of network ( , or ) at step of an attack, . After averaging over all 4 points, network A has an average rank , network B has , and network C has . Here, represents the number of winnings. Network A wins the first rank for 4 values, network B wins only once when , and network C wins 3 times.

Three networks, denoted by A, B, and C, with 4 nodes and 4 edges, are shown in Figure 3. As the outdegree-based node-removal attack is performed, the remaining nodes and the required number of driver-nodes are shown in the figure. Initially, both networks A and C require only 1 driver-node, while network B requires 2. As can be seen from Figure 3(1), the maximum outdegree node in network B is node #1, while for networks A and C, every node has the same outdegree 1. Thus, the first attack is applied to node #1 in network B, while a random attack is performed on networks A and C. Since nodes are removed from network A, it always requires only 1 driver-node. For network B, the first attack breaks the network into two separated subnetworks. It should be noted that, in Figure 3C(2), it requires 2 control inputs to nodes #1 and #4. However, after node #4 is removed, it requires only 1 control input. Not only the needed number of driver-nodes is reduced, but also the density is reduced. This is also reflected by the simulation results shown in Figure 4, where the density curves show an upward trend, but it is not monotonically increasing. Finally, each network retains one and only one node, and reaches 1.

In Figure 4, the corresponding density of driver-nodes, , as a function of the proportion of the removed nodes, , is plotted. Since a smaller value of the density of the driver-nodes represents a better network controllability, at each point of , the controllabilities of the three networks are ranked ordinally, as marked in the figure. Then, the overall average rank is taken, denoted by , as a quantitative and comparative measure of the robustness of the network controllability. When two (or more) networks have the same value at a sample point , they share the same rank. For example, when , for both networks A and C, ; thus, they share the ranks 1 and 2, and the same average rank 1.5 is assigned to networks A and C, respectively.

It can be seen from Figure 4 that network A has better controllability robustness than networks B and C. However, given the many and complicated curves there, the comparison may not be clearly observed. For example, in the comparison of edge-removal attack, where the network size is 1000 and the average degree is 10, each curve has 10000 sample points to compare. Therefore, besides the average rank , the number of winning the first place is also considered, which reflects the times that the network performs the best controllability under an attack. As shown in Figure 4, network A keeps requiring the minimum number of driver-nodes, among the three networks at each sample point, and thus the value for network A is 4. A draw in the first place is also counted as a winning time. For network B, it only wins once, when , which is a draw.

The average rank and the number of winning times, , reflect two aspects of the comparison of network controllability robustness. A lower value of or a higher value of is expected for a network model with good robustness of controllability.

This quantitative measure can be scaled to a setting with any number of networks and to edge-removal attacks as well.

3.3. QSNs with Different Redirecting Probabilities

Firstly, comparison is performed among the original QSN and the QSN with reversed edges. All networks have the same size with nodes and edges. Some other network settings are also studied, with results summarized in the SI file, where the network settings include with average degree , with , and ( ), where the average degree values , , and are determined by the nature of MCN [25]. Note that (7) can be applied to sparse networks. When and , ; therefore, it is excluded from the experiments reported in SI.

Both state controllability and structural controllability are compared. Figures 611 show the curves of network controllability against the 6 different types of attacks. There are 11 networks being compared here, namely, the original QSN and the QSNs with to , with an increment of . For clarity, only the results of the original QSN and the QSNs with , , , and are presented in Figures 611.

The curves of heterogeneity and the numbers of three motifs are also plotted for reference. The heterogeneity of a network is calculated by , where represents the average degree of the network, and represents the raw second moment of the network [31].

The three counted motifs are shown in Figure 5. Empirically revealed, these three motifs are important to achieve robust network controllability [4, 30].

Figure 5

Alt text
Topologies of the three motifs counted in simulations: (a) a 3-ring motif; (b) a 4-ring motif; and (c) a 4-chain motif.

Figure 6

Alt text
Simulation results of random node-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegree ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 7

Alt text
Simulation results of betweenness-targeted node-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 8

Alt text
Simulation results of degree-targeted node-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 9

Alt text
Simulation results of random edge-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

Figure 10

Alt text
Simulation results of betweenness-targeted edge-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

Figure 11

Alt text
Simulation results of degree-targeted edge-removal attack on QSN variants: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

3.3.1. Node-Removal Attacks

Figure 6 shows the simulation results of random node-removal attacks. Comparing Figures 6(a), 6(b), 6(d), and 6(f), it can be seen that during a long period ( ), QSN with has the largest numbers of 3- and 4-rings and also has the best controllability robustness. Once the 3- and 4-rings are exhausted (around ), the controllabilities of different networks become very similar to each other. The original QSN has fewer rings, while the QSN with has no rings. All the networks have similar numbers of 4-chains, as shown in Figure 6(e), which does not distinguish the robustness of controllability in this case. The outdegree heterogeneity curves in Figure 6(c) show that the QSN with has lowest values and the original QSN and the QSN with have the highest values. Lower heterogeneity is beneficial against the random node-removal attack. When a higher-heterogeneity network is being attacked by random node removals, and when a large-degree node is removed, the controllability would decrease severely. However, in a lower-heterogeneity network, there are fewer large-degree nodes; therefore, the controllability could be maintained better than in a higher-heterogeneity one.

In summary, the QSN with performs most robustly against random node-removal attacks, followed by those with and . The original QSN and the QSN with perform very similarly to each other, and they are ranked the last two. A positive correlation between the controllability robustness and the numbers of 3- and 4-rings is clearly observed. Many 3- and 4-rings in the network help maintain a good controllability.

Figure 7 shows the simulation results of betweenness-targeted node-removal attacks. This attack method breaks the 3-rings, 4-chains, and 4-rings much faster than random node-removal. For example, under this attack, the 3- and 4-rings are exhausted in all the networks before they reach , while under a random node-removal attack, the 3- and 4-rings are not exhausted even around . Except for this, the phenomenon seen from Figure 7 is similar to that from Figure 6. Redirected edges increase the numbers of 3- and 4-rings, as well as the robustness of controllability, of these networks.

Figure 8 shows the simulation results of degree-targeted node-removal attacks. A similar phenomenon, as seen in Figure 7, can be observed; namely, the QSN with shows the best controllability robustness, which also has more motifs than other networks. Comparing Figures 7 and 8, (1) the betweenness-based node-removal attack is more harmful to the motifs, which are exhausted earlier under a betweenness-based attack than a degree-based attack; (2) after the 3- and 4-rings are exhausted, the controllabilities of different networks become similar to each other.

3.3.2. Edge-Removal Attacks

Similarly to Figures 6, 7, and 8, here Figures 9, 10, and 11 show the simulation results of random, betweenness-targeted, and degree-targeted edge-removal attacks, respectively.

Similarly to the random node-removal, the random edge-removal is not effective on destroying motifs, while the two intentional edge-removal attacks are effective, where the 3- and 4-rings can be cleaned up before reaching . When the motifs are exhausted in a network, the required density of driver-nodes, , becomes high. Consistently, the QSN with has the largest numbers of 3- and 4-rings during all the 6 attacks, and they maintain the best controllability robustness as well.

The full comparison results of the original QSN and the QSN with to , with an increment of , are summarized in Tables 2 (for exact controllability) and 3 (for structural controllability). The average rank and the number of winning times are both listed. For example, in the first cell of Table 2, the number “9.95” means the average rank ( ) of the original QSN during the entire random node-removal attack process over all 11 networks. The number below inside parentheses represents the number of winning the first place during the entire process, where the “(1)” under “9.95” means that the QSN only wins the first rank once (perhaps a draw). A low value of average rank, or a high value of winning times, means better robustness of controllability.

Table 2

Comparison of the original QSN and the QSN with redirected edges in terms of exact controllability. Average rank and number of winning rank one are listed for each network. Italic numbers represent the minimum average rank, and italic numbers inside parentheses mean the maximum number of winning times.
Alt text

Table 3

Comparison of the original QSN and the QSN with redirected edges in terms of structural controllability. Average rank and number of winning rank one are listed for each network. Italic numbers represent the minimum average rank, and italic numbers inside parentheses mean the maximum number of winning times.
Alt text

As shown in Tables 2 and 3, the minimum average ranks mostly appear around the QSN with , while the maximum ranks are bipolarly distributed in the original QSN and the QSN with . The controllability robustness becomes better as increases from (the original QSN could be considered as the QSN with ) to and then becomes worse as changes from to . Figure 12 shows the initial number of 3 motifs in each network. When , the network has the largest numbers of 3-rings, 4-rings, and 4-chains.

Figure 12

Alt text
Comparison of the initial numbers of 3 motifs (3-rings, 4-rings, and 4-chains) in the QSN with different values.

3.4. Comparison with Other Network Models

The QSN with is compared to 4 other complex network models, under the same 6 types of malicious attacks. The 4 models include random graph (RG) [1], multiplex congruence network (MCN) [25], random triangle network (RTN) [26, 32], and random rectangle network (RRN) [30]. These 4 models are compared to the original QSN in [30], where RRN shows overall best robustness of controllability. The uncomparable generic directed scale-free network is excluded in the comparison here. The generation methods of these networks are briefly introduced as follows.

For each model, possible isolated nodes, multiple edges, and self-loops, if existing in the final network, will be removed. Thus, a simple directed graph will be obtained as a result. For a fair comparison, the networks are generated with the same number of nodes and the same number of edges . Here, and (i.e., ). An extensive comparison of the 5 networks is given in SI, where the parameters are set to with , with , and with .

3.4.1. Random-Graph Networks

A directed RG network is generated as follows:

(1)

Start with isolated nodes.

(2)

Pick up all possible pairs of nodes, denoted by and ( , ), once and once only, from the nodes, and connect each pair of nodes by a directed edge with probability . The edge is with an even probability 0.5 to be directed from to or from to .

Statistically, the expectation of the number of edges of an RG network is . To precisely control the number of edges , if necessary, uniformly at random adding or removing edges is performed where, when adding an edge, the direction can be random.

3.4.2. Multiplex Congruence Networks

Each node in an MCN is marked by an index . The congruence relation of the node indices is applied to generate edges in the MCN. Given a congruence value , the MCN is generated as follows:

(1)

Start with isolated nodes.

(2)

A directed edge is added if .

This generates a layer (the th layer) in the multiplex. The degree distribution of each layer follows a power-law form. There is no pattern in the MCN, and its topology is determined by the two parameters and .

3.4.3. Random Triangle Networks

Based on the observations that a multiring structure benefits the robustness of controllability [4] and the network stability [33, 34] and that the triangular structure is frequently encountered in real-life situations, a directed RTN is designed here for comparison study of the network controllability robustness, as follows:

(1)

Start with isolated nodes, with the other 3 nodes linked in as directed ring.

(2)

Randomly pick up two nodes, and , without edge or in between. Then, randomly pick up a node from the neighbors of node . If there is an edge , then add two edges and ; otherwise, add two edges and .

(3)

Repeat Step (2), until edges have been added.

3.4.4. Random Rectangle Networks

The above directed RTN is extended to an RRT, as follows:

(1)

Start with isolated nodes, and the other 4 nodes are linked as a directed ring.

(2)

Randomly pick up three nodes, , , and , without edges between any pair of them. Then, randomly pick up a node from the neighbors of node . If there is an edge , then add edges , , and ; otherwise (with an edge ), add edges , , and .

(3)

Repeat Step (2), until edges have been added.

Since, at each time step, two edges are added to RTN, and three edges are added to RRN; uniform at random adding or removing edges can be performed to control the number of edges precisely.

3.4.5. Simulation Results

Figures 1318 show a comparison of the 5 networks. From these figures, some common features can be observed: (1) RTN has the largest number of 3-rings, since it is based on triangles; (2) RRN has the largest number of 4-rings, since it is based on rectangles; and (3) MCN has the largest value of , which is the only topology with power-law degree distribution in this comparison.

Figure 13

Alt text
Simulation results of random node-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 14

Alt text
Simulation results of betweenness-targeted node-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 15

Alt text
Simulation results of degree-targeted node-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed nodes in the network.

Figure 16

Alt text
Simulation results of random edge-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

Figure 17

Alt text
Simulation results of betweenness-targeted edge-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

Figure 18

Alt text
Simulation results of degree-targeted edge-removal attack on the 5 networks: (a) exact controllability (EC); (b) structural controllability (SC); (c) heterogeneity of outdegrees ( ); (d) number of 3-rings; (e) number of 4-chains; and (f) number of 4-rings. represents the proportion of the removed edges in the network.

As can be seen from Figures 13, 14, and 15, QSN with clearly outperforms the other 4 topologies against the node-removal attacks.

It can be seen from Figures 16, 17, and 18 that the QSN with clearly outperforms the other 4 topologies against node-removal attacks.

Figure 16 shows the simulation results of the 5 networks against random node-removal attacks. The QSN with clearly outperforms RG, RTN, and MCN and has similar performance comparable to RRN. RRN has better controllability when is near but less than ; after that, the performances are undistinguishable. Quantitatively, according to Tables 4 and 5, the QSN with outperforms RRN in both the average rank and the number of winning times.

Table 4

Comparison of robustness of exact controllability among 5 networks. Average rank and number of winning rank one are listed for each network. Italic numbers represent the minimum average rank, and italic numbers inside parentheses mean the maximum number of winning times.
Alt text

Table 5

Comparison of robustness of structural controllability among 5 networks. Average rank and number of winning rank one are listed for each network. Italic numbers represent the minimum average rank, and italic numbers inside parentheses mean the maximum number of winning times.
Alt text

In Figures 17 and 18, the QSN with is clearly ranked at the third place among the 5 network topologies. Both RRN and RTN perform better than the QSN with , under both betweenness-targeted and degree-targeted edge-removal attacks.

Tables 4 and 5 show the average ranks and the number of winning times in the comparison among the 5 networks. Overall, the QSN with gains the lowest average rank. RRN has the maximum number of winning times, due to its strong performance against the betweenness-targeted and degree-targeted edge-removal attacks.

3.5. Effects of Degree Distributions

Finally, the effect of a degree distribution on the robustness of network controllability is briefly discussed.

Figure 19 shows the degree distributions of the QSN variants. Together with these distributions, the relationships between the numbers of motifs (mainly, 3- and 4-rings and 4-chains) and the controllability robustness are observed, as summarized below:

(1)

If the degree distribution of the QSN (or a variant) network is not uniform but Poisson, then the numbers of 3- and 4-rings are positively correlated to the controllability robustness: the more rings, the better controllability robustness.

(2)

If the degree distribution of the QSN (or a variant) network is uniform (only for the original QSN and the QSN with ), the existence of many rings in the original QSN and the absence of rings in the QSN with do not affect the controllability robustness.

Figure 19

Alt text
Degree distributions of the QSN with different values. The original QSN and the QSN with have a uniform outdegree distribution, while the QSN with , , and has a Poisson-like outdegree distribution.

The extensive comparison results presented in SI confirms that the existence of many 3- and 4-rings in the QSN with improves the robustness of the controllability, when both network size and average degree are changed.

4. Conclusions

Inspired by the idea of small-world network model, which was formed by randomly rewiring edges, aiming to enhance the synchronizability of an undirected nearest-neighbor regular network, this paper proposed a new network model by randomly redirecting edges, aiming to enhance the controllability robustness of a directed snapback network against both random and intentional node-removal and edge-removal attacks. Through extensive numerical simulations, it was found that the modified q-snapback network, with statistically one-half of the feedforward edges being redirected, is overall better than other variants, and also better than comparable random networks, multiplex congruence networks, random triangle networks, and random rectangle networks, against various attacks. It was found that there are many 3-rings and 4-rings in the modified q-snapback networks, which seems to be the main reason that make such networks strong in resisting malicious attacks. The advantageous role of ring motifs in complex networks remains to be further understood in future studies towards more and better technical network applications.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Supplementary Materials

Supplemental information includes 32 tables and 97 figures can be found with this article online. (Supplementary Materials)

References

  1. P. Erdős and A. Rényi, “On the strength of connectedness of a random graph,” Acta Mathematica Hungarica, vol. 12, no. 1-2, pp. 261–267, 1964. View at Publisher · View at Google Scholar
  2. D. J. Watts and S. H. Strogatz, “Collective dynamics of 'small-world' networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. View at Publisher · View at MathSciNet · View at Google Scholar
  3. A. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. View at Publisher · View at MathSciNet · View at Scopus · View at Google Scholar
  4. Y. Lou, L. Wang, and G. Chen, “Toward stronger robustness of network controllability: a snapback network model,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, no. 9, pp. 2983–2991, 2018. View at Publisher · View at Google Scholar
  5. Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks,” Nature, vol. 473, no. 7346, pp. 167–173, 2011. View at Publisher · View at Scopus · View at Google Scholar
  6. A. E. Motter, “Networkcontrology,” Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 25, no. 9, Article ID 097621, 2015. View at Publisher · View at Google Scholar
  7. Y.-Y. Liu and A.-L. Barabási, “Control principles of complex networks,” Reviews of Modern Physics, vol. 88, Article ID 035006, 2016. View at Google Scholar
  8. L. Wang, X. Wang, G. Chen, and W. K. Tang, “Controllability of networked MIMO systems,” Automatica, vol. 69, pp. 405–409, 2016. View at Publisher · View at Google Scholar
  9. L. Wang, X. Wang, and G. Chen, “Controllability of networked higher-dimensional systems with one-dimensional communication,” Philosophical Transactions of the Royal Society A: Mathematical, Physical & Engineering Sciences, vol. 375, no. 2088, Article ID 20160215, 2017. View at Publisher · View at Google Scholar
  10. L. Z. Wang, Y. Z. Chen, W.-X. Wang, and Y.-C. Lai, “Physical controllability of complex networks,” Scientific Reports, vol. 7, Article ID 40197, 2017. View at Google Scholar
  11. Y. Zhang and T. Zhou, “Controllability analysis for a networked dynamic system with autonomous subsystems,” IEEE Transactions on Automatic Control, vol. 62, no. 7, pp. 3408–3415, 2017. View at Publisher · View at Google Scholar
  12. Y. Hao, Z. Duan, and G. Chen, “Further on the controllability of networked MIMO LTI systems,” International Journal of Robust and Nonlinear Control, vol. 28, no. 5, pp. 1778–1788, 2018. View at Publisher · View at Google Scholar
  13. Y. Hao, Z. Duan, G. Chen, and F. Wu, “New controllability conditions for networked identical LTI systems,” IEEE Transactions on Automatic Control, vol. PP(99), no. 1-1, 2019. View at Publisher · View at Google Scholar
  14. Y.-D. Xiao, S.-Y. Lao, L.-L. Hou, and L. Bai, “Optimization of robustness of network controllability against malicious attacks,” Chinese Physics B, vol. 23, no. 11, Article ID 118902, 2014. View at Google Scholar
  15. P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, “Attack vulnerability of complex networks,” Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, vol. 65, no. 5, part 2, Article ID 056109, 2002. View at Publisher · View at Scopus · View at Google Scholar
  16. B. Shargel, H. Sayama, I. R. Epstein, and Y. Bar-Yam, “Optimization of robustness and connectivity in complex networks,” Physical Review Letters, vol. 90, no. 6, Article ID 068701, 2003. View at Scopus · View at Google Scholar
  17. C. M. Schneider, A. A. Moreira, J. S. Andrade Jr., S. Havlin, and H. J. Herrmann, “Mitigation of malicious attacks on networks,” Proceedings of the National Acadamy of Sciences of the United States of America, vol. 108, no. 10, pp. 3838–3841, 2011. View at Publisher · View at Scopus · View at Google Scholar
  18. A. Bashan, Y. Berezin, S. V. Buldyrev, and S. Havlin, “The extreme vulnerability of interdependent spatially embedded networks,” Nature Physics, vol. 9, no. 10, pp. 667–672, 2013. View at Publisher · View at Scopus · View at Google Scholar
  19. C.-L. Pu, W.-J. Pei, and A. Michaelson, “Robustness analysis of network controllability,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 18, pp. 4420–4425, 2012. View at Publisher · View at Scopus · View at Google Scholar
  20. S. Nie, X. Wang, H. Zhang, Q. Li, B. Wang, and S. Hayasaka, “Robustness of controllability for networks based on edge-attack,” PLoS ONE, vol. 9, no. 2, Article ID e89066, 2014. View at Publisher · View at Google Scholar
  21. S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, “Catastrophic cascade of failures in interdependent networks,” Nature, vol. 464, no. 7291, pp. 1025–1028, 2010. View at Publisher · View at Scopus · View at Google Scholar
  22. J. Xu, J. Wang, H. Zhao, and S. Jia, “Improving controllability of complex networks by rewiring links regularly,” in Proceedings of the 26th Chinese Control and Decision Conference, CCDC '14, pp. 642–645, China, 2014. View at Scopus
  23. L. Hou, S. Lao, B. Jiang, and L. Bai, “Enhancing complex network controllability by rewiring links,” in Proceedings of the International Conference on Intelligent System Design and Engineering Applications (ISDEA '13), pp. 709–711, IEEE, 2013.
  24. P. Erdös and A. Rényi, “On the evolution of random graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 5, pp. 17–61, 1960. View at MathSciNet · View at Google Scholar
  25. X.-Y. Yan, W.-X. Wang, G. Chen, and D.-H. Shi, “Multiplex congruence network of natural numbers,” Scientific Reports, vol. 6, Article ID 23714, 2016. View at Google Scholar
  26. D. Yang, T. W. S. Chow, Y. Zhang, and G. Chen, “An exponential triangle model for the Facebook network based on big data,” in Proceedings of the 15th IEEE International Conference on Industrial Informatics, INDIN '17, pp. 992–996, IEEE, 2017. View at Scopus
  27. G. Chen, X. F. Wang, and X. Li, Fundamentals of Complex Networks: Models, Structures and Dynamics, John Wiley & Sons, 2nd edition, 2014.
  28. M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Acadamy of Sciences of the United States of America, vol. 103, no. 23, pp. 8577–8582, 2006. View at Publisher · View at Scopus · View at Google Scholar
  29. Z. Z. Yuan, C. Zhao, Z. R. Di, W.-X. Wang, and Y.-C. Lai, “Exact controllability of complex networks,” Nature Communications, vol. 4, article 2447, 2013. View at Google Scholar
  30. G. Chen, Y. Lou, and L. Wang, “A comparative study on controllability robustness of complex networks,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 66, no. 5, pp. 828–832, 2019. View at Google Scholar
  31. G. Yan, N. D. Martinez, and Y. Liu, “Degree heterogeneity and stability of ecological networks,” Journal of the Royal Society Interface, vol. 14, no. 131, p. 20170189, 2017. View at Publisher · View at Google Scholar
  32. C. Lu, M. Xie, M. C. Wendl et al., “Patterns and functional implications of rare germline variants across 12 cancer types,” Nature Communications, vol. 6, Article ID 10086, 2015. View at Publisher · View at Scopus · View at Google Scholar
  33. P. Schultz, J. Heitzig, and J. Kurths, “Detours around basin stability in power networks,” New Journal of Physics , vol. 16, 2014. View at Scopus · View at Google Scholar
  34. J. Nitzbon, P. Schultz, J. Heitzig, J. Kurths, and F. Hellmann, “Deciphering the imprint of topology on nonlinear dynamical network stability,” New Journal of Physics , vol. 19, no. 3, 2017. View at Scopus · View at Google Scholar

Copyright © 2019 Yang Lou et al. Exclusive Licensee Science and Technology Review Publishing House. Distributed under a Creative Commons Attribution License (CC BY 4.0).

  • Views 423
  • Citations 0
Altmetric Attention Score
Find out more