Attacks on high-betweenness nodes induce abrupt percolation transitions on random networks

PEROTTI, J. I.; ALMEIRA, NAHUEL; BILLONI, ORLANDO V.

Conferencia; IUPAP, 27th Internacional Conference on Statistical Physics; 2019

Many complex systems can be described by networks, in which nodes represent the constituent components and edges represent connections between them. A fundamental issue concerning networked systems is their robustness to the failure of its elements. Since the degree to which the system continues functioning, as its components are degraded, typically depends on the integrity of the underlying network, the question of system robustness can be addressed by analyzing how the network structure changes as nodes are removed. Of special importance is the case of directed attacks, where nodes are removed in decreasing order ofimportance. Node importance is typically identified using centrality measures, such as its degree or betweenness. Networks with a broad degree distribution are fragile against attacks on their hubs. On the other hand, homogeneous networks are expected to be more robust. There exist, nonetheless, exceptions to this rule; real systems such as power grids and road networks are very fragile against attacks, in spite of being homogeneous in terms of their degree. It has been argued that betweenness heterogeneity, rather than degree heterogeneity, is the cause of network vulnerability. Indeed, scale-free networks have long-tailed betweenness distribution, as it happens with the two homogeneous networks mentioned before. In this work, we perform a systematic analysis of the robustness of random homogeneous networks studying the percolation transition induced by a betweenness-based attack on their nodes. We found that,when a small fraction of nodes is removed, this attack has a very poor performance, approximating random deletion, but there exists a critical fraction after which the network undergoes an abrupt transition, suddenly becoming disconnected. Similar transitions have been previously found in the context of explosive percolation under different dynamic rules, and in cascading dynamics on interdependent networks. Awareness of these transitions is of importance in the prediction and understanding of catastrophic events such as blackouts, severe traffic congestion, and desertification processes.