Conditional attack strategy for real-world complex networks

Quyen Nguyen, H.D. Pham, D. Cassi and M. Bellingeri

Physica A: Statistical Mechanics and its Applications, 2019, vol. 530, issue C

Abstract: 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.

Keywords: complex network; Intentional attack; Betweenness centrality; Largest connected clustered (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119309240
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:530:y:2019:i:c:s0378437119309240

DOI: 10.1016/j.physa.2019.121561

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().