Research Article
Entropy Optimization of Scale-free Networks Robustness to Targeted Attack
College of Electrical and Information Engineering, Xuchang University, Xuchang, 461000, China
INTRODUCTIONS
Many networks can be characterized as scale-free networks whose degree distributions following p(k)∼ck-α, with α∈(2, 3) (Albert et al., 1999; Newman, 2003), these networks including information networks, technological networks, social networks and biological networks.
To investigate the vulnerability of scale-free networks, Albert et al. (1999) presented two failure modes, i.e., random failure and targeted attack and they found that the scale-free network performs robust to random failure but is vulnerable to targeted attack (Albert et al., 2000). Cohen et al. (2000, 2001) formulated the scale-free network vulnerability as the percolation of generalized random networks using percolation theory. Through the thorough analysis of the robustness of scale-free networks under random failure and targeted attack, Cohen et al. (2000) pointed out that there exists a threshold p and when a fraction p>pc, the network will be broken to disconnected island parts, where p is the ratio of the number of nodes removed to the total number of the nodes in the whole network.
The heterogeneous distribution on links is an essential character of a scale-free network and impacts on the network robustness directly. The more heterogeneous of a network is, the better robustness the network will be. Therefore, other than using percolation theory to analysis and optimize network robustness, the heterogeneity measured by entropy is also used to analyze scale-free network vulnerability and optimization network robustness (Wang et al., 2006). The work by Wang et al. (2006) has proved that the entropy of the degree distribution is effective to measure robustness for scale-free network to random failures. However, the parameter threshold pc indicating the ratio of removed nodes, can not prove the correlation of the entropy of degree distribution to targeted attack, so can not prove the effectiveness of the entropy in measuring the robustness of scale-free networks to targeted attack. Wu and others proposed many different methods to enhance network robustness against intentional attack (Wu et al., 2007; Zhao and Xu, 2009; Xiao et al., 2010; Xiao and Xiao, 2011) etc. Though these methods appear to be effective in detail, they can't reveal the essential relationship among pc, heterogeneous and scale-free networks robustness.
In this study, we improve the work of Wang et al. (2006) to investigate the effectiveness of the entropy in measuring robustness of scale-free network to targeted attack. After examining the relationship between the entropy and the network threshold pc being defined in (Cohen et al., 2000), we define and introduce a parameter pd, to indicate the threshold of the ratio of the number of lost edges to that of all edges in the whole network, i.e., at the threshold pd, the network began to break down to disconnected island parts and no longer is an integrated network topology. Using pd, our work has proved that the entropy of the degree distribution has a positive effect on pd, so that the entropy can be used to measure the network robustness to targeted attack.
To sum up, our work has proved that the entropy of the degree distribution is an effective measurement to evaluate network robustness to both random failures and targeted attack.
THE ENTROPY OF DEGREE DISTRIBUTION FOR TARGETED ATTACK
As demonstrated by Albert et al. (1999), the degree distribution of scale-free network follows power law, i.e., p(k)∼ck-α, k = m, m+1,...,K, m is the minimal network degree (e.g., for Internet, m = 1), K is the maximal network degree. The entropy of the degree distribution is defined by Wang et al. (2006) as follow:
(1) |
N is the total number of vertices.
With the formula (1) of H and continuous approximation, the approximate entropy of the degree distribution can be expressed as formula (2). For more detail derivation, please refer to by Wang et al. (2006):
(2) |
Essentially, H is the approximate entropy of the degree distribution in scale-free network α is the scaling exponent. Figure 1 shows the relationship between α and H, for different values of N when m = 1. For a given N, the entropy of the scale-free network degree distribution decreases with α increasing. With the increase of scaling exponent α, the network heterogeneity will decrease, so that H will also decrease. As an extreme example, when α→∞:
so that the degree distribution is lowest with the entropy being zero. On the contrary, when α→∞, p(m) = p(m+1) = = p(K), network heterogeneity reaches the largest, the entropy H is the largest. For a given α, the larger N is, the more complex the scale-free network is and thus the larger H is.
As mentioned above, pc is an important indicator to measure networks robustness, i.e., the larger the pc, the more robust the network (Cohen et al., 2000). In the random failure scenario, pc behaves a positive effect on the entropy H (Wang et al., 2006).
In the random failure scenario, the failure on nodes and edges of a network occur randomly, nevertheless, the targeted attackers usually destroy the most important network nodes with high connection degree.
Fig. 1: | Relationship between α and H for different N with m = 1 |
Such differences should be carefully considered in proving of the entropy on targeted attack.
Under the targeted attack scenario, according to the percolation theory, we can figure out the standard formula of pc is (Cohen et al., 2001):
(3) |
(4) |
(5) |
(6) |
where, is the probability of an edge randomly being selected associating the removed nodes.
in the targeted attack scenario, is equivalent to the maximum degree in the random failure scenario.
K is the maximal network degree in the targeted attack scenario.
pc is the percentage of removed points in the targeted attack scenario when the network crashes.
Therefore, in the targeted attack scenario, the relationship between pc and α, as well as that between pc and the entropy H can be illustrated in Fig. 2 and 3 respectively, for a set of N(m = 1).
Figure 3 indicates that in the targeted attack, as the entropy H increases, pc increases and then decreases, that is, pc is no longer proportional to the entropy H as do in random failure, so that the entropy H can not be used to measure network robustness. Another indicator other pc is required to evaluate the entropy H on network robustness for targeted attack.
From Fig. 2, we can find that the smaller α is, the larger the max degrees are, i.e., the larger number of edges the max degree node will be connected to. In other words, more edges are occupied by just a small number of hub nodes with a small α, so that once these hub nodes are removed by targeted attacker, a large quantities of network edges will be lost and the network is more be crashed. Therefore, the lost edges can also be used as an effective measurement to evaluate the robustness of networks to targeted attack.
Therefore, we define the edges parameter pd to be the threshold ratio of the removal edges to all the edges in the network topology at which the scale-free networks will break down, so that we can discuss the relationship between pd and H for targeted attack.
Fig. 2: | Relationship between pc and α for different N with m = 1 |
Fig. 3: | Relationship between pc and H for different N with m = 1 |
In study Cohen et al. (2001), is defined as: the probability that a connection belongs to a deleted node, i.e.:
(7) |
According to the definition of pd, in the scenario of targeted attacks, we can formulate pd as following:
(8) |
Formula (7) and (8) are factually the same, i.e., = pd. So we can the percolation theory to get the following equations:
(9) |
(10) |
(11) |
Thus we can derive the relationship between pd and α for m = 1, as shown in Fig. 4. We can find that pd will increase with the increasing of α. In addition, using equation (1), we can get the relationship between the entropy H and pd, as shown in Fig. 5, in which, at m = 1, the change of pd is consistent with that of H.
Fig. 4: | Relationship between pd and α for different N with m = 1 |
Fig. 5: | Relationship between pd and H for different N with m = 1 |
Fig. 6: | Relationship between pd and H for different average connectivity (k). For all curves, αε (2, 3), N = 5x104 |
In other words, when m = 1, the greater the entropy of the degree distribution is, the larger number of edges need to be removed to collapse the network.
To demonstrate the relationship between pd and H in detail, we show the results of the parameter threshold pd and H for different average connectivity (k) in Fig. 6, when αε (2, 3), N = 5x104. The average connectivity (k) is obtained with continuous approximation:
(12) |
As shown in Fig. 6, with the increase of (k), the pd will also increase which means the enhancing on the network robustness. Given a constant (k), pd is proportional to H which indicates that on targeted attack, the bigger pd is, the greater the entropy of the network is and the more edges need to be removed to collapse the network and thus the stronger the network robustness will be.
The heterogeneity of network links relates to network robustness to both random failures and targeted attacks. The entropy of degree distribution has been proved to be an effective parameter to measure the heterogeneity of link distribution, so to measure network robustness to random failure. In this work, we proved that the entropy of degree distribution also performs its effectiveness on measuring network robustness to targeted attack, via introducing the parameter pd as the ratio of removed edges. Therefore, the entropy of degree distribution will contribute to understanding in deep robustness of scale-free networks so to achieve the optimal design of scale-free networks which are our future investigations.
This study was supported by the Science Research Project of Henan Education Department (Grant No. 12A510021), Science and technology R&D program of Xuchang Science and technology bureau (Grant No. 1101060).