# Underestimated Cost of Targeted Attacks on Complex Networks

Authors: Xiao-Long Ren; Niels Gleinig; Dijana Tolić; Nino Antulov-Fantulin
Journal: Complexity
 (2018)

---

## Abstract

The robustness of complex networks under targeted attacks is deeply connected to the resilience of complex systems, which is defined as the ability to make appropriate response to the attack. In this paper, we study robustness of complex networks under a realistic assumption that the cost of removing a node is not constant but rather proportional to the degree of a node or equivalently to the number of removed links a removal action produces. We have investigated the state-of-the-art targeted node removing algorithms and demonstrate that they become very inefficient when the cost of the attack is taken into consideration. For the case when it is possible to attack or remove links, we propose a simple and efficient edge removal strategy named Hierarchical Power Iterative Normalized cut (HPI-Ncut). The results on real and artificial networks show that the HPI-Ncut algorithm outperforms all the node removal and link removal attack algorithms when the same definition of cost is taken into consideration. In addition, we show that, on sparse networks, the complexity of this hierarchical power iteration edge removal algorithm is onlyOnlog2+ε⁡n.


---

## Body

## 1. Introduction

The ability of complex system to dynamically adapt to internal failures or external disturbances is called a resilience. The adaptation is connected to the robustness of the network structure [1], which is defined as the ability to maintain functionality without adaptation to internal failures or external disturbances (attacks). In this paper, we will focus on the robustness of complex networks under targeted attacks with the more realistic cost function. Robustness of connected components under random failure of nodes or links is described with the classical percolation theory [2, 3]. Percolation is the simplest process showing a continuous phase transition, scale invariance, fractal structure, and universality and it is described with just a single parameter, that is, the probability of removing a node or edge. Network science studies have demonstrated that scale-free networks [4, 5] are more robust than random networks [6, 7] under random attacks or failures but less robust under targeted attacks [8–12]. Recently, studies of network resilience have moved their focus to more realistic scenarios of interdependent networks [13], competing networks [14], different failure [15], and recovery [16, 17] mechanisms.Although the study of network robustness has received a huge amount of attention, the majority of the targeted attack strategies are still based on the heuristic identification of influential nodes [11, 18–21] with no performance guarantees for the optimality of the solution. Finding the minimal set of nodes such that their removal maximally fragments the network is called the network dismantling problem [22, 23] and it belongs to the NP-hard class. Thus no polynomial-time algorithm has been found for it and only recently different state-of-the-art methods were proposed as approximation algorithms [22–28] for this task. Although state-of-the-art methods show promising results for network dismantling, we take one step back and analyze the implicit assumption these network dismantling algorithms have. The implicit assumption that the cost of a removing action is equivalent for all nodes regardless of their importance or centrality in network is not a realistic one. Attacking a central node, for example, a high degree node in sociotechnical systems, usually comes with the higher additional cost when compared to the same action on a low degree node. Therefore, it is more realistic to explicitly assume that the cost of an attack is heterogeneous. In this paper, we define the cost of removing a node as a function of its degree.Recently, similar definition of the cost [29] was used to analyze fragmentation and strengthening process for a class of random network models. Under the assumption of the random network models, they found that the optimal cost for fragmentation and strengthening process consists out of the list of priorities of degrees for removed nodes which is independent of the network’s degree distribution.In this work, we make the explicit assumption that the cost of an attack is proportional to the degree of a node or equivalently to the number of adjacent links a removed node has. We investigated different state-of-the-art node removal algorithms on real networks and results show that with respect to this concept of cost, most state-of-the-art algorithms are very inefficient and in most instances perform even worse than the random removal strategy for a fixed finite budget of cost.Furthermore, when edge removal attacks are possible, we compare them to the node removal strategies with respect to the same definition of cost, that is, the number of removed links needed to fragment the network. Note that removing a node is equivalent to removing all the edges of that node, and therefore all node removal actions can be reproduced with the edge removal strategy but vice versa does not hold. Therefore, we also make highlight that the comparisons between node and edge based strategies are only interpretable in cases when edge based attacks are possible. In that case, we propose and use an edge removal strategy, named theHierarchical Power Iterative Normalized cut (HPI-Ncut) as one of the possible solutions to overcome the large fragmentation cost. Although edge based strategies have higher degree of freedom as they can remove only a fraction of edges adjacent to the node, still we find cases where node-based strategies can outperform the edge based strategies. However, our proposed method (HPI-Ncut) always outperforms all the state-of-the-art targeted node-based attack algorithms and edge removal strategies [18, 27, 30].The structure of this paper is organized as follows. First, in Section2 (“Materials and Methods”), we introduce the empirical and artificial networks that are used in this paper (Section 2.1), present and describe current targeted attack strategies (Section 2.2), define a degree cost-fragmentation measure (Section 2.3), and describe the proposed HPI-Ncut method (Section 2.4). Then, in Section 3 (“Results and Discussions”), we quantify the cost of the state-of-the-art node removal strategies and show that in most cases the cost of such attacks is inefficient with respect to the degree-based definition of cost (Section 3.1). These results have important impact for real world scenarios of network fragmentations where cost budget is limited. Finally, when it is possible to remove single edges (e.g., shielding communication links, removing power lines, cutting off trading relationships, or others), we use the proposed HPI-Ncut method and compare its performances with other strategies (Section 3.2). The effect of edge removal HPI-Ncut method as an immunization measure for the epidemic spreading process on networks is presented (Section 3.3).


## 2. Materials and Methods

In this section, we describe data sets and some existing state-of-the-art targeted attack algorithms. Among them, the node removal-based attack algorithms are designed to dismantle the network into pieces with no thought for the cost of the attacking. In other words, these algorithms consider all the nodes have uniform cost. We also introduce the edge betweenness and bridgeness, which originally proposed evaluateing the importance of nodes, as two comparable link attacking methods. Then, we define the degree cost-fragmentation effectiveness (DCFE) as an index to measure the performance of different attacking methods. At last, we introduce the degree cost-fragmentation effectiveness measure and present the HPI-Ncut method.


### 2.1. Data Sets

To evaluate the performances of the network dismantling (fragmentation) algorithms, we used both real networks and synthetic networks in this paper: (a)Political Blogs [31] which is an undirected social network that was collected around the time of the US presidential election in 2004. This network is a relatively dense network whose average degree is 27.36; (b)Petster-hamster which is an undirected social network which contains friendships and family links between users of the website http://hamsterster.com. This network data set can be downloaded from KONECT (http://konect.uni-koblenz.de/networks/petster-hamster); (c)Power Grid [32] which is an undirected Power Grid network in which a node is either a generator, a transformer, or a substation, while a link represents a transmission line. This network data set can also be downloaded from KONECT (http://konect.uni-koblenz.de/networks/opsahl-powergrid); (d)Autonomous Systems is an undirected network from the University of Oregon Route Views Project [33]. This network data set can be downloaded from SNAP (https://snap.stanford.edu/data/as.html); (e) Erdös and Rényi (ER) network [34] is constructed with 2500 nodes. Its average degree is 20 and the connection probability is 0.01; (f) Scale-free (SF) network with size 10,000, exponent 2.5, and average degree 4.68; (g) Scale-free (SF) network with size 10,000, exponent 3.5, and average degree 2.35; (h) stochastic block model (SBM) with ten clusters is an undirected network with 4232 nodes and average degree 2.60. The basic properties of these networks are listed in Table 1.Table 1
Basic statistical features of the GCCs of the eight real and synthetic networks.
Network
Nodes
Links
Avg. degree
Sparsity
Political Blogs (PB)
1222
16714
27.36
2.24
E
-
2
Petster-hamster (PH)
2000
16098
16.10
8.05
E
-
3
Power Grid (PG)
4941
6594
2.67
5.40
E
-
4
Autonomous Systems (AS)
6474
12572
3.88
6.00
E
-
4
ER
2500
12500
10.00
4.00
E
-
3
SF (γ=2.5)
10000
23423
4.68
4.69
E
-
4
SF (γ=3.5)
10000
11761
2.35
2.35
E
-
4
SBM
4232
5503
2.60
6.15
E
-
4


### 2.2. Compared Attack Strategies

In this subsection, we will briefly introduce state-of-the-art node removal attack algorithms and some edge evaluation methods which are used in this paper. We also employ several baselines methods for edge based attacks, which are based on the random edge removal and sequential removal of edges with high betweenness and bridgeness measures.(i)
Percolation method: in the study of the network attacks, percolation [35] is a random process of uniform removal of either nodes (site percolation) or edges (bond percolation).(ii)
High degree (HD) method [9, 36]: in HD method, all the nodes are ranked according to their degrees at the beginning. Then the highest ranked node (and its associated edges) will be removed one by one. The high degree adaptive (HDA) method is an adaptive version of the HD method. The HDA recomputes and ranks the degree of all the nodes before every removing.(iii)
Equal graph partitioning (EGP) algorithm: EGP algorithm [21], which is based on the nested dissection [37] algorithm, can partition a network into two groups with arbitrary size ratio. In every iteration, EGP algorithm divides the target nodes set into three subsets: first group, second group, and the separate group. The separate group is made up of all the nodes that connect to both the first group and the second group. Then minimize the separate group by trying to move nodes to the first group or the second group. Finally, after removing all the nodes in the separate group, the original network will be decomposed into two groups. In our implementation, we partition the network into two groups with approximate equal size.(iv)
Collective Influence (CI) algorithm: CI algorithm [24] attacks the network by mapping the integrity of a tree-like random network into optimal percolation theory [38] to identify the minimal separate set. Specifically, the collective influence of a node is computed by the degree of the neighbors belonging to the frontier of a ball with radius l. CI is an adaptive algorithm which iteratively removes the node with highest CI value after computing the CI values of all the nodes in the residual network. In our implementation, we compute the CI values with l=3.(v)
Min-Sum algorithm: the three-stage Min-Sum algorithm [22] includes (1) breaking all the circles, which could be detected form the 2-core [19] of a network, by the Min-Sum message passing algorithm, (2) breaking all the trees larger than a threshold C1, (3) greedily reinserting short cycles no greater than a threshold C2, which ensures that the size of the GCC is not too large. In our implementation, we set C1 and C2 as 0.5% and 1% of the size of the networks.(vi)
CoreHD algorithm: inspired by Min-Sum algorithm, CoreHD algorithm [23] iteratively deletes the node with highest degree from the 2-core [19] of the residual network.(vii)
Belief propagation-guided decimation (BPD) [28, 39]: the BPD method is a loop-focused global algorithms which removes a set of nodes so that all the loops in the network are broken. In every iteration process, the node with the highest probability of being suitable for deletion is deleted. After the deletion of a specific fraction of nodes, the probability of all the nodes will be updated.(viii)
Edge betweenness [40]: betweenness is a widely used centrality measure which is the sum of the fraction of all-pairs shortest paths that pass a node. Edge betweenness, an extension of the betweenness, is used to evaluate the importance of a link and is defined as the sum of the fraction of all-pairs shortest paths that pass this link [36]. In this strategy, the links are removed sequentially from high to low edge betweenness value.(ix)
Bridgeness [30]: bridgeness uses local information of the network topology to evaluate the significance of edges in maintaining network connectivity. The bridgeness of a link is determined by the size of k-clique communities that the two end points of this link are connected with and the size of the k-clique communities that this link is belonging to.


### 2.3. Degree Cost-Fragmentation Effectiveness (DCFE)

The robustness of the network structure can be measured in different means, but a common way is to characterize the function of the size of the largest connected component (GCC) with respect to the ratio of the removed nodes or edges, that is, cost. Characterization of this function was done in two distinct ways: (i) by the value of critical point when the largest component completely collapses [41] or (ii) by measuring the size of the largest component during the whole attacking process [42]. However, only recently [29] the cost functions for nodes attacks were formulated in a more general way as a function of degree.We make explicit assumption that the cost of removing a node is proportional to the degree or to the number of the adjacent edges that have to be removed. Let us define the functionfD(x) as the size of GCC for fixed attack cost x for strategy D. The cost x∈[0,1] is measured as the ratio of the number of removed edges in the network. Now, for a fixed budget x, strategy D is more efficient than strategy L if and only if fD(x)<fL(x); that is, the size of the GCC is smaller by attacking with strategy D than with strategy L with the limited budget x.Here we define thedegree cost-fragmentation effectiveness (DCFE) for strategy D as the area under the curve of the size of GCC versus the cost, which can be computed as the integral over all possible budgets: FD=∫01fD(x)dx. This measure is a combination of the robustness measure that takes all possible cost budgets [42] into consideration. Here, the cost is proportional to the degree [29] or to the number of the adjacent edges that have to be removed. Smaller value of DCFE implies that the attack has stronger effect over all possible budgets.


### 2.4. HPI-Ncut: Edge Removal Strategy

In this section, we introduce and describe the Hierarchical Power Iterative Normalized cut for edge removal strategy (HPI-Ncut). Thus, if the edge removal actions on networks are applicable, we compare them with the same definition of the cost to the node-based strategies. The link fragmentation problem can be narrated as follows: if we have a budget ofx links that can be attacked or removed, which links should we pick? This is mathematically equivalent to asking how to partition a given network with a minimal separate set of edges.We applied the spectral strategy for edge attack problem, which fall in the class of well-known spectral clustering and partitioning algorithms [43–47]. We use the hierarchical partitioning with Ncut objective function [44] combined with power iteration procedure for approximation of eigenvectors.Now, we describe the hierarchical iterative algorithm for edge removing. This algorithm hierarchically applies the spectral bisection algorithm, which has the same objective function as the normalized cut algorithm [44]. Furthermore we have used the power iteration method to approximate spectral bisection. In order to explain our algorithm, we quickly recall the spectral bisection algorithm.The Spectral Bisection Algorithm
Input: adjacency matrixW of a network
Output: a separated set of edges that partition the network into two disconnected clustersA, A¯:
(1)
compute the eigenvectorv2, which corresponds to the second smallest eigenvalue of the normalized Laplacian matrix Lw=D-1/2D-WD-1/2, or some other vector v for which vTLwv/vTv is close to minimal. We use the power iteration method to compute this vector, which will be explained later,
(2)
put all the nodes withv2(i)>0 into the first cluster A and all the nodes with v2(i)≤0 into the second cluster A¯. All the edges between these two clusters form the separation set that can partition the network.The clusters that we obtained by this method had usually very balanced sizes. If, however, it is very important to get clusters of exactly the same size, one could put thosen/2 nodes with the largest entries in v2 into one cluster and the remaining nodes into the other cluster.Hierarchical Power Iterative Normalized Cut (HPI-Ncut) Algorithm
Input: adjacency matrix of a network
Output: partition of the network into small groups:
(1)
partition the GCC of the network into two disconnected clustersA and A¯ by using the spectral bisection algorithm and removing all the links in the separated set,
(2)
if the budget for link removal has not been overrun and if the GCC is not yet small enough, partitionA and A¯ with Step  (1), respectively.The reason why we cluster hierarchically is because this allows us to refine the fragmentation gradually. For example, if, after partitioning the network into2k clusters, we decide that the clusters should be smaller, we would just have to partition each of the existing clusters into 2 new clusters, obtaining 2k+1 clusters. So the links that were removed already remain removed and we just need to remove some additional ones. If, however, we had used spectral clustering straightforwardly, it could happen that the set of links to be removed in order to partition the network into 2k+1 clusters would not contain the set of links that needed to be removed for 2k clusters.Power Iteration Method
Input: adjacency matrixW of a network, η(n) number of iterations
Output: the eigenvectorv2 or some other vector v for which vTLwv/vTv is close to λ2:
(1)
drawv randomly with uniform distribution on the unit sphere
(2)
setv←v-v1Tv·v1, where v1=(1/n)(1,…,1)
(3)
fori=1 to η(n)
v
←
L
~
v
/
L
~
v, where L~=2·I-Lw and Lw=D-1/2D-WD-1/2.Objective Function of the Spectral Bisection Algorithm. In Appendix A, we show that the spectral bisection algorithm has the same objective function with the relaxed Ncut [44] algorithm:(1)NcutA,A¯≔∑i∈A,j∈A¯Wi,j1∑i∈ADii+1∑j∈A¯Djj,where A⊆V denotes set of nodes in the first partition, A¯ denotes the set of nodes in the second partition, and Dii is the degree of the node i.The main reason we used this objective function is that it minimizes the number of links that are removed and the total sum of node degree centralities in both partitionsA and A¯ is approximately equal. In Appendix B, we show the exponential convergence of the power iteration method to the eigenvector associated with the second smallest eigenvalue of Lw.Complexity of the HPI-Ncut Algorithm. In Appendix C, we show that the complexity of the spectral bisection algorithm is O(η(n)·n·d¯) and the complexity of the hierarchical clustering algorithm is O(η(n)·n·d¯·log⁡(n)) where η(n) is the number of iterations in the power iteration method. The power iteration method converges with exponential speed as η(n)→∞. The average degree d¯ is almost constant for large sparse network. Hence we may expect asymptotically good results with η(n)=log⁡(n)1+ε for any ε>0, giving the hierarchical spectral clustering algorithm a complexity of O(n·log2+ε⁡(n)). In practice, we have used ε=0.1, which gives a complexity of O(n·log2.1⁡(n)).


## 2.1. Data Sets

To evaluate the performances of the network dismantling (fragmentation) algorithms, we used both real networks and synthetic networks in this paper: (a)Political Blogs [31] which is an undirected social network that was collected around the time of the US presidential election in 2004. This network is a relatively dense network whose average degree is 27.36; (b)Petster-hamster which is an undirected social network which contains friendships and family links between users of the website http://hamsterster.com. This network data set can be downloaded from KONECT (http://konect.uni-koblenz.de/networks/petster-hamster); (c)Power Grid [32] which is an undirected Power Grid network in which a node is either a generator, a transformer, or a substation, while a link represents a transmission line. This network data set can also be downloaded from KONECT (http://konect.uni-koblenz.de/networks/opsahl-powergrid); (d)Autonomous Systems is an undirected network from the University of Oregon Route Views Project [33]. This network data set can be downloaded from SNAP (https://snap.stanford.edu/data/as.html); (e) Erdös and Rényi (ER) network [34] is constructed with 2500 nodes. Its average degree is 20 and the connection probability is 0.01; (f) Scale-free (SF) network with size 10,000, exponent 2.5, and average degree 4.68; (g) Scale-free (SF) network with size 10,000, exponent 3.5, and average degree 2.35; (h) stochastic block model (SBM) with ten clusters is an undirected network with 4232 nodes and average degree 2.60. The basic properties of these networks are listed in Table 1.Table 1
Basic statistical features of the GCCs of the eight real and synthetic networks.
Network
Nodes
Links
Avg. degree
Sparsity
Political Blogs (PB)
1222
16714
27.36
2.24
E
-
2
Petster-hamster (PH)
2000
16098
16.10
8.05
E
-
3
Power Grid (PG)
4941
6594
2.67
5.40
E
-
4
Autonomous Systems (AS)
6474
12572
3.88
6.00
E
-
4
ER
2500
12500
10.00
4.00
E
-
3
SF (γ=2.5)
10000
23423
4.68
4.69
E
-
4
SF (γ=3.5)
10000
11761
2.35
2.35
E
-
4
SBM
4232
5503
2.60
6.15
E
-
4


## 2.2. Compared Attack Strategies

In this subsection, we will briefly introduce state-of-the-art node removal attack algorithms and some edge evaluation methods which are used in this paper. We also employ several baselines methods for edge based attacks, which are based on the random edge removal and sequential removal of edges with high betweenness and bridgeness measures.(i)
Percolation method: in the study of the network attacks, percolation [35] is a random process of uniform removal of either nodes (site percolation) or edges (bond percolation).(ii)
High degree (HD) method [9, 36]: in HD method, all the nodes are ranked according to their degrees at the beginning. Then the highest ranked node (and its associated edges) will be removed one by one. The high degree adaptive (HDA) method is an adaptive version of the HD method. The HDA recomputes and ranks the degree of all the nodes before every removing.(iii)
Equal graph partitioning (EGP) algorithm: EGP algorithm [21], which is based on the nested dissection [37] algorithm, can partition a network into two groups with arbitrary size ratio. In every iteration, EGP algorithm divides the target nodes set into three subsets: first group, second group, and the separate group. The separate group is made up of all the nodes that connect to both the first group and the second group. Then minimize the separate group by trying to move nodes to the first group or the second group. Finally, after removing all the nodes in the separate group, the original network will be decomposed into two groups. In our implementation, we partition the network into two groups with approximate equal size.(iv)
Collective Influence (CI) algorithm: CI algorithm [24] attacks the network by mapping the integrity of a tree-like random network into optimal percolation theory [38] to identify the minimal separate set. Specifically, the collective influence of a node is computed by the degree of the neighbors belonging to the frontier of a ball with radius l. CI is an adaptive algorithm which iteratively removes the node with highest CI value after computing the CI values of all the nodes in the residual network. In our implementation, we compute the CI values with l=3.(v)
Min-Sum algorithm: the three-stage Min-Sum algorithm [22] includes (1) breaking all the circles, which could be detected form the 2-core [19] of a network, by the Min-Sum message passing algorithm, (2) breaking all the trees larger than a threshold C1, (3) greedily reinserting short cycles no greater than a threshold C2, which ensures that the size of the GCC is not too large. In our implementation, we set C1 and C2 as 0.5% and 1% of the size of the networks.(vi)
CoreHD algorithm: inspired by Min-Sum algorithm, CoreHD algorithm [23] iteratively deletes the node with highest degree from the 2-core [19] of the residual network.(vii)
Belief propagation-guided decimation (BPD) [28, 39]: the BPD method is a loop-focused global algorithms which removes a set of nodes so that all the loops in the network are broken. In every iteration process, the node with the highest probability of being suitable for deletion is deleted. After the deletion of a specific fraction of nodes, the probability of all the nodes will be updated.(viii)
Edge betweenness [40]: betweenness is a widely used centrality measure which is the sum of the fraction of all-pairs shortest paths that pass a node. Edge betweenness, an extension of the betweenness, is used to evaluate the importance of a link and is defined as the sum of the fraction of all-pairs shortest paths that pass this link [36]. In this strategy, the links are removed sequentially from high to low edge betweenness value.(ix)
Bridgeness [30]: bridgeness uses local information of the network topology to evaluate the significance of edges in maintaining network connectivity. The bridgeness of a link is determined by the size of k-clique communities that the two end points of this link are connected with and the size of the k-clique communities that this link is belonging to.


## 2.3. Degree Cost-Fragmentation Effectiveness (DCFE)

The robustness of the network structure can be measured in different means, but a common way is to characterize the function of the size of the largest connected component (GCC) with respect to the ratio of the removed nodes or edges, that is, cost. Characterization of this function was done in two distinct ways: (i) by the value of critical point when the largest component completely collapses [41] or (ii) by measuring the size of the largest component during the whole attacking process [42]. However, only recently [29] the cost functions for nodes attacks were formulated in a more general way as a function of degree.We make explicit assumption that the cost of removing a node is proportional to the degree or to the number of the adjacent edges that have to be removed. Let us define the functionfD(x) as the size of GCC for fixed attack cost x for strategy D. The cost x∈[0,1] is measured as the ratio of the number of removed edges in the network. Now, for a fixed budget x, strategy D is more efficient than strategy L if and only if fD(x)<fL(x); that is, the size of the GCC is smaller by attacking with strategy D than with strategy L with the limited budget x.Here we define thedegree cost-fragmentation effectiveness (DCFE) for strategy D as the area under the curve of the size of GCC versus the cost, which can be computed as the integral over all possible budgets: FD=∫01fD(x)dx. This measure is a combination of the robustness measure that takes all possible cost budgets [42] into consideration. Here, the cost is proportional to the degree [29] or to the number of the adjacent edges that have to be removed. Smaller value of DCFE implies that the attack has stronger effect over all possible budgets.


## 2.4. HPI-Ncut: Edge Removal Strategy

In this section, we introduce and describe the Hierarchical Power Iterative Normalized cut for edge removal strategy (HPI-Ncut). Thus, if the edge removal actions on networks are applicable, we compare them with the same definition of the cost to the node-based strategies. The link fragmentation problem can be narrated as follows: if we have a budget ofx links that can be attacked or removed, which links should we pick? This is mathematically equivalent to asking how to partition a given network with a minimal separate set of edges.We applied the spectral strategy for edge attack problem, which fall in the class of well-known spectral clustering and partitioning algorithms [43–47]. We use the hierarchical partitioning with Ncut objective function [44] combined with power iteration procedure for approximation of eigenvectors.Now, we describe the hierarchical iterative algorithm for edge removing. This algorithm hierarchically applies the spectral bisection algorithm, which has the same objective function as the normalized cut algorithm [44]. Furthermore we have used the power iteration method to approximate spectral bisection. In order to explain our algorithm, we quickly recall the spectral bisection algorithm.The Spectral Bisection Algorithm
Input: adjacency matrixW of a network
Output: a separated set of edges that partition the network into two disconnected clustersA, A¯:
(1)
compute the eigenvectorv2, which corresponds to the second smallest eigenvalue of the normalized Laplacian matrix Lw=D-1/2D-WD-1/2, or some other vector v for which vTLwv/vTv is close to minimal. We use the power iteration method to compute this vector, which will be explained later,
(2)
put all the nodes withv2(i)>0 into the first cluster A and all the nodes with v2(i)≤0 into the second cluster A¯. All the edges between these two clusters form the separation set that can partition the network.The clusters that we obtained by this method had usually very balanced sizes. If, however, it is very important to get clusters of exactly the same size, one could put thosen/2 nodes with the largest entries in v2 into one cluster and the remaining nodes into the other cluster.Hierarchical Power Iterative Normalized Cut (HPI-Ncut) Algorithm
Input: adjacency matrix of a network
Output: partition of the network into small groups:
(1)
partition the GCC of the network into two disconnected clustersA and A¯ by using the spectral bisection algorithm and removing all the links in the separated set,
(2)
if the budget for link removal has not been overrun and if the GCC is not yet small enough, partitionA and A¯ with Step  (1), respectively.The reason why we cluster hierarchically is because this allows us to refine the fragmentation gradually. For example, if, after partitioning the network into2k clusters, we decide that the clusters should be smaller, we would just have to partition each of the existing clusters into 2 new clusters, obtaining 2k+1 clusters. So the links that were removed already remain removed and we just need to remove some additional ones. If, however, we had used spectral clustering straightforwardly, it could happen that the set of links to be removed in order to partition the network into 2k+1 clusters would not contain the set of links that needed to be removed for 2k clusters.Power Iteration Method
Input: adjacency matrixW of a network, η(n) number of iterations
Output: the eigenvectorv2 or some other vector v for which vTLwv/vTv is close to λ2:
(1)
drawv randomly with uniform distribution on the unit sphere
(2)
setv←v-v1Tv·v1, where v1=(1/n)(1,…,1)
(3)
fori=1 to η(n)
v
←
L
~
v
/
L
~
v, where L~=2·I-Lw and Lw=D-1/2D-WD-1/2.Objective Function of the Spectral Bisection Algorithm. In Appendix A, we show that the spectral bisection algorithm has the same objective function with the relaxed Ncut [44] algorithm:(1)NcutA,A¯≔∑i∈A,j∈A¯Wi,j1∑i∈ADii+1∑j∈A¯Djj,where A⊆V denotes set of nodes in the first partition, A¯ denotes the set of nodes in the second partition, and Dii is the degree of the node i.The main reason we used this objective function is that it minimizes the number of links that are removed and the total sum of node degree centralities in both partitionsA and A¯ is approximately equal. In Appendix B, we show the exponential convergence of the power iteration method to the eigenvector associated with the second smallest eigenvalue of Lw.Complexity of the HPI-Ncut Algorithm. In Appendix C, we show that the complexity of the spectral bisection algorithm is O(η(n)·n·d¯) and the complexity of the hierarchical clustering algorithm is O(η(n)·n·d¯·log⁡(n)) where η(n) is the number of iterations in the power iteration method. The power iteration method converges with exponential speed as η(n)→∞. The average degree d¯ is almost constant for large sparse network. Hence we may expect asymptotically good results with η(n)=log⁡(n)1+ε for any ε>0, giving the hierarchical spectral clustering algorithm a complexity of O(n·log2+ε⁡(n)). In practice, we have used ε=0.1, which gives a complexity of O(n·log2.1⁡(n)).


## 3. Results and Discussions

In this section, we compare existing node targeting attack strategies with respect to the new definition of cost. We make explicit assumption that the cost of removing a node is proportional to the number of the adjacent edges that have to be removed. This suggests that the nodes with higher degree have higher associated removal cost.


### 3.1. Effectiveness of the Node Targeting Attack Strategies

By taking into the account the degree-based cost in targeted attacks, the results can be highly counterintuitive. The performances of the state-of-the-art node removal-based methods are in some cases even worse than the naive process of random removal of nodes (site percolation), when we take into account the attack cost, as shown in Figures1 and 2. In fact, networks have their intrinsic resilience under attacking for their distinct network structures. To avoid the interference of the architectural difference of networks, we use site percolation method as a baseline null model. The site percolation strategy randomly removes nodes in a network, which could be used to reflect the intrinsic resilience of the attacked network to a certain extent. The cost-fragmentation effectiveness of the site percolation is denoted with F∗=∫01f∗(x)dx; see details in Section 2.3.Figure 1
The size of the GCC of the networks versus the link removing proportion, comparing with classical node removal-based methods on real networks. The results of the site percolation are obtained after 100 independent runs.
(a)
Power Grid
(b)
Political Blogs
(c)
Petster-hamster
(d)
Autonomous SystemsFigure 2
The size of the GCC of the networks versus link removing proportion, comparing with classical node removal-based methods on artificial networks. The results of the site percolation are obtained after 100 independent runs.
(a)
ER
(b)
SF(γ=2.5)
(c)
SF(γ=3.5)
(d)
SBM with ten clustersTable2 summarizes the DCFE of different attack strategies on eight networks. Table 3 summarizes the improvement of DCFE of different attack strategies D comparing with the null model (site percolation), which is calculated as ∫01(f∗(x)-fD(x))dx. On the whole, all node-centric strategies (HD, HDA, EGP, CI, CoreHD, Min-Sum, and BPD) distinctly work better than baseline on the three networks with lower average degree, that is, Power Grid, SF (γ=3.5), and SBM network. However, on empirical social Petster-hamster network, Political Blogs network, Autonomous Systems network, and SF (γ=2.5) network, all these node-centric strategies are comparably equal or even worse than the baseline method, according to the DCFE score. More interestingly, for a fixed budget, many networks are more fragile with the HD attack strategy than by HDA, as the results shown in Tables 2 and 3. In the last line of Table 3, we compute the average value of the improvement over different networks, which can reflect the overall performance of the algorithms. These results suggest that state-of-the-art node removal-based algorithms in realistic settings are rather inefficient if the cost of fragmentation is taken into account.Table 2
DCFE, that is, the area under the curve of the size of the GCC after attacking by different algorithms.Psite is short for site percolation, Pbond for bond percolation, Betw for betweenness, and Bridg for bridgeness. The best performing algorithm in each row is emphasized in bold.
DCFE
P
s
i
t
e
HD
HDA
EGP
CI
Min-Sum
CoreHD
BPD
P
b
o
n
d
Betw
Bridg
HPI-Ncut
PB
0.638
0.920
0.861
0.619
0.657
0.726
0.815
0.722
0.843
0.597
0.910
0.278
PH
0.627
0.677
0.696
0.747
0.687
0.675
0.736
0.661
0.817
0.536
0.689
0.224
PG
0.371
0.260
0.293
0.263
0.219
0.130
0.256
0.113
0.305
0.145
0.420
0.014
AS
0.567
0.576
0.604
0.592
0.567
0.567
0.576
0.561
0.605
0.527
0.618
0.192
ER
0.601
0.547
0.647
0.502
0.441
0.268
0.647
0.247
0.753
0.387
0.542
0.032
SF (γ=2.5)
0.619
0.700
0.706
0.671
0.650
0.636
0.660
0.632
0.683
0.672
0.694
0.342
SF (γ=3.5)
0.406
0.231
0.228
0.343
0.214
0.202
0.227
0.192
0.298
0.312
0.352
0.092
SBM
0.487
0.419
0.378
0.397
0.348
0.284
0.374
0.274
0.384
0.348
0.512
0.075Table 3
The improvement of the DCFE of each algorithm, comparing with the baseline, that is, site percolation method. The best performing algorithm in each column is emphasized in bold.
Improvement
P
b
o
n
d
HD
HDA
EGP
CI
Min-Sum
CoreHD
BPD
Betw
Bridg
HPI-Ncut
PB
−32%
−44%
−35%
3%
−3%
−14%
−28%
−13%
6%
−43%
56%
PH
−30%
−8%
−11%
−19%
−10%
−8%
−17%
−5%
15%
−10%
64%
PG
18%
30%
21%
29%
41%
65%
31%
70%
61%
−13%
96%
AS
−7%
−2%
−7%
−4%
0
0
−2%
1%
7%
−9%
66%
ER
−25%
9%
−8%
17%
27%
55%
−8%
59%
36%
10%
95%
SFγ=2.5
−10%
−13%
−14%
−8%
−5%
−3%
−7%
−2%
−9%
−12%
45%
SFγ=3.5
27%
43%
44%
15%
47%
50%
44%
53%
23%
13%
77%
SBM
20%
13%
22%
18%
28%
41%
23%
44%
28%
−6%
84%
Average
−5%
3%
2%
6%
16%
23%
5%
26%
21%
−9%
73%


### 3.2. Effectiveness of the HPI-Ncut Attacks

In this section, we will compare the proposed edge removal-based attack strategy, HPI-Ncut algorithm, with random uniform attack, edge betweenness, bridgeness, and some classical node removing strategies (see the details in Section2). The results show that the HPI-Ncut strategy greatly decreases the cost of the attack, comparing with the state-of-the-art removing strategies.In general case, each attack strategy algorithm could generate a ranking list of all (or partial) nodes or links of the network. After removing the nodes or links one after another, the size of the GCC of the residual network characterizes the effectiveness of each algorithm. The removal process will cease when the size of the GCC is smaller than a given threshold (here we use 0.01). In this paper, to test the effectiveness of this spectral edge removal algorithm, HPI-Ncut, we plot the size of the GCC versus the removal fraction of links, for both real networks (Figures1 and 3) and synthetic networks (Figures 2 and 4), comparing with classical node removing algorithms (Figures 1 and 2) and existing link evaluation methods (Figures 3 and 4). The results show that the HPI-Ncut algorithm outperforms all the other attack algorithms.Figure 3
The size of the GCC of the networks versus link removing proportion, comparing with existing link removal-based methods on real networks. The results of the bond percolation are obtained after 100 independent runs.
(a)
Power Grid
(b)
Political Blogs
(c)
Petster-hamster
(d)
Autonomous SystemsFigure 4
The size of the GCC of the networks versus link removing proportion, comparing with existed link removal-based methods on artificial networks. The results of the bond percolation are obtained after 100 independent runs.
(a)
ER
(b)
SF(γ=2.5)
(c)
SF(γ=3.5)
(d)
SBM with ten clustersIn Figures1 and 2, we compared the HPI-Ncut algorithm with some state-of-the-art node removal-based target attack algorithms. Figure 1(a) shows that all the node removal-based algorithms are better than the site percolation method on Power Grid network, which is because the average degree of the Power Grid network is very low, only 2.67. This could also be verified by the results in Figures 2(c) and 2(d), in which the average degree of the SF (γ=3.5) and the SBM network are 2.35 and 2.60, respectively. The trends of the curves in Figures 1 and 2 also show that the target attack algorithms work better on networks with lower average degree. Furthermore, regardless of the HPI-Ncut algorithm, other algorithms have poorer performance than baseline method (site percolation). The performances of site percolation are better until the proportion of the removed links is greater than 0.7 on SF (γ=3.5) network and until the proportion is greater than 0.2 on SF (γ=2.5) network. The site percolation on the SF (γ=3.5) presents an obvious phase transition phenomenon [48] comparing with the result on the SF (γ=2.5). In addition, in Figures 2(a) and 2(d), the SBM network has obvious clusters structure comparing with the ER network. The BPD, Min-Sum, CI, CoreHD, EGP, and site percolation algorithms have a better performance on the SBM network. Moreover, the error of the site percolation method on the ER network is larger than the error on SBM network. That implies that the cluster structure of a network has a big influence on the performance of the attack strategies.To conclude the results of Figures1 and 2, the state-of-the-art targeted node removal strategies make large cost for optimized targeted attacks. When it is possible to apply edge-bases strategies, the HPI-Ncut algorithm overwhelmingly outperforms all the node removal-based attack algorithms, no matter on sparse or dense networks or on the networks with or without clusters structure. It is also interesting to show that some of the node targeted attack strategies (BPD, Min-Sum) can also outperform edge based strategies on several networks (PG, ER, SF, and SBM), but not the HPI-Ncut.In Figures3 and 4, we compared the HPI-Ncut algorithm with some exited link evaluation algorithms. First of all, we can find that the HPI-Ncut algorithm works better and is more stable than all the other algorithms. Secondly, comparing with the results of site and bond percolation in Figures 1 and 2, we can see that the bond percolation method outperforms the site percolation method only when the average degree of the network is lower (see the results of the Power Grid, SF (γ=3.5), and SBM network); otherwise, the site percolation is a better choice. Thirdly, in Figures 4(b) and 4(c), we can see that the bond percolation method has a better performance comparing with the edge betweenness and bridgeness algorithm when the cost is limited on scale-free networks; that is, the proportion of the removed links is smaller than 0.63 in Figure 4(b) and is smaller than 0.4 in Figure 4(c). To conclude, the HPI-Ncut algorithm overwhelmingly outperforms all the node removal-based attack algorithms and link evaluation algorithms, no matter on sparse or dense networks or on networks with or without clusters structure.


### 3.3. Spreading Dynamics after HPI-Ncut Immunization

To more intuitively display the ability of the HPI-Ncut to make immunization of links, we studied the susceptible-infectious-recovery (SIR) [49] epidemic spreading process on four real networks. We compared both the spreading speed and spreading scope on these networks before and after targeted immunization by HPI-Ncut. The simulation results in Figure 5 show that, by simply removing 10% of links, the function of the networks had been profoundly affected by the HPI-Ncut immunization. The proportion of the GCC of the Political Blogs, Power Grid, Petster-hamster, and Autonomous Systems network after attack are 37% (449/1222), 1% (54/4941), 57% (1146/2000), and 37% (2387/6474), respectively. Thus, the spreading speeds are greatly delayed and the spreading scoops are tremendously shrunken on these networks.Figure 5
The spreadability of the networks before and after the removing of 10% edges by HPI-Ncut algorithm. Thex-axis is the time units. Pi is the number of infected entities and Pr is the number of recovered entities in the network. In the SIR model, the infection rate β is 0.10, the recovery rate is 0.02, and the basic reproduction number is 5. All the results are the average of 100 times independent runs. It is worth noting that the size of GCC of the Power Grid network is only 54 after removing 10% of links by HPI-Ncut algorithm.
(a)
Political Blogs
(b)
Power Grid
(c)
Petster-hamster
(d)
Autonomous Systems


## 3.1. Effectiveness of the Node Targeting Attack Strategies

By taking into the account the degree-based cost in targeted attacks, the results can be highly counterintuitive. The performances of the state-of-the-art node removal-based methods are in some cases even worse than the naive process of random removal of nodes (site percolation), when we take into account the attack cost, as shown in Figures1 and 2. In fact, networks have their intrinsic resilience under attacking for their distinct network structures. To avoid the interference of the architectural difference of networks, we use site percolation method as a baseline null model. The site percolation strategy randomly removes nodes in a network, which could be used to reflect the intrinsic resilience of the attacked network to a certain extent. The cost-fragmentation effectiveness of the site percolation is denoted with F∗=∫01f∗(x)dx; see details in Section 2.3.Figure 1
The size of the GCC of the networks versus the link removing proportion, comparing with classical node removal-based methods on real networks. The results of the site percolation are obtained after 100 independent runs.
(a)
Power Grid
(b)
Political Blogs
(c)
Petster-hamster
(d)
Autonomous SystemsFigure 2
The size of the GCC of the networks versus link removing proportion, comparing with classical node removal-based methods on artificial networks. The results of the site percolation are obtained after 100 independent runs.
(a)
ER
(b)
SF(γ=2.5)
(c)
SF(γ=3.5)
(d)
SBM with ten clustersTable2 summarizes the DCFE of different attack strategies on eight networks. Table 3 summarizes the improvement of DCFE of different attack strategies D comparing with the null model (site percolation), which is calculated as ∫01(f∗(x)-fD(x))dx. On the whole, all node-centric strategies (HD, HDA, EGP, CI, CoreHD, Min-Sum, and BPD) distinctly work better than baseline on the three networks with lower average degree, that is, Power Grid, SF (γ=3.5), and SBM network. However, on empirical social Petster-hamster network, Political Blogs network, Autonomous Systems network, and SF (γ=2.5) network, all these node-centric strategies are comparably equal or even worse than the baseline method, according to the DCFE score. More interestingly, for a fixed budget, many networks are more fragile with the HD attack strategy than by HDA, as the results shown in Tables 2 and 3. In the last line of Table 3, we compute the average value of the improvement over different networks, which can reflect the overall performance of the algorithms. These results suggest that state-of-the-art node removal-based algorithms in realistic settings are rather inefficient if the cost of fragmentation is taken into account.Table 2
DCFE, that is, the area under the curve of the size of the GCC after attacking by different algorithms.Psite is short for site percolation, Pbond for bond percolation, Betw for betweenness, and Bridg for bridgeness. The best performing algorithm in each row is emphasized in bold.
DCFE
P
s
i
t
e
HD
HDA
EGP
CI
Min-Sum
CoreHD
BPD
P
b
o
n
d
Betw
Bridg
HPI-Ncut
PB
0.638
0.920
0.861
0.619
0.657
0.726
0.815
0.722
0.843
0.597
0.910
0.278
PH
0.627
0.677
0.696
0.747
0.687
0.675
0.736
0.661
0.817
0.536
0.689
0.224
PG
0.371
0.260
0.293
0.263
0.219
0.130
0.256
0.113
0.305
0.145
0.420
0.014
AS
0.567
0.576
0.604
0.592
0.567
0.567
0.576
0.561
0.605
0.527
0.618
0.192
ER
0.601
0.547
0.647
0.502
0.441
0.268
0.647
0.247
0.753
0.387
0.542
0.032
SF (γ=2.5)
0.619
0.700
0.706
0.671
0.650
0.636
0.660
0.632
0.683
0.672
0.694
0.342
SF (γ=3.5)
0.406
0.231
0.228
0.343
0.214
0.202
0.227
0.192
0.298
0.312
0.352
0.092
SBM
0.487
0.419
0.378
0.397
0.348
0.284
0.374
0.274
0.384
0.348
0.512
0.075Table 3
The improvement of the DCFE of each algorithm, comparing with the baseline, that is, site percolation method. The best performing algorithm in each column is emphasized in bold.
Improvement
P
b
o
n
d
HD
HDA
EGP
CI
Min-Sum
CoreHD
BPD
Betw
Bridg
HPI-Ncut
PB
−32%
−44%
−35%
3%
−3%
−14%
−28%
−13%
6%
−43%
56%
PH
−30%
−8%
−11%
−19%
−10%
−8%
−17%
−5%
15%
−10%
64%
PG
18%
30%
21%
29%
41%
65%
31%
70%
61%
−13%
96%
AS
−7%
−2%
−7%
−4%
0
0
−2%
1%
7%
−9%
66%
ER
−25%
9%
−8%
17%
27%
55%
−8%
59%
36%
10%
95%
SFγ=2.5
−10%
−13%
−14%
−8%
−5%
−3%
−7%
−2%
−9%
−12%
45%
SFγ=3.5
27%
43%
44%
15%
47%
50%
44%
53%
23%
13%
77%
SBM
20%
13%
22%
18%
28%
41%
23%
44%
28%
−6%
84%
Average
−5%
3%
2%
6%
16%
23%
5%
26%
21%
−9%
73%


## 3.2. Effectiveness of the HPI-Ncut Attacks

In this section, we will compare the proposed edge removal-based attack strategy, HPI-Ncut algorithm, with random uniform attack, edge betweenness, bridgeness, and some classical node removing strategies (see the details in Section2). The results show that the HPI-Ncut strategy greatly decreases the cost of the attack, comparing with the state-of-the-art removing strategies.In general case, each attack strategy algorithm could generate a ranking list of all (or partial) nodes or links of the network. After removing the nodes or links one after another, the size of the GCC of the residual network characterizes the effectiveness of each algorithm. The removal process will cease when the size of the GCC is smaller than a given threshold (here we use 0.01). In this paper, to test the effectiveness of this spectral edge removal algorithm, HPI-Ncut, we plot the size of the GCC versus the removal fraction of links, for both real networks (Figures1 and 3) and synthetic networks (Figures 2 and 4), comparing with classical node removing algorithms (Figures 1 and 2) and existing link evaluation methods (Figures 3 and 4). The results show that the HPI-Ncut algorithm outperforms all the other attack algorithms.Figure 3
The size of the GCC of the networks versus link removing proportion, comparing with existing link removal-based methods on real networks. The results of the bond percolation are obtained after 100 independent runs.
(a)
Power Grid
(b)
Political Blogs
(c)
Petster-hamster
(d)
Autonomous SystemsFigure 4
The size of the GCC of the networks versus link removing proportion, comparing with existed link removal-based methods on artificial networks. The results of the bond percolation are obtained after 100 independent runs.
(a)
ER
(b)
SF(γ=2.5)
(c)
SF(γ=3.5)
(d)
SBM with ten clustersIn Figures1 and 2, we compared the HPI-Ncut algorithm with some state-of-the-art node removal-based target attack algorithms. Figure 1(a) shows that all the node removal-based algorithms are better than the site percolation method on Power Grid network, which is because the average degree of the Power Grid network is very low, only 2.67. This could also be verified by the results in Figures 2(c) and 2(d), in which the average degree of the SF (γ=3.5) and the SBM network are 2.35 and 2.60, respectively. The trends of the curves in Figures 1 and 2 also show that the target attack algorithms work better on networks with lower average degree. Furthermore, regardless of the HPI-Ncut algorithm, other algorithms have poorer performance than baseline method (site percolation). The performances of site percolation are better until the proportion of the removed links is greater than 0.7 on SF (γ=3.5) network and until the proportion is greater than 0.2 on SF (γ=2.5) network. The site percolation on the SF (γ=3.5) presents an obvious phase transition phenomenon [48] comparing with the result on the SF (γ=2.5). In addition, in Figures 2(a) and 2(d), the SBM network has obvious clusters structure comparing with the ER network. The BPD, Min-Sum, CI, CoreHD, EGP, and site percolation algorithms have a better performance on the SBM network. Moreover, the error of the site percolation method on the ER network is larger than the error on SBM network. That implies that the cluster structure of a network has a big influence on the performance of the attack strategies.To conclude the results of Figures1 and 2, the state-of-the-art targeted node removal strategies make large cost for optimized targeted attacks. When it is possible to apply edge-bases strategies, the HPI-Ncut algorithm overwhelmingly outperforms all the node removal-based attack algorithms, no matter on sparse or dense networks or on the networks with or without clusters structure. It is also interesting to show that some of the node targeted attack strategies (BPD, Min-Sum) can also outperform edge based strategies on several networks (PG, ER, SF, and SBM), but not the HPI-Ncut.In Figures3 and 4, we compared the HPI-Ncut algorithm with some exited link evaluation algorithms. First of all, we can find that the HPI-Ncut algorithm works better and is more stable than all the other algorithms. Secondly, comparing with the results of site and bond percolation in Figures 1 and 2, we can see that the bond percolation method outperforms the site percolation method only when the average degree of the network is lower (see the results of the Power Grid, SF (γ=3.5), and SBM network); otherwise, the site percolation is a better choice. Thirdly, in Figures 4(b) and 4(c), we can see that the bond percolation method has a better performance comparing with the edge betweenness and bridgeness algorithm when the cost is limited on scale-free networks; that is, the proportion of the removed links is smaller than 0.63 in Figure 4(b) and is smaller than 0.4 in Figure 4(c). To conclude, the HPI-Ncut algorithm overwhelmingly outperforms all the node removal-based attack algorithms and link evaluation algorithms, no matter on sparse or dense networks or on networks with or without clusters structure.


## 3.3. Spreading Dynamics after HPI-Ncut Immunization

To more intuitively display the ability of the HPI-Ncut to make immunization of links, we studied the susceptible-infectious-recovery (SIR) [49] epidemic spreading process on four real networks. We compared both the spreading speed and spreading scope on these networks before and after targeted immunization by HPI-Ncut. The simulation results in Figure 5 show that, by simply removing 10% of links, the function of the networks had been profoundly affected by the HPI-Ncut immunization. The proportion of the GCC of the Political Blogs, Power Grid, Petster-hamster, and Autonomous Systems network after attack are 37% (449/1222), 1% (54/4941), 57% (1146/2000), and 37% (2387/6474), respectively. Thus, the spreading speeds are greatly delayed and the spreading scoops are tremendously shrunken on these networks.Figure 5
The spreadability of the networks before and after the removing of 10% edges by HPI-Ncut algorithm. Thex-axis is the time units. Pi is the number of infected entities and Pr is the number of recovered entities in the network. In the SIR model, the infection rate β is 0.10, the recovery rate is 0.02, and the basic reproduction number is 5. All the results are the average of 100 times independent runs. It is worth noting that the size of GCC of the Power Grid network is only 54 after removing 10% of links by HPI-Ncut algorithm.
(a)
Political Blogs
(b)
Power Grid
(c)
Petster-hamster
(d)
Autonomous Systems


## 4. Conclusion

To summarize, we investigated some state-of-the-art node target attack algorithms and found that they are very inefficient when the degree-based cost of the attack is taken into consideration. The cost of removing a node is defined as the number of links that have to be removed in the attack process.We found some highly counterintuitive results; that is, the performances of the state-of-the-art node removal-based methods are even worse than the naive site percolation method with respect to the limited cost. This demonstrates that the current state-of-the-art node targeted attack strategies underestimate the heterogeneity of the cost associated with the nodes in complex networks.Furthermore, in cases when the link removal strategies are possible, we compared the performances of the node-centric (HD, HDA, EGP, CI, CoreHD, BPD, and Min-Sum) and edge removal strategies (edge betweenness and bridgeness strategy) based on the cost of their attacks, which are measured in the same units, that is, the ratio of the removed links. We propose a hierarchical power iterative algorithm (HPI-Ncut) to fragment a network, which has the same objective function with the Ncut [44] spectral clustering algorithm. The results show that HPI-Ncut algorithm outperforms all the node removal-based attack algorithms and link evaluation algorithms on all the networks. In addition, the total complexity of the HPI-Ncut algorithm is only On·log2+ε⁡n, which makes it very practical to be applied on large scale networks over a million of nodes.The underestimated cost of current state-of-the-art algorithms with respect to the degree-based cost has high influence on the development and design of better robustness and resilience mechanisms in complex systems. Furthermore, more accurate estimation of robustness under realistic conditions will allow better allocation of response resources.



---

*Source: 9826243-2018-01-17.xml*