# New Betweenness Centrality Node Attack Strategies for Real-World Complex Weighted Networks

Authors: Quang Nguyen; Ngoc-Kim-Khanh Nguyen; Davide Cassi; Michele Bellingeri
Journal: Complexity
 (2021)

---

## Abstract

In this work, we introduce a new node attack strategy removing nodes with the highest conditional weighted betweenness centrality (CondWBet), which combines the weighted structure of the network and the node’s conditional betweenness. We compare its efficacy with well-known attack strategies from literature over five real-world complex weighted networks. We use the network weighted efficiency (WEFF) like a measure encompassing the weighted structure of the network, in addition to the commonly used binary-topological measure, i.e., the largest connected cluster (LCC). We find that if the measure is WEFF, the CondWBet strategy is the best to decrease WEFF in 3 out of 5 cases. Further, CondWBet is the most effective strategy to reduce WEFF at the beginning of the removal process, whereas the Strength that removes nodes with the highest sum of the link weights first shows the highest efficacy in the final phase of the removal process when the network is broken into many small clusters. These last outcomes would suggest that a better attacking in weighted networks strategy could be a combination of the CondWBet and Strength strategies.


---

## Body

## 1. Introduction

The study of real-world complex networks has attracted much attention in recent decades because a large number of real complex systems can be abstracted as networks [1, 2]. One of the fundamental research topics is their robustness (resilience), i.e., capacity of the network to hold its functioning when a proportion of nodes are removed/blocked [3–12]. The robustness is usually evaluated by the size of the largest connected cluster (LCC) in the network and is a fundamental problem of theoretical and applied network science with huge efforts made in recent years [3, 7, 9, 12–17]. Previous studies showed that most real-world networks are resilient to random failure [4] but can disintegrate quickly when a small proportion of most connected nodes (hubs) are attacked [13]. Furthermore, one of the remarkable observations is when the proportion of removed nodes is high enough, a phase transition occurs, and the probability for the existence of a LCC in the network abruptly collapses (i.e., the network loses its global nodes connectivity). Monte Carlo simulation is usually used to run the attack by removing nodes according to a structural criterion and tracing the network damage using measures/indicators of its functioning. The most common criteria are node’s centrality such as degree centrality [3, 4, 5, 9], closeness centrality [9, 18], and betweenness centrality [7, 14, 19]. Other node attack strategies are based on eigenvector [9, 20], the degree of the second neighbors [7], and entropy [21].Overall findings showed that nodes attack strategies based on betweenness centrality are highly efficient to dismantle the LCC for most model and real-world networks [7, 9, 10, 12]. The attack based on the betweenness centrality (Bet) ranks and removes nodes according to their role in routing the shortest paths in the network; i.e., nodes with higher betweenness centrality are the ones that pass the major number of shortest paths among other nodes [7, 12]. This finding indicated that the most important nodes are not necessarily the most connected ones (i.e., hubs), but they can be nodes with a medium or low connectivity level and high betweenness centrality. However, it is found that the Bet strategy becomes ineffective at the end of the removal process when the network may be broken in many fully connected subnetworks (clusters) [10]. This is due to the inherent nature of betweenness’s definition for a fully connected network (e.g., a complete graph); all node’s betweenness is zero. At this stage, the Bet strategy was unable to break the fully connected LCC for a very long time, and finally, it fails to completely break the network earlier than other strategies, such as the degree-based strategy. To overcome this limitation of the betweenness nodes attack strategies, Nguyen et al. [22] introduced the “conditional attack strategy” (CondBet) that removes nodes according to their betweenness only if they belong to the LCC, demonstrating how the new conditional strategy outperforms the classic nodes attack strategies. However, most of the aforementioned researches investigate binary complex networks, where the interaction between two nodes is either 1 (have an edge) or 0 (no edge).In reality, many real-world complex networks are naturally weighted with some interaction value associated to the links. For example, in a communication network, the link weights may represent the frequency of e-mail exchanges [23, 24]; in the Internet network link weights could be the connection bandwidth magnitude [24, 25]; in a flights transportation network, the link weights could be the total passengers flowing between airports ([26]. In some cases, real networks own very large link weight heterogeneity, with link weights spanning over five order of magnitude, such as the passengers flow between airports [8]. This implies that, to perform more real and precise network description, it is necessary to account the link weights heterogeneity.Bellingeri and Cassi [27] analyzed the robustness of real-world networks to different nodes attack strategies using binary and weighted indicators of network functioning. The authors found that the inclusion of link weights in the analyses changes the network response to nodes attack, outlining the importance to investigate the performance of nodes attack strategies in weighted networks [27]. This leads us to the questions: (1) Which is the best nodes attack strategy to harm real weighted networks? And (2) How does the inclusion of link weight changes the global efficacy of the nodes attack betweenness-based strategies? (3) What metric should we use to measure the robustness of a weighted network?In this paper, we analyzed the robustness of a high-quality dataset of real-world weighted networks from different fields of science. We implemented six attack strategies based on binary and weighted properties of the nodes. We adopted the recalculated (adaptive) version of the nodes attack strategies, in which the nodes rank is updated after each nodes removal [12]. Here, we introduce for the first time the conditional nodes weighted betweenness centrality (CondWBet) attack strategy (the weighted version of the CondBet strategy) that remove nodes of highest weighted betweenness centrality inside the LCC. We test the efficacy of the different nodes attack strategies by computing their impact on network robustness using both binary and weighted measures of network functioning, i.e., the largest connected cluster (LCC) and the weighted efficiency (WEFF).We found that the conditional betweenness attack strategy (CondBet) is the best to fragment the LCC in all the networks confirming previous evidences [22]. Then, when the goal is to decrease the network efficiency measure (WEFF), in 3 out of 5 networks, the new weighted conditional betweenness strategy (CondWBet) is the best strategy. On the other hand, in two other networks, the nodes strength attack strategies (Strength that removes nodes with highest sum of link weights) and the binary conditional betweenness strategy (CondBet) are the best strategies. We propose that an efficient breakdown of a weighted network, as measured by the WEFF, can be divided into two phases: the first one is when the network is still dense and the CondBet/CondWBet are more appropriate to dismantle the network as they can separate the network into smaller clusters; the second one is when the network is broken into many small clusters, and then the Strength strategy is more efficient as it breaks the nodes that reduce the most of the WEFF. The introduction of the new node attack strategy CondWBet and its efficacy comparison with other strategies from literature is the main contribution our work.The paper is organized as follows. In Section2, we describe the data and methods used in this work. Section 3 presents the empirical findings: the efficacy of six intentional attacking strategies over five real-world weighted networks. Finally, Section 4 summarizes the results and concludes the study.


## 2. Method and Data

### 2.1. The Nodes Attack Strategies

We simulate nodes attacks strategies belonging to two main groups, the binary and the weighted-based strategies. In each group, we use node degree, node betweenness centrality, and the conditional betweenness centrality for nodes ranking. In case of nodes ranking ties (e.g., nodes with equals rank), we randomly sort one of them.In total, we adopt six nodes attack strategies:(i)
Deg: degree-based attack strategy removes nodes according to their degree; i.e., the degree of the node is the number of links to it [3]. This is the simplest and the oldest type of node attack widely used to test the networks robustness.(ii)
Bet: betweenness attack strategy removes the nodes with the highest betweenness centrality first. The betweenness centrality of the node is a macroscale network metric measuring the number of times a node appears in the shortest path between all pairs of nodes in the network [7, 12, 28].(iii)
CondBet: conditional betweenness attack strategy is the improved version of the Bet [22]. The CondBet removes the node with highest betweenness if it is in the LCC; otherwise, it removes the node with highest betweenness inside the LCC. In other words, the CondBet removes nodes inside the LCC only, maximizing the efficacy of the Bet strategy into disrupting the LCC. It has been shown that the CondBet performs better than Bet, and it owns higher efficacy to fragment the LCC on a variety of real-world networks.(iv)
Strength: strength attack strategy removes nodes in decreasing rank of strength. The strength of the node is the sum of the link weights pointing to it [27]. The strength of the node is defined as the “weighted degree” and for this reason, the Strength can be viewed as the weighted counterpart of the Deg strategy.(v)
WBet: Weighted Betweenness attack strategy removes nodes according to their weighted betweenness centrality. Like the binary version of the nodes betweenness centrality, the weighted betweenness centrality for each node is the number of the shortest paths that pass through the nodes. The difference in this case is that the shortest paths among nodes are weighted shortest path (WSP). To compute WSP, it is necessary to distinguish whether the link weights indicate “flow” or “cost” among nodes [28]. Examples of “weight as a flows” are the strength of friendship among individuals, the number of common papers among authors, the number of flights among airports, and the number of synapses among neurons. Examples of “weight as a cost” are the distance among cities, the resistance in a circuit, and the time to information delivery between computers. If they are “flow,” in WSP, each link contributes to the shortest path according to their inverse weight. This is a standard procedure making links of higher weight equivalent to “larger, faster, and shorter route” between nodes. Since our real-world networks have link weights as a flow, the WSP between two nodes is the path minimizing the sum of the inverse link weights between that pair of nodes. Differently, if they are “cost,” the WSP between nodes is the path minimizing the sum of the link weights to travel between them.(vi)
CondWBet: conditional weighted betweenness attack strategy is introduced for the first time in this work. It is the weighted version of the CondBet. The CondWBet strategy removes nodes inside the LCC according to their recalculated weighted betweenness centrality.


## 2.1. The Nodes Attack Strategies

We simulate nodes attacks strategies belonging to two main groups, the binary and the weighted-based strategies. In each group, we use node degree, node betweenness centrality, and the conditional betweenness centrality for nodes ranking. In case of nodes ranking ties (e.g., nodes with equals rank), we randomly sort one of them.In total, we adopt six nodes attack strategies:(i)
Deg: degree-based attack strategy removes nodes according to their degree; i.e., the degree of the node is the number of links to it [3]. This is the simplest and the oldest type of node attack widely used to test the networks robustness.(ii)
Bet: betweenness attack strategy removes the nodes with the highest betweenness centrality first. The betweenness centrality of the node is a macroscale network metric measuring the number of times a node appears in the shortest path between all pairs of nodes in the network [7, 12, 28].(iii)
CondBet: conditional betweenness attack strategy is the improved version of the Bet [22]. The CondBet removes the node with highest betweenness if it is in the LCC; otherwise, it removes the node with highest betweenness inside the LCC. In other words, the CondBet removes nodes inside the LCC only, maximizing the efficacy of the Bet strategy into disrupting the LCC. It has been shown that the CondBet performs better than Bet, and it owns higher efficacy to fragment the LCC on a variety of real-world networks.(iv)
Strength: strength attack strategy removes nodes in decreasing rank of strength. The strength of the node is the sum of the link weights pointing to it [27]. The strength of the node is defined as the “weighted degree” and for this reason, the Strength can be viewed as the weighted counterpart of the Deg strategy.(v)
WBet: Weighted Betweenness attack strategy removes nodes according to their weighted betweenness centrality. Like the binary version of the nodes betweenness centrality, the weighted betweenness centrality for each node is the number of the shortest paths that pass through the nodes. The difference in this case is that the shortest paths among nodes are weighted shortest path (WSP). To compute WSP, it is necessary to distinguish whether the link weights indicate “flow” or “cost” among nodes [28]. Examples of “weight as a flows” are the strength of friendship among individuals, the number of common papers among authors, the number of flights among airports, and the number of synapses among neurons. Examples of “weight as a cost” are the distance among cities, the resistance in a circuit, and the time to information delivery between computers. If they are “flow,” in WSP, each link contributes to the shortest path according to their inverse weight. This is a standard procedure making links of higher weight equivalent to “larger, faster, and shorter route” between nodes. Since our real-world networks have link weights as a flow, the WSP between two nodes is the path minimizing the sum of the inverse link weights between that pair of nodes. Differently, if they are “cost,” the WSP between nodes is the path minimizing the sum of the link weights to travel between them.(vi)
CondWBet: conditional weighted betweenness attack strategy is introduced for the first time in this work. It is the weighted version of the CondBet. The CondWBet strategy removes nodes inside the LCC according to their recalculated weighted betweenness centrality.


## 3. The Real-World Networks

We analyzed the efficacy of the nodes attack strategies on five real-world weighted networks (Table1). The first two are financial networks constructed from stock prices in the SP500 index in the US market using a threshold method [29]. We keep the value of the correlation coefficients that are higher than the threshold as link weights. By adjusting the threshold, we can obtain two networks with a similar average degree and number of nodes but with different topological structures. The first network, (i) the SP500_1, is built from Feb. 1993 to Feb. 1996, which is relatively uniformly connected and contains 315 nodes and 8706 links (see Figure 1(a)). The second, (ii) SP500_2, is built from May 1999 to May 2002, which contains 371 nodes and 10636 links [22]. This network has several well-connected clusters connecting to the central bulk through intermediated stocks (see Figure 1(c)). The other three networks are as follows: (iii) the co-authorship undirected network of scientists working on network theory and experiments (NetScience) compiled by Newman [30]. Nodes represent authors, and link weights represent the number of common papers. The network includes 1589 nodes and 2742 links (see Figure 1(e)); (iv) the network of 6005 peoples who trade Bitcoin on a platform called Bitcoin OTC (Bitcoin) [31, 29]. The weight of the links represents the rate of members on other members, which is in a scale of −10 (total distrust) to +10 (total trust) with steps of 1. We simplified the network by removing self-node links and converting it to an undirected network. It results in a network of 6005 nodes and 21492 links (see Figure 1(g)); (v) the network of 500 busiest airports in U.S. [33], where nodes represent airports, and the weight of a link identifies the normalized passengers flowing between two airports/nodes (see Figure 1(i)) [8].Table 1
Structural statistics of the real-world networks: network type, nodes type, weight definition,N nodes’ number, L links’ number, <k> average node degree, 
 average node strength, w average link weight, C global clustering coefficient, Q the modularity, LCC the size of initial largest clustered components, LCC% the relative size of the LCC, Nb_comp the number of components, the new metric <r> for the ratio of pair betwenneess ranking change, and the network Reference.
NameSP500_1SP500_2NetScienceBitcoinUSAirportTypeFinancialFinancialCo-authorSocialTrafficNodesStockStockScientistMemberAirportWeightCorrelation coefficientCorrelation coefficientNumber of common papersTrusting ratePassengers flowN31531715896005499L8706106362742214922980<k>27.628.61.723.575.97
10.34918.8171.4976.5380.0675w0.1870.3280.4330.9130.018C0.5110.7180.8780.2880.726Q0.2530.3730.9540.4980.283LCC3153693795875499LCC%100.0%99.5%23.9%97.8%100.0%Nb123961281<r>0.393000.436260.007520.148020.31965Ref.[22][22][30, 34][31, 32][33]Figure 1
An example of weighted network composed of two small clusters. The node A has higher strength (10) and lower weighted betweenness (2/5) than node B; the node B presents lower strength (4), and higher weighted betweenness (3) than node (A) For this reason, the CondWBet will remove the node B and the Strength will remove node (A) The CondWBet is more efficient than Strength when the robustness measure is the LCC, but it is worse than the Strength when measured by the WEFF.A detailed summary of all networks is represented in Table1. Overall, our networks have a number of nodes from 315 to 6005. The two financial networks, the SP500_1 and SP500_2, are very dense with an average degree of more than 27, while the NetScience network is the sparsest one with an average degree of 1.72. Also, the NetScience network is composed of 396 subgraphs, and its LCC’s size is only 23.9% of the total number of nodes N. Its clustering coefficient C and modularity Q are also highest among networks. Other networks are almost connected with the LCC’s size of more than 99% of N. Finally, we compute the new metric <r> that characterizes the influence of network link weights to the ranking of nodes’ betweenness, where <r> is the ratio of pair of nodes whose relative betweenness changes when weights are included. Concretely,(1)<r>=1N·N−1∑i≠j∈GΙbeti>betjandwbeti<wbetjorbeti<betjandwbeti>wbetj,where N is the total number of nodes of network G, beti (wbeti) is the betweenness (weighted betwennness) of node i and I{} is the indicator function. In other words, higher <r> indicates that the inclusion of link weights changes the node betweenness centrality ranking.


## 4. The Network Robustness Measures

We used two measures of network robustness along the nodes attack process, e.g., the size of the largest connected cluster (LCC) and the weighted efficiency (WEFF). The LCC is a simple indicator evaluating the binary-topological connectivity of the network nodes.The network efficiency (WEFF) is introduced by [35] with the goal to account the network information delivery rate in the network. WEFF is the average of the sum of the inverse of the weighted shortest paths (WSP) among nodes:(2)WEFF=1N⋅N−1∑i≠j∈G1di,j,where N is the total number of nodes of network G and d(i, j) is the length of the WSP between node i and node j.The WEFF is a measure that considers the difference in link weights in the evaluation of the weighted network functioning (integrity) and can be viewed like an indicator of how efficiently the network nodes exchange information [19, 35]. Recently, the network efficiency has been used to evaluate and compare the efficacy of different nodes attack strategy for weighted networks [27, 36, 37].In addition, for each attack strategy, we compute a single value defined as the network robustness (R) as done in [37]. The value of R corresponds to the area below the curve of the system functioning indicators (LCC and WEFF) against the fraction of nodes removed. We denote RLCC and RWEFF as the network robustness when using LCC and WEFF functioning indicators, respectively.


## 5. Results

### 5.1. Efficacy of the Attack Strategies with LCC

We found that the CondBet is the best strategy to minimize RLCC for all the five networks (Figure 2 and Table 2). This outcome confirms the highest efficacy of this strategy into fragment the LCC [22]. CondWBet is the second best strategy to fragment the LCC outperforming the WBet counterpart in all the network (Figure 2). We can see that, at the end of the removal process, the nodes betweenness centrality strategies such as Bet and WBet become inefficient, especially in the SP500_2 and NetScience networks (Figure 3). The Bet and WBet nodes attack strategies get stuck in a fully connected LCC and are not able to break it for a long fraction of removals. In fact, both binary (Bet) and weighted (WBet) nodes betweenness centrality inside a fully connected LCC are zero for all the nodes (because all the paths inside this subnetwork are shortest paths); thus, the Bet and WBet strategies are not able to select nodes and fragment the LCC. In Figure 3, we compare the LCC size after removing a fraction q of nodes by the attack strategies outlining the conditional strategies CondBet and CondWBet as the best to attack the LCC; this is because they are able to select the most important nodes during the entire removal process.Figure 2
The single value network robustness (R) for LCC (a) and WEFF (b) for each network and strategy. To easily compare the efficacy of the strategies, we normalized R by the max robustness value produced by a strategy for that network.
(a)(b)Table 2
The most efficient nodes attack strategy for the five real-world weighted networks.
NetworkBest strategy to reduce RLCCBest strategy to reduce RWEFFSP500_1CondBetCondWBetSP500_2CondBetCondBetNetScienceCondBetStrengthBitcoinCondBetCondWBetUSAirportCondBetCondWBetFigure 3
Normalized largest connected cluster (LCC) and weighted efficiency (WEFF) as a function of the fraction of removed nodes (q) under different attack strategies: (a, b) the SP500 threshold network from Feb. 1993 to Feb. 1996 (SP500_1), (c, d) the SP500 threshold network from May 1999 to May 2002 (SP500_2), (e, f) the co-authors network (NetScience), (g, h) the Bitcoin trust network, and (i, j) the USAirport network.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Moreover, we find that including link weights as done in the Strength, WBet, and CondWBet worsens the efficacy of the strategies with respect to their corresponding nonweighted strategy counterpart (Deg, Bet, and CondBet, respectively) (Figures2 and 3). For example, in the SP500_2 network, the removal of q = 4% nodes by CondBet strategy triggers the faster network fragmentation with respect the same nodes removal fraction performed by the CondWBet (Figure 4). In Figure 4, we can see that the CondBet strategy is able to fragment the network isolating a large cluster, thus producing a sharper LCC decrease. This would suggest that, for the networks analyzed here, adding information about link weights may degenerate the efficacy of the attack strategies to select important nodes supporting the simple binary-topological connectivity (measured by the LCC). In fact, the link weights structure may induce the weighted attack strategies to remove nodes; hence, it is important for network functioning, not playing a major role in shaping the topological network connectivity. As we may expect, this effect is more important for networks with high <r> value (the SP500_1, SP500_2, and the USAirport).Figure 4
Topological structure of the SP500_2 network atq = 4% attacked by (a) the CondWBet strategy and (b) the CondBet strategy. The CondBet strategy is more effective to fragment the network isolating a large cluster, thus producing a sharper LCC decrease than the weighted counterpart CondWBet.
(a)(b)


## 5.1. Efficacy of the Attack Strategies with LCC

We found that the CondBet is the best strategy to minimize RLCC for all the five networks (Figure 2 and Table 2). This outcome confirms the highest efficacy of this strategy into fragment the LCC [22]. CondWBet is the second best strategy to fragment the LCC outperforming the WBet counterpart in all the network (Figure 2). We can see that, at the end of the removal process, the nodes betweenness centrality strategies such as Bet and WBet become inefficient, especially in the SP500_2 and NetScience networks (Figure 3). The Bet and WBet nodes attack strategies get stuck in a fully connected LCC and are not able to break it for a long fraction of removals. In fact, both binary (Bet) and weighted (WBet) nodes betweenness centrality inside a fully connected LCC are zero for all the nodes (because all the paths inside this subnetwork are shortest paths); thus, the Bet and WBet strategies are not able to select nodes and fragment the LCC. In Figure 3, we compare the LCC size after removing a fraction q of nodes by the attack strategies outlining the conditional strategies CondBet and CondWBet as the best to attack the LCC; this is because they are able to select the most important nodes during the entire removal process.Figure 2
The single value network robustness (R) for LCC (a) and WEFF (b) for each network and strategy. To easily compare the efficacy of the strategies, we normalized R by the max robustness value produced by a strategy for that network.
(a)(b)Table 2
The most efficient nodes attack strategy for the five real-world weighted networks.
NetworkBest strategy to reduce RLCCBest strategy to reduce RWEFFSP500_1CondBetCondWBetSP500_2CondBetCondBetNetScienceCondBetStrengthBitcoinCondBetCondWBetUSAirportCondBetCondWBetFigure 3
Normalized largest connected cluster (LCC) and weighted efficiency (WEFF) as a function of the fraction of removed nodes (q) under different attack strategies: (a, b) the SP500 threshold network from Feb. 1993 to Feb. 1996 (SP500_1), (c, d) the SP500 threshold network from May 1999 to May 2002 (SP500_2), (e, f) the co-authors network (NetScience), (g, h) the Bitcoin trust network, and (i, j) the USAirport network.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Moreover, we find that including link weights as done in the Strength, WBet, and CondWBet worsens the efficacy of the strategies with respect to their corresponding nonweighted strategy counterpart (Deg, Bet, and CondBet, respectively) (Figures2 and 3). For example, in the SP500_2 network, the removal of q = 4% nodes by CondBet strategy triggers the faster network fragmentation with respect the same nodes removal fraction performed by the CondWBet (Figure 4). In Figure 4, we can see that the CondBet strategy is able to fragment the network isolating a large cluster, thus producing a sharper LCC decrease. This would suggest that, for the networks analyzed here, adding information about link weights may degenerate the efficacy of the attack strategies to select important nodes supporting the simple binary-topological connectivity (measured by the LCC). In fact, the link weights structure may induce the weighted attack strategies to remove nodes; hence, it is important for network functioning, not playing a major role in shaping the topological network connectivity. As we may expect, this effect is more important for networks with high <r> value (the SP500_1, SP500_2, and the USAirport).Figure 4
Topological structure of the SP500_2 network atq = 4% attacked by (a) the CondWBet strategy and (b) the CondBet strategy. The CondBet strategy is more effective to fragment the network isolating a large cluster, thus producing a sharper LCC decrease than the weighted counterpart CondWBet.
(a)(b)


## 6. Efficacy of the Attack Strategies with WEFF

When the goal is to minimize RWEFF, the CondWBet strategy is the best strategy in 3 out of 5 networks (Figure 3, Table 2). The CondWBet is highly effective to reduce the network efficiency (WEFF), because it is able to remove the nodes passing the most of the weighted shortest paths in the network (equation (2)). For this reason, when removing the nodes with highest weighted betweenness, we trigger the disruption of many weighted shortest paths in the network with a quick WEFF decrease. Furthermore, CondWBet is more efficient than the classic betweenness strategy WBet for all networks. This can be explained by the ability of CondWBet to select nodes only inside the LCC at the end of the removal process when the LCC may be fully connected, thus providing further efficacy with respect classic WBet.For the SP500_2, the efficacy difference between CondBet and CondWBet to reduce WEFF is very low, with almost negligible advantage of the CondBet strategy (Figures2 and 3). For this reason, we can consider CondBet and CondWBet roughly equally performing, with negligible difference due to some less important effect.Differently, in the NetScience network, the Strength is clearly the best strategy to decrease WEFF. The highest efficacy of the Strength strategy for the NetScience network can be explained by the peculiar embedding of the highest weight links (strong links). The NetScience is the social network of co-authorship, where nodes are scholars, and links weights indicate the number of common papers. In this network, the strong links occur between senior and most prolific scholars leading different research groups; i.e., the strong links act as bridges between different research communities [36, 38]. The nodes of higher strength are these senior scholars publishing many papers and holding the collaborations with different research groups. For this reason, when removing nodes of higher strength in the NetScience network, we remove strong links (playing a major role into shaping WEFF) and at the same time, we delete the bridge links between communities, producing abrupt collapses of WEFF (Figure 5).Figure 5
Topological structure of the NetScience network at (a) the beginning and (b) following theq = 2% of node removal by Strength strategy. The thicker links in the left panel indicate the links of highest weight (strong links representing higher number of common papers) occurring between most prolific scholars. The removal of the 2% of the higher strength nodes produces both the network fragmentation and the deletion of the strong links thus inducing an abrupt WEFF decrease.
(a)(b)Last, we find an interesting “efficacy transition” between CondBet/CondWBet and Strength strategies for all the networks; i.e., at the beginning of the removal process, CondBet/CondWBet are the best strategies, whereas, at the end of the removal process, Strength strategy shows the highest efficacy into reducing WEFF (Figure6). This may be explained by the fact that when the network is broken apart in many small clusters, the nodes betweenness-based strategies would become ineffective to produce a significant further network fragmentation. For this reason, at this stage by selecting the highest strength nodes, we can intercept the remaining strong links that play the major contribution in shaping the network efficiency (WEFF). For example, USAirport network is mostly broken and contains a large number of small clusters as soon as q = 7% (Figure 6). At this stage, the betweenness-based strategies CondBet/CondWBet lose their global ability to intercept nodes bridge, and the Strength strategy that removes nodes with highest link weights becomes the most efficacy strategy for reducing WEFF. Thus, before the transition, the CondBet/CondWBet are the most efficacy strategies and after this transition, when the network is broken into many small clusters, the Strength strategy is the best one for the remaining removal process. This situation can be better illustrated by a sample network as shown in Figure 1. We have a small network of 9 nodes, with node A being less connected than node B, but its links have much higher weight than those of node B. If attacked by the CondBet/CondWBet, node B will be removed; however, the remaining WEFF is still higher than that if node A is removed, because of higher strength of the node A. In such case, the most efficient strategy must be the Strength strategy that removes node A of higher strength in the network.Figure 6
The weighted efficiency (WEFF) as a function of the fraction of removed nodes (q) under three most efficacy attack strategies: Strength, CondBet, and CondWBet. (a) SP500_1, (b) SP500_2, (c) NetScience, (d) Bitcoin, and (e) US Airports. The transition between phases is marked by the red crosses. The inserts show a magnification of the transition (except for NetScience where this transition is clear).
(a)(b)(c)(d)(e)As a consequence, we can infer a general result for which, when the network is broken enough, the Strength strategy may be one of the best strategies to decrease the network efficiency (WEFF). The transition point values are summarized in Table3 and the topological images of each network at this point are shown in Figure 7. Further observations that are specific to each real-world network are presented in the Appendix.Table 3
Fraction of removed nodesq range corresponding to the transition when the Strength strategy becomes more efficient than other strategies.
SP500_1SP500_2NetScienceBitcoinUSAirportApproximate range of the fraction of removed nodesq when the transition happens0.670.660.040.120.07Overall highest efficacy strategy for reducing RWEFFCondWBetCondBetStrengthCondWBetCondWBetThe overall highest efficacy strategy with minimum RWEFF for each real-world networks is shown in the last row. See Figures 4–5 for more details.Figure 7
The topological image of the each networks in the beginning of the removal process where the conditional betweenness strategies CondBet/CondWBet are the most efficacy strategies (left column); at the transition point when the network are broken in many small clusters and the Strength strategy becomes the most efficacy for the remaining nodes removal process (right column).


## 7. Conclusion

In this work, we studied the efficacy of different nodes attack strategies on real-world complex networks adopting different measures of the network functioning, both accounting the binary-topological connectedness and the link weights structure of the network. We used both classic topological-binary attacks and introduced new attacks based on weighted properties of the nodes and found that the recently introduced conditional attack strategy (CondBet) still outperforms the other strategies to break the LCC in all the 5 networks, confirming the highest effectiveness of this strategy [22]. Furthermore, the inclusion of link weighs into nodes attack strategy results in a lower efficacy when the goal is to reduce the LCC. This would suggest that adding information about link weights may degenerate the efficacy of the attack strategies to select important nodes supporting the simple binary-topological connectivity (LCC).Secondly, when measuring the network functioning with the network efficiency WEFF, we find that, in 3 out of 5 networks, the newly introduced conditional weighted betweenness strategy CondWBet outperforms all other strategies, showing that, with the aim to select the most important nodes in real networks, it is necessary to consider the link weights. Further analysis shows that if the target is to decrease WEFF, the node attack process can be divided into two phases: in the first phase, when the network is well connected, the CondBet/CondWBet are the most efficient. If the correlation between the links’ weight and the node betweenness is low (i.e., high <r>), and the network modularity is high, the inclusion of weight may avoid the removal of important bridge node by CondWBet, decreasing the efficacy of this strategy; in the second phase, the Strength shows the highest efficacy because when the network is broken into many small clusters, the Strength strategy may break the most important cluster, thus being the best one to decrease the network efficiency (WEFF). The best strategy would be therefore a result of the balance between these two node attack strategies.These last outcome would suggest that a better attacking strategy for real-world weighted networks could be a combination of CondBet/CondWbet and Strength. However, an analytic model is necessary to determine the transition time and construct the combined strategy. Our work may help best design the attack strategy, or inversely design a more robust weighted network structure in practice.



---

*Source: 1677445-2021-10-15.xml*