Error and attack tolerance of complex networks

Tolerance against failures and errors is an important feature of many complex networked systems [1,2]. It has been shown that a class of inhomogeneously wired networks called scale-free[1,3] networks can be surprisingly robust to failures, suggesting that socially self-organized systems such as the World-Wide Web, the Internet, and other kinds of social networks [4] may have significant tolerance against failures by virtue of their scale-free degree distribution. I show that ...

It is a mainstream idea that scale-free network would be fragile under the selective attacks. Internet is a typical scale-free network in the real world, but it never collapses under the selective attacks of computer viruses and hackers. This phenomenon is different from the deduction of the idea above because this idea assumes the same cost to delete an arbitrary node. Hence this paper discusses the behaviors of the scale-free network under the selective node attack with dif...

Complex networks describe a wide range of systems in nature and society, much quoted examples including the cell, a network of chemicals linked by chemical reactions, or the Internet, a network of routers and computers connected by physical links. While traditionally these systems were modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks is governed by robust organizing principles. Here we review the recent advances in the f...

Error tolerance and attack vulnerability are two common and important properties of complex networks, which are usually used to evaluate the robustness of a network. Recently, much work has been devoted to determining the network design with optimal robustness. However, little attention has been paid to the problem of how to improve the robustness of existing networks. In this paper, we present a new parameter alpha, called enforcing parameter, to guide the process of enhanci...

The scale-fee networks, having connectivity distribution $P(k)\sim k^{-\alpha}$ (where $k$ is the site connectivity), is very resilient to random failures but fragile to intentional attack. The purpose of this paper is to find the network design guideline which can make the robustness of the network to both random failures and intentional attack maximum while keeping the average connectivity $<k>$ per node constant. We find that when $<k>=3$ the robustness of the scale-free n...

We study the detailed mechanism of the failure of scale-free networks under intentional attacks. Although it is generally accepted that such networks are very sensitive to targeted attacks, we show that for a particular type of structure such networks surprisingly remain very robust even under removal of a large fraction of their nodes, which in some cases can be up to 70%. The degree distribution $P(k)$ of these structures is such that for small values of the degree $k$ the ...

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 pro...

Previous studies on the invulnerability of scale-free networks under edge attacks supported the conclusion that scale-free networks would be fragile under selective attacks. However, these studies are based on qualitative methods with obscure definitions on the robustness. This paper therefore employs a quantitative method to analyze the invulnerability of the scale-free networks, and uses four scale-free networks as the experimental group and four random networks as the cont...

The vulnerability of networks to targeted attacks is an issue of widespread interest for policymakers, military strategists, network engineers and systems biologists alike. Current approaches to circumvent targeted attacks seek to increase the robustness of a network by changing the network structure in one way or the other, leading to a higher size of the largest connected component for a given fraction of nodes removed. In this work, we propose a strategy in which there is ...

The structure of complex networks in previous research has been widely described as scale-free networks generated by the preferential attachment model. However, the preferential attachment model does not take into account the detailed topological property observed in real networks. Here we propose the models of scale-free networks which can reproduce the topological assortativity of real networks. With an identical degree distribution and network size, we study the structural...