Prediction of damage results of complex network under grey information attack

Abstract

In this paper, the prediction of damage results for complex network is considered under grey information attack. Firstly, in order to construct more realistic networks, a new algorithm is proposed to generate 3 types of fully connected networks (normal scale-free network, scale-free network with cutoff, random network). Secondly, robustness of the 3 networks is analyzed under grey information attack. And then, a new method is proposed to predict the damage results by training the BP neural network. Thirdly, the effects of different topological parameters on the damage results are analyzed and a new method is proposed to find central nodes of the network. Finally, the damage results of a real bus network under grey information attack are predicted by the proposed method and several suggestions are given to help protect the real bus network.

Keywords

Complex network damage result prediction BP neural network grey information attack urban bus network

1 Introduction

Nowadays, we are in a world consisting of various networks, the stability and robustness of these networks are becoming paramount and interesting in science and engineering when networks are under attacked. Ref. [1] shows the huge differences in robustness between intentional attack and random attack. Ref. [2 –4] resolves the size of giant component and value of critical removal fraction using generating function method based on percolation theory. Ref. [5] studies the North American power grid in view of network and analyzes its invulnerability.

In general, most attack strategies are the random attacks or intentional attacks. If the attackers know nothing about the network topology, they used to randomly attack a number of nodes or edges. If the attackers master the network topology information accurately, they can choose certain nodes or edges as their targets. While, for real networks, the information attackers knew maybe not precise or complete, based on this idea, grey information attacks were proposed. That is grey information attacks happen when attackers know something but not everything about network topology. The intentional attacks and the random attacks are two special ways for grey information attacks, so they should be mainly considered. Ref. [6, 7] study the robustness of the network with grey information attack and find that different information precision for attacking networks will lead to different damage results of the networks. Based on Ref. [6 –8] proposes a new grey information attack strategy, which provides insight into the investigation of attack and defense strategies of complex networks. Although great efforts have been devoted to analyzing the network robustness under grey information attacks, there are still some open problems: How will the network change with different information precision for attacking networks? Can we predict the damage results of the network based on the experience under grey information attack?

As one of the hot fields in complex network, prediction problems attracted widespread attention recently. One of the prediction methods uses the known information to predict the unknown information. The other uses the past data to predict the future trends of the network and most of the predictions focus on network evolution [9] and link prediction [10]. Ref. [11] predicts the topology of the network by proposing an evolving network model. Ref. [12] studies a variety of techniques for link prediction in social network. Ref. [13] considers the link prediction for evolution process of different networks including brain network, protein network, ecological network and social network. In addition, Ref. [14] predicts the network security situation based on the defined parameter of the network security. However, the predictions for network robustness are less concerned. In fact, when some nodes break down, prediction provides a fast way to evaluate the final damage results of the network and can even avoid further damage by promoting assistances. Furthermore, in order to reduce the conceivable attack damages, the designers can find the key stations by prediction then make a more robust design for these key nodes. Ref. [15] makes predictions for the scale-free network under random attack, and the relative size of the giant component is predicted. However, one parameter is not enough to evaluate the network robustness, it is necessary to take more measure parameters to represent various impacts on the network.

Considering the prediction of complex network robustness, it is necessary to construct more realistic network models. In earlier researches, compared with regular networks, random networks represent the real networks better. However, recent studies find that most of these real networks are not completely random. These networks have scale-free property and high network connectivity. Ref. [16] proposes a network growing algorithm with preferential attachment to generate fully connected networks, but the degree distribution of the generated networks should always obey power law form with the exponent 3. According to the weight assigned to each node, Ref. [17] adds edges in the network to generate scale-free network with changeable exponent. However, the generated networks may not be fully connected and do not have the other non-power-law characteristics as well.

In this paper, based on grey information attack, damage result predictions for different types of network are considered. The contributions of this paper are threefold. Firstly, in order to represent the connectivity of real networks, a method to generate fully connected networks randomly is proposed. Comparing with the previous work [16, 17], the proposed method can generate networks with different degree distribution. Secondly, robustness of 3 types of network under grey information attack is analyzed and a new method is developed to predict the damage results based on the simulation results. Finally, a new method to find the central nodes in a network is provided. In addition, several suggestions are given to the city planners which will help them to protect the real bus network.

2 Complex network model under grey information attack

2.1 Generation of fully connected network

In order to construct more realistic networks, random network and scale-free network are considered in this paper. Most network generation algorithms can only generate scale-free network with fixed exponent or non-fully connected network [16 –21]. For normal scale free network, the degree distribution is described by P (k) ∼ k^−γ, here P (k) is the probability that nodes with degree k exist, γ is the exponent of the scale-free network. However, it shows that nodes with large degree in many networks are cost-prohibitive [22]. So the degree distributions of these networks are described by P (k) ∼ k^−γe^−(k/-κ), here κ is the cutoff. When k is greater than κ, it becomes very costly to add edges between nodes [22]. So, from Ref. [23], we randomly get two degree sequences subject to two different degree distributions respectively. For normal scale free network, the degree of node v can be calculated by $k_{v} = k_{min} (1 - x)^{- 1 / - (γ - 1)}$ (1) where k_min ⩽ k_v < N − 1, N is the number of nodes, k_min is the minimum degree, x is the random variable in the range of [0, 1) subjects to a uniform distribution. For the scale-free network with cutoff, the degree of node v can be calculated by $k_{v} = k_{min} - κ ln (1 - x)$ (2)

and the probability that accepts the generated k_v is p = (k_v/ − k_min) ^−γ.

Fig.1

Flow chart to generate fully connected network.

Through configuration model (CM) [24], the method by which randomly generate the network with given degree sequences is shown in Fig. 1 and the detailed explanations for each step is as follows.

Step 1. Generate a network contains N separate nodes, and then generate the degree k_v of each node by Equations (1 or 2).

Step 2. Build a set M contains stubs of all nodes in degree sequences, then randomly choose two stubs in M which belong to nodes i and j respectively. If the two stubs belong to the same nodes, then i = j. Generate edges between i and j, then delete the two stubs from M.

Step 3. Choose one loop or multiple edges e₁ (v₁, w₁) in the generated network, where v₁ and w₁ are the endpoints of edge e₁ and if v₁ = w₁, e₁ is a loop. Then randomly choose another edge e₂ (v₂, w₂), where v₂ and w₂ are the endpoints of edge e₂. By Monte Carlo switching step, the endpoints of e₁ and e₂ are exchanged to generate two new edges e₃ (v₁, w₂) and e₄ (v₂, w₁), judge whether the new edges are loops or multiple edges, and if so, cancel the previous Monte Carlo switching step.

Step 4. Randomly choose two nodes v₁ and v₂ from the generated network, verify whether they are in the same connected component, if not, check the number of neighbors of v₁ and v₂. If the number of neighbors of v₁ and v₂ are both equal to 1, edge swap cannot connect these two connected components and two nodes need to be chosen randomly again. Otherwise, randomly choose one of the neighbors of v₁ and v₂ respectively, referred to as w₁ and w₂. By Monte Carlo switching step, endpoints of e₁ and e₂ are exchanged to generate two new edges.

Step 5. In order to generate a more random network, we will continue to swap edges by Monte Carlo switching step randomly, then verify whether the network is fully connected, if not, cancel the switching. Repeat this step C · N times, here C is an integer greater than 1 [25].

For random network, because of its uniform distribution of the degree, with the same average degree, the connectivity of the random network is worse than the scale free network. When the original network with small average degree is randomly generated through CM, random edge swap cannot make the original network fully connected. So a random network with large average degree is generated by randomly adding W edges between N nodes, where W = k · N, k is the average degree of the network. The new generated network does not have loops or multiple edges and connects well, then verify if the generated network is fully connected, if not, regenerate the network until it becomes fully connected.

2.2 Fully connected network under grey information attack

For grey information attack, observed value and information precision mastered by attackers are crucial. In this paper, observed value means the degree of nodes mastered by attackers, whose accuracy depends on the information precision. In undirected connected network G = (V, E), V is the node set, E is the edge set. The real degree and the observed degree of node v are d_v and ${\tilde{d}}_{v}$ , d_min and d_max are the minimum and maximum value of degree respectively. Considering the method in Ref. [7], ${\tilde{d}}_{v}$ is assumed as a random variable follows uniform distribution in the region [d_v − (d_v − d_min) (1 − α), d_v + (d_max − d_v) (1 − α)], so ${\tilde{d}}_{v}$ is formalized as

$\begin{matrix} {\tilde{d}}_{v} = [d_{v} - (d_{v} - d_{min}) (1 - α)] (1 - δ) \\ + [d_{v} + (d_{max} - d_{v}) (1 - α)] δ \end{matrix}$ (3)

where δ is a uniform distribution variable in the interval [0, 1], α ∈ [0, 1] is the information precision. When α = 0, ${\tilde{d}}_{v} = (d_{max} - d_{min}) δ$ , which means ${\tilde{d}}_{v}$ is a random variable with a uniform distribution in the region [d_min, d_max], attack strategy is the same as the random attack. When α = 1, ${\tilde{d}}_{v} = d_{v}$ , which means the observed degree value equals to the real value, it is the same as the intentional attack. So, the random attack and intentional attack are two special cases for grey information attack.

3 Analysis and prediction for the network under grey information attack

3.1 Analysis of network robustness

For the 3 generated fully connected networks (normal scale-free network, scale-free network with cutoff and random network), nodes of the 3 networks according to the observed degree value and deduce the damage results of the network in different attack strategies (random attack, intentional attack and grey information attack). 3 parameters are selected to measure the network robustness.

(1) Relative size of the giant component S is defined as: $S = N^{'} / - N$ (4) where N is the number of nodes in initial network, N′ is the number of nodes in the giant component after the network has been attacked.

(2) The average path length of the giant component L is defined as $L = \frac{2}{N^{'} (N^{'} - 1)} \sum_{i \neq j} d'_{i j}$ (5) where $d'_{i j}$ is the shortest distance between nodes i and j in the giant component.

(3) Network performance parameter E is defined as $E = \frac{1}{N (N - 1)} \sum_{i \neq j} 1 / d_{i j}$ (6)

where d_ij is the shortest distance between nodes i and j in the initial network. Furthermore, following the idea in [26], an overall parameter to measure the network robustness is proposed by combing the above three parameters linearly, $T = a \times \frac{S^{'}}{S} + b \times \frac{L}{L^{'}} \times {(\frac{S^{'}}{S})}^{2} + c \times \frac{E^{'}}{E}$ (7) where S′, L′ and E′ represent the relative size of the giant component, the average path length of the giant component and the network performance parameter respectively. a, b and c are their weights. The change of network connectivity can be measured by the change of relative size of giant component S′/ − S, network connectivity is the most important property after the network has been damaged, so a is set as 0.5 in this paper. Since the change of network topology can be measured by the change of distance, the change of topology in the giant component can be calculated by L/ − L′. Meanwhile the change of the whole network topology can be measured by E′/E. The weight b and c are set as 0.3 and 0.2 respectively. Finally, the relative size of the giant component has more impacts on the average path length, so we multiply L/L′ by the square of (S′/S).

Next, several simulations are given to analyze the robustness of 3 types of networks. There are 1000 nodes in each network. Most of the real networks obey power law form with the exponent between interval [2, 3]. Therefore, the exponent of both normal scale-free network and scale-free network with cutoff is chosen as 2.5. Based on grey information, different proportions of nodes are attacked intentionally according to the decreasing order of degree and record average results of 200 simulations.

Figure 2 shows the change of robustness measurement parameters in scale-free network under grey information attack. f represents the proportion of broken nodes when the network is attacked. As shown in Fig. 2(a) and (c), nodes with larger degree tend to fail with an increasing α, and the damage results of the network become more serious. When α = 1, the nodes will be broken down sequentially according to the decreasing order of degree. In this case, when 10% of the nodes are broken down, network collapses completely. When α = 0, it means that attacks happen randomly, when f = 10%, S and L change a little, which indicates f influence the network weakly at this time. However, in Fig. 2(b), L increases at first except the case α = 1, that indicates f have greater impact on network topology than network connectivity initially. When L reaches to its peak, f have the strongest impacts on network connectivity. For α = 1, L decreases all the time, it means nodes with larger degree have a significant impact on both network connectivity and network topology.

Fig.2

Change of robustness measurement parameters in scale-free network under grey information attack. (a) S. (b) L. (c) E. (d) T.

Fig.3

Change of robustness measurement parameters in scale-free network with cutoff under grey information attack. (a) S. (b) L. (c) E. (d) T.

Figure 3 shows the change of robustness measurement parameters in scale-free network with cutoff. As shown in Fig. 3(a–d), when α = 1, the parameters are consistent with normal scale-free network. But when α ≠ 1, damage results of scale-free network with cutoff are always heavier than normal scale-free network. This is because comparing with normal scale-free network, scale-free network with cutoff has fewer nodes with large degree, which indicates for scale-free network, the more nodes with large degree there are, the more robust the network is under non-intentional attack. Furthermore, different from normal scale-free network, in scale-free network with cutoff, when α > 0.6, the change of parameters under grey information attack is similar to intentional attack. This is because when the maximum degree of network is small, by Equation (3), bigger α causes smaller random distribution range of ${\tilde{d}}_{v}$ which is closer to d_v. It is almost the same to use the observed value as the real degree value to attack the network.

As shown in Fig. 4(a–d), for each α, robustness measurement parameters change a little. Particularly in Fig. 4(b), when α = 1, L does not decline directly, but rises at first and declines after reaching its peak. It indicates that, in random network, the degree distribution of nodes is more uniform, and there are not any nodes with particular large degree which can influence network robustness remarkably.

Fig.4

Change of robustness measure parameters in random network under grey information attack. (a) S. (b) L. (c) E. (d) T.

Under grey information attack, there is significant difference between scale-free network and random network. For scale-free network, if there are more nodes with large degree, the damage results will be lightened. For random network, there is not any node with large degree.

3.2 Prediction of damage results using neural network

Neural networks can approach any non-linear function by training. So in this paper, we will use BP neural network to predict the damage results. In input layer, 25 parameters which can reflect the number and topology of broken nodes are considered as inputs. They are showed in Table 1. 3 parameters which can reflect damage results of the network are used as the outputs. They are S, L and E. The number of middle layer neurons is determined by the following formula.

$N_{hid} = \sqrt{N_{in} \cdot (N_{out} + 1) + 1}$ (8) where N_in, N_out is the number of input layer neurons, output layer neurons respectively. N_hid = 10 by calculating. S-function is used as the transfer function from input layer to middle layer and the linear function is used as the transfer function from middle layer to output layer. Meanwhile, Levenberg— Marquardt algorithm is used to learn the iterative process in BP neural network prediction model.

The data of simulation results in Subsection 3.1 is used to train the neural network. The nonlinear relationship of each network can be gotten by training the corresponding network. The 25 input parameters are normalized with the following formula. $X_{ij} = {\begin{matrix} 0 (X_{i min} = X_{i max}) \\ X_{i} = \frac{2 \times (X_{ij} - X_{i min})}{(X_{i max} - X_{i min})} - 1 (X_{i min} \neq X_{i max}) \end{matrix}$ (9) where X_ij is the value of ith parameters belonging to the jth training data, X_imin, X_imax represents the minimum and maximum value of ith parameter respectively. When X_imin equals to X_imax, the parameter changes a little, and the data is assigned a value of 0. At the same time, this parameter does not affect prediction, therefore it will be removed the input parameters. After training, through the anti-normalization process, we will compare the real value with predicted value under grey information attack. And the average relative error which reflects the prediction accuracy is calculated by the error formula. $Er = \frac{\sqrt{\frac{1}{m} \sum_{i = 1}^{m} (y_{i} - {\hat{y}}_{i})^{2}}}{\sqrt{\frac{1}{m} \sum_{i = 1}^{m} y_{i}^{2}}}$ (10) $Acc = 1 - Er$ (11)

Table 1

Weight contribution rate of topological parameters of broken nodes in different network (%)

Input parameters	Normal scale-free network				Scale-free network with cutoff				Random network
	S	L	E	T (rank)	S	L	E	T (rank)	S	L	E	T (rank)
Number of broken nodes	1.52	1.08	1.30	1.15(9)	10.40	3.21	18.01	10.60(5)	28.10	37.66	15.90	18.82(1)
Degree maximum	1.93	2.12	2.17	1.62(7)	1.53	0.94	2.15	1.41(7)	1.83	0.94	3.09	1.84(15)
Degree minimum	0.27	0.21	0.30	0.23(18)	0.68	0.48	0.92	0.62(20)	1.94	0.79	3.01	1.87(14)
Average degree	34.99	33.37	33.79	27.63(1)	18.47	23.42	14.19	13.49(1)	21.80	28.28	10.26	13.98(2)
Degree variance	23.27	21.27	19.41	17.46(3)	16.77	23.81	9.60	11.27(4)	4.57	2.20	8.33	4.79(4)
Median degree	0.92	1.42	1.29	0.85(11)	1.30	0.86	1.75	1.17(14)	2.19	1.98	3.17	2.04(13)
Mode degree	0.67	0.9	1.03	0.64(13)	1.09	0.94	1.33	0.94(18)	0.91	0.73	1.20	0.81(20)
Clustering coefficient maximum	0.11	0	0.11	0.08(22)	0.22	0.13	0.29	0.20(21)	1.17	0.91	1.56	1.05(18)
Clustering coefficient minimum	0	0	0	0(−)	0	0	0	0(−)	0	0	0	0(−)
Average clustering coefficient	1.14	1.77	1.63	1.06(10)	1.44	0.99	1.91	1.29(11)	1.58	1.28	2.03	1.40(17)
Clustering coefficient variance	0.81	1.06	1.00	0.71(12)	1.39	0.94	1.84	1.25(13)	2.49	1.36	4.05	2.46(9)
Median clustering coefficient	0	0	0	0(−)	0	0	0	0(−)	3.94	1.15	7.79	4.31(6)
Mode clustering coefficient	0	0	0	0(−)	0	0	0	0(−)	0	0	0	0(−)
Coreness maximum	0.49	0.68	0.69	0.46(15)	0	0	0	0(−)	0	0	0	0(−)
Coreness minimum	0.28	0.23	0.36	0.25(17)	1.04	0.84	1.24	0.89(19)	0.86	0.58	1.32	0.82(19)
Average coreness	0.71	0.87	0.85	0.61(14)	1.47	1.05	1.76	1.26(12)	6.34	7.89	4.27	4.45(5)
Coreness variance	0.26	0.17	0.25	0.20(20)	1.55	0.99	2.12	1.41(8)	2.99	3.43	2.54	2.26(11)
Median coreness	0.14	0.11	0.19	0.13(21)	1.21	0.79	1.73	1.12(15)	0	0	0	0(−)
Mode coreness	0.27	0.23	0.25	0.21(19)	1.37	0.70	2.10	1.32(10)	0	0	0	0(−)
Betweenness maximum	2.01	2.05	2.10	1.64(6)	1.41	0.75	2.06	1.32(9)	1.82	1.12	2.85	1.77(16)
Betweenness minimum	1.80	1.97	1.81	1.44(8)	3.85	4.92	3.39	2.94(6)	3.78	1.35	7.46	4.13(7)
Average betweenness	1.68	1.98	3.39	1.86(5)	14.45	11.77	16.51	12.18(3)	5.10	1.27	9.82	5.49(3)
Betweenness variance	23.9	24.23	24.34	19.25(2)	18.07	20.79	14.21	13.30(2)	3.92	3.54	4.19	3.22(8)
Median betweenness	2.49	3.82	3.38	2.26(4)	1.11	0.79	1.37	0.97(17)	2.28	2.16	3.15	2.09(12)
Mode betweenness	0.33	0.27	0.36	0.27(16)	1.17	0.83	1.53	1.05(16)	2.38	1.37	4.02	2.40(10)

where y_i and ${\hat{y}}_{i}$ respectively represent the real and predicted value of robustness measurement parameters for the ith time, m is the total number of predictions, Acc indicates the average prediction accuracy.

For the prediction of normal scale-free network, the minimum, median and mode value of clustering coefficient in each set of data are always the same, so these 3 input parameters in the prediction model are not considered. As shown in Fig. 5, by BP neural network prediction, the real damage results and predicted damage results under grey information attack with different information precision α and the proportion of broken nodes f are compared, the left figures are based on real values of S, L and E, and the right figures are based on predicted values of S, L and E. These figures demonstrate small differences between real values and predicted values. And by Equations (10 and 11), the average prediction accuracy of S, L, E is 94.18%, 85.54%, and 96.41% respectively. As shown in Fig. 5(d), the average prediction accuracy of T is 94.18%. So the predictions are accurate.

Fig.5

Change of network damage results between real and predicted value in normal scale-free network under grey information attack. (a) S. (b) L. (c) E. (d) T.

For the scale-free network with cutoff, the minimum, median and mode value of clustering coefficient, and maximum value of coreness in each set of data are always the same, so these 4 input parameters are not considered in the prediction model. As shown in Fig. 6(a–c), by BP neural network prediction, the damage results under grey information attack with different information precision α and the proportion of broken nodes f are compared. The average prediction accuracy of S, L, E and T is 90.20%, 84.42%, 91.02% , 91.24% respectively, the predictions are also accurate.

Fig.6

Change of network damage results between real and predicted value in scale-free network with cutoff under grey information attack. (a) S. (b) L. (c) E. (d) T.

For the random network, besides the minimum and mode value of clustering coefficient, the maximum, median and mode value of coreness are always the same, so these 5 input parameters are not considered. As shown in Fig. 7(a–c), by BP neural network prediction, the damage results under grey information attack with different information precision α and the proportion of broken nodes f are compared. The average prediction accuracy of S, L, E and T is 96.64%, 88.91%, 98.04% and 97.45% respectively. It is the most accurate prediction among the 3 networks.

Fig.7

Change of network damage results between real and predicted value in random network under grey information attack. (a) S. (b) L. (c) E. (d) T.

By training the neural networks, we can predict the damage results for different networks. So, we can assess damage results of the network caused by any attacks in advance. Next, we will find the main parameters influencing the predicted results in order to estimate the central nodes which have considerable impact on network robustness.

3.3 Influence factors of complex network robustness

In this paper, the weight contribution rate is introduced to analyze the various influence factors which include the number parameter and different topological parameters of broken nodes. The weight contribution rate is defined as the ratio of various input parameters to the output parameters in BP neural network, which can be calculated as follows

$B_{ik} = \sum_{j} {| W_{ij} | \cdot | | W_{jk} | \cdot (\ln | W_{ij} | / - ln \sum_{i} | W_{ij} |) |}$ (12) where W_ij, W_jk is the connection weights of the input layer node i to the middle layer node j, middle layer node j to output layer node k respectively. For normalization, ${\tilde{B}}_{ik}$ can be gotten by ${\tilde{B}}_{ik} = B_{ik} / - \sum_{i} B_{ik}$ (13)

Under grey information attack, Table 1 shows the ratio of 25 factors of broken nodes to the 3 robustness measurement parameters.

As shown in Table 1, for different networks, S, L, E can be influenced differently by various factors of broken nodes. Next, we will consider the effect of various factors on the whole robustness measurement parameters T. The effect on T can be calculated by (7). For normal scale-free network, the top five factors which have the greatest impact on the network robustness are average degree, betweenness variance, degree variance, median betweenness and average betweenness. While in scale-free network with cutoff, the top five factors that influence robustness the most are average degree, betweenness variance, average betweenness, degree variance and the number of broken nodes. But in random network, they are the number of broken nodes, average degree, average betweenness, degree variance and average coreness.

For normal scale-free network, the number of broken nodes would not be the main factor affects the network robustness, there are some central nodes, which are determined by degree and betweenness of nodes and have great influence on the robustness. But for scale-free network with cutoff, the number of broken nodes is the main factor affecting the robustness of the network, the impact of central nodes is less. For random network, the most important factor affecting the network robustness is the number of broken nodes.

4 Analysis of bus network for a city

In this section, we take Shenyang (one of the biggest cities in China) bus network (data from http://shenyang.8684.cn/) as an example. Firstly, a bus network model is constructed, the bus stops are chosen as nodes and an edge exists between two nodes if they are consecutive stops on any bus line [27]. Then, the robustness of this real network under grey information attack is analyzed, which is shown in Fig. 8.

Comparing Fig. 8 with Fig. 3, under grey information attack, there are many similarities for S, L, E and T between Shenyang bus network and scale-free network with cutoff. The damage results of the two networks are the same when α is small. This is because the degree distribution of Shenyang bus network are the same as scale-free network with cutoff, which means that Shenyang bus network does not have the nodes with large degree [28].

Fig.8

Change of robustness measure parameters in Shenyang bus network under grey information attack. (a) S, (b) L, (c) E, (d) T.

While when α > 0.6, the damage results of Shenyang bus network are less serious than scale-free network with cutoff. Because the degree of Shenyang bus network is smaller than the scale-free network with cutoff, the impact is lighter when the nodes with large degree are removed. In a word, it can be inferred that Shenyang bus network has many similarities with scale-free network with cutoff, but they are not the same.

Next, the damage results by training BP neural network are predicted. Under grey information attack, the comparisons of real value with predicted value are shown in Fig. 9. The mode of clustering coefficient in each set of data is always the same, so the mode of clustering coefficient is not considered in the prediction. The average prediction accuracy rate of S, L, E are 88.98%, 80.89% and 91.68% respectively. And its average prediction accuracy rate is 90.54%.

Fig.9

Change of network damage results between real and predicted value in Shenyang bus network under grey information attack. (a) S. (b) L. (c) E. (d) T.

Then different contribution rate of broken nodes on 3 measure parameters and T for Shenyang bus network are shown in Table 2.

Table 2

Different topological parameters of broken nodes to contribution rate of Shenyang bus network robustness (%)

Input parameters	Shenyang bus network
	S	L	E	T	Rank
The number of broken nodes	57.15	40.08	50.65	43.77	1
Degree maximum	0.31	0.62	0.75	0.38	23
Degree minimum	1.22	1.86	1.67	1.11	14
Average degree	11.91	20.21	13.99	10.15	2
Degree variance	3.12	2.46	2.89	2.43	3
Median degree	1.65	1.98	1.81	1.37	9
Mode degree	1.18	1.28	1.46	1.03	17
Clustering coefficient maximum	0.88	1.09	0.96	0.73	21
Clustering coefficient minimum	1.08	1.57	1.61	1.02	18
Average clustering coefficient	1.24	1.78	1.39	1.03	16
Clustering coefficient variance	1.25	1.73	1.46	1.06	15
Median clustering coefficient	1.06	1.63	1.41	0.95	20
Mode clustering coefficient	0	0	0	0	−
Coreness maximum	1.80	2.08	1.77	1.43	7
Coreness minimum	0.19	0.48	0.66	0.30	24
Average coreness	2.47	3.63	2.31	1.93	4
Coreness variance	1.72	2.02	1.86	1.42	8
Median coreness	1.46	1.47	1.56	1.20	13
Mode coreness	0.57	0.95	0.79	0.52	22
Betweenness maximum	1.66	1.96	1.67	1.33	10
Betweenness minimum	1.82	2.67	2.02	1.52	6
Average betweenness	2.01	1.83	2.83	1.85	5
Betweenness variance	1.20	3.12	1.35	1.01	19
Median betweenness	1.47	1.74	1.69	1.24	11
Mode betweenness	1.58	1.76	1.44	1.22	12

As shown in Table 2, in Shenyang bus network, the top five factors of broken nodes that sharply influence the network robustness are the number of broken nodes, average degree, degree variance, average coreness and average betweenness. The number of broken nodes is the primary parameter in Shenyang bus network, and the central nodes are determined by degree, coreness and betweenness of nodes. Compared with Table 1, it is easy to find that the top five factors of Shenyang bus network are close to random network. The most influential factor affecting the network robustness is the number of broken nodes. Meanwhile, other 4 influential topological parameters are the same as random network. So, it is inferred that Shenyang bus network is not only similar to scale-free network with cutoff, but also has several similarities with random network.

By analyzing the main factors on T in Shenyang bus network, some suggestions are proposed to ensure the bus network work well. For one thing, a large number of non-central nodes should be avoid breaking down. This is because the number of broken nodes is the most important factor that affects network robustness. For another thing, the stops passed by more bus lines should be protected because degree is the main parameter for central nodes.

5 Conclusion and prospect

In this paper, firstly, a new way is proposed to randomly generate fully connected networks and analyzed the robustness of 3 networks under grey information attack. Secondly, based on different information precision, the network damage results of the 3 kinds of complex network are simulated. Thirdly, by training the BP neural network, the damage results can be predicted for other information precision. The topological parameters of broken nodes that influence the robustness of different network are also analyzed. This paper found that the central nodes can be determined by the degree and betweenness of nodes in normal scale-free network and scale-free network with cutoff. But for random network, the central nodes are determined by the nodes coreness. Furthermore, various types of networks are affected differently by central nodes. Finally, the damage results of Shenyang bus network under grey information attack were predicted. And it is found that the central nodes are determined by the degree, betweeness and coreness. Also, several suggestions are given to help protect the real bus network.

Footnotes

Acknowledgments

This work is partially supported by the National Natural Science Foundation of China (61473073, 61104074), Fundamental Research Funds for the Central Universities (N170417006) and Program for Liaoning Excellent Talents in University (LJQ2014028).

References

Albert

, Jeong

and Barabási

A.L.

, Error and attack tolerance of complex networks, Nature 406(6794) (2000), 378–382.

Cohen

, Erez

, Ben-Avraham

, et al., Resilience of the Internet to random breakdowns, Physical Review Letters 85(21) (2000), 4626.

Cohen

, Erez

, Ben-Avraham

, et al., Breakdown of the Internet under intentional attack, Physical Review Letters 86(16) (2001), 3682.

Callaway

D.S.

, Newman

M.E.J.

, Strogatz

S.H.

, et al., Network robustness and fragility: Percolation on random graphs, Physical Review Letters 85(25) (2000), 5468.

Albert

, Albert

and Nakarado

G.L.

, Structural vulnerability of the North American power grid, Physical Review E 69(2) (2004), 025103.

, Deng

H.Z.

and Tan

Y.J.

, Vulnerability of complex networks under intentional attack with incomplete information, Journal of Physics A: Mathematical and Theoretical 40(11) (2007), 2665.

Jun

, Jun

, Yong

, et al., Attack robustness of scale-free networks based on grey information, Chinese Physics Letters 28(5) (2011), 058904.

Shang

, Robustness of scale-free networks under attack with tunable grey information, EPL (Europhysics Letters) 95(2) (2011), 28005.

Albert

and Barabási

A.L.

, Topology of evolving networks: Local events and universality, Physical Review Letters 85(24) (2000), 5234.

10.

Lü

and Zhou

, Link prediction in complex networks: A survey, Physica A: Statistical Mechanics and its Applications 390(6) (2011), 1150–1170.

11.

Zhi-Yun

, Peng

, Li

, et al., An evolving network model with modular growth, Chinese Physics B 21(2) (2012), 028904.

12.

Al Hasan

and Zak

M.J.

, A survey of link prediction in social networks, in: Social Network Data Analytics Sringer US, 2011, pp. 243–275.

13.

Cannistraci

C.V.

, Alanis-Lobato

, , and Ravasi

, From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks, Scientific Reports 3 (2013), pp. 1613.

14.

Zhang

, Jin

, Cui

, et al., Network security situation prediction based on BP and RBF neural network, Trustworthy Computing and Services, Springer Berlin Heidelberg (2013), 659–665.

15.

LaRocca

and Guikema

S.D.

, Characterizing and predicting the robustness of power-law networks, Reliability Engineering & System Safety 133 (2015), 157–166.

16.

Barabási

A.L.

and Albert

, Emergence of scaling in random networks, Science 286(5439) (1999), 509–512.

17.

Goh

K.I.

, Kahng

and Kim

, Universal behor of load distribution in scale-free networks, Physical Review Letters 87(27) (2001), 278701.

18.

Chung

and Lu

, Connected components in random graphs with given expected degree sequences, Annals of Combinatorics 6(2) (2002), 125–145.

19.

Mihail

C.G.M.

and Zegura

, The markov chain simulation method for generating connected power law random graphs, Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, SIAM (2003), 16–25.

20.

Catanzaro

, Boguñá

and Pastor-Satorras

, Generation of uncorrelated random scale-free networks, Physical Review E 71(2) (2005), 027103.

21.

Newman

M.E.J.

, Assortative mixing in networks, Physical Review Letters 89(20) (2002), 208701.

22.

Amaral

L.A.N.

, Scala

, Barthelemy

, et al., Classes of small-world networks, Proceedings of the National Academy of Sciences 97(21) (2000), 11149–11152.

23.

Clauset

, Shalizi

C.R.

and Newman

M.E.J.

, Power-law distributions in empirical data, SIAM Review 51(4) (2009), 661–703.

24.

Bornholdt

, Schuster

H.G.

, Handbook of graphs and networks: From the genome to the interne, John Wiley & Sons, 2006.

25.

Milo

, Kashtan

, Itzkovitz

, et al., On the uniform generation of random graphs with prescribed degree sequences, , arXiv preprint cond-mat/0312028, 2003.

26.

Zhang

, Ran

, Wang

and Deng

, Fuzzy evaluation of network vulnerability, Quality and Reliability Engineering International 32(5) (2016), 1715–1730.

27.

Sienkiewicz

and Hołyst

J.A.

, Statistical analysis of 22 public transport networks in Poland, Physical Review E 72(4) (2005), 046127.

28.

Ren

, Wang

Y.F.

, Liu

M.M.

and Xu

Y.J.

, Analysis of robustness of urban bus network, Chinese Physics B 25(2) (2016), 020101.