Conditional attack strategy for real-world complex networks

When attacking a real-world complex network, the removing strategy based on recalculated nodes betweenness centrality (Bet) is usually the best strategy for reducing the size of the largest connected component (LCC). In particular during the early stage of the removing process, the Bet strategy can reduce the size of LCC by a order of magnitude smaller than all other common strategies. However, near the end of this process, it can be less efficient and fail to completely break the network before other strategies. We found that this limit has origin from the nature of the betweenness centrality’s definition: when a subgraph is very well connected, the betweenness of their nodes is very small and if it is a complete subgraph (a clique), the betweenness centrality of all nodes is zero. In consequence, when the network becomes fragmented and the largest connected component is (or closed to) a complete graph, the betweenness strategy will almost ignore it and remove nodes elsewhere, thus making the size of the LCC unchanged. Therefore, we propose a modified strategy that remove the highest betweenness node (global) conditioned on whether the node is in the LCC. If it is not, the strategy will seek inside the LCC and remove the one with the highest betweenness (local). We analyzed the efficacy of this strategy for several real-world complex networks and found that it is consistently the most efficient for all networks and for all time during the attacking process. Finally, we analyze the relationship between the relative efficiency of the betweenness centrality with respect to other strategies and the network’s clustering structure. We found that real-world complex networks owing to higher clustering are more vulnerable to the Bet attack strategy. We show this relation by comparing different social networks, and then comparing two financial networks (SP500) sampled at different times that present the same number of nodes but different clustering coefficient level. This work sheds light on the design of a more robust network and as an initial speculative example, we propose a “toy model network” that after an initial node attack presents peculiar robustness properties against to both degree and betweenness attack.