Efficiency of Scale-Free Networks: Error and Attack Tolerance

Abstract

The concept of network efficiency, recently proposed to characterize the properties of small-world networks, is here used to study the effects of errors and attacks on scale-free networks. Two different kinds of scale-free networks, i.e. networks with power law P(k), are considered: 1) scale-free networks with no local clustering produced by the Barabasi-Albert model and 2) scale-free networks with high clustering properties as in the model by Klemm and Eguiluz, and their properties are compared to the properties of random graphs (exponential graphs). By using as mathematical measures the global and the local efficiency we investigate the effects of errors and attacks both on the global and the local properties of the network. We show that the global efficiency is a better measure than the characteristic path length to describe the response of complex networks to external factors. We find that, at variance with random graphs, scale-free networks display, both on a global and on a local scale, a high degree of error tolerance and an extreme vulnerability to attacks. In fact, the global and the local efficiency are unaffected by the failure of some randomly chosen nodes, though they are extremely sensititive to the removal of the few nodes which play a crucial role in maintaining the network's connectivity.

23 pages, 10 figures

References in corpus (8)

• Statistical mechanics of complex networks
• Lethality and centrality in protein networks
• Efficient Behavior of Small-World Networks
• The Web of Human Sexual Contacts
• Is the Boston subway a small-world network ?
• Highly clustered scale-free networks
• Growing Scale-Free Networks with Small World Behavior
• The network topology of a potential energy landscape: A static scale-free network

Cited by in corpus (36)

• The structure and dynamics of multilayer networks
• A model for cascading failures in complex networks
• Modeling Cascading Failures in the North American Power Grid
• Robustness and resilience of complex networks
• Vulnerability and Protection of Critical Infrastructures
• Combining complex networks and data mining: why and how
• A spectrum of routing strategies for brain networks
• Topology and correlations in structured scale-free networks
• Complex networks vulnerability to module-based attacks
• A limited resource model of fault-tolerant capability against cascading failure of complex network
• Measure for degree heterogeneity in complex networks and its application to recurrence network analysis
• Emergent failures and cascades in power grids: a statistical physics perspective
• Optimization of network structure to random failures
• Information Theory Perspective on Network Robustness
• Effect of edge removal on topological and functional robustness of complex networks
• Resumption of dynamism in damaged networks of coupled oscillators
• Evolving efficiency and robustness of global oil trade networks
• Identifying time dependence in network growth
• Topological Analysis and Mitigation Strategies for Cascading Failures in Power Grid Networks
• Preferential attachment with information filtering - node degree probability distribution properties
• The effect of randomness for dependency map on the robustness of interdependent lattices
• Link deletion in directed complex networks
• Failure mechanisms of load sharing complex systems
• Integrating fluctuations into distribution of resources in transportation networks
• Duality between preferential attachment and static random networks on hyperbolic spaces
• Performance of attack strategies on modular networks
• Degree and component size distributions in generalized uniform recursive tree
• Using complex networks to model 2-D and 3-D soil porous architecture
• Information Propagation Analysis of Social Network Using the Universality of Random Matrix
• How the planned V0 railway line would increase the resilience of the railway network of Hungary against attacks
• Towards Limited Scale-free Topology with Dynamic Peer Participation
• Detrended fluctuation analysis on the correlations of complex networks under attack and repair strategy
• Inference of the Russian drug community from one of the largest social networks in the Russian Federation
• Macroscopic and Microscopic Characteristics of Networks with Time-variant Functionality for Evaluating Resilience to External Perturbations
• Modelling China's Credit System with Complex Network Theory for Systematic Credit Risk Control
• Graph Metrics for Internet Robustness -- A Survey