The sensitivity of networks to the removal of vertices has been studied extensively over the last 15 years. A common approach to measuring this sensitivity is (i) successively removing vertices following a specific removal strategy and (ii) comparing the original and the modified network using a specific comparison method. In this paper we apply a wide range of removal strategies and comparison methods in order to study the sensitivity of medium-sized networks from the real world and randomly generated networks. In the first part of our study we observe that social networks and web graphs differ in sensitivity. When removing vertices, social networks are robust, web graphs are not. This effect is consistent with the work of who analyzed very large social networks and web graphs. For randomly generated networks we find that their sensitivity depends significantly on the comparison method. The choice of removal strategy has surprisingly marginal impact on the sensitivity for removal strategies derived from common centrality measures. However, the removal strategy has a strong impact when removing the vertices in random order.
Albert and Barabási @cite_12 examined the error and attack tolerance of random graphs with respect to node removal. Based on centrality measures, @cite_7 removed nodes and edges from real-world networks and random graphs to investigate the attack vulnerability regarding the average inverse of the geodesic length and the size of the largest connected subgraph. The behavior of very large social networks and web graphs with respect to vertex removal based on various removal strategies and comparison methods based on the neighborhood function has been studied by @cite_6 . @cite_26 measured the impact of random errors to real-world networks and generated graphs by means of stochastic quantifiers.
@cite_26 @cite_7 @cite_12 @cite_6
1967385589 2025550035 2327083405 2032332507
We study the response of complex networks subject to attacks on vertices and edges. Several existing complex network models as well as real-world networks of scientific collaborations and Internet traffic are numerically investigated, and the network performance is quantitatively measured by the average inverse geodesic length and the size of the largest connected subgraph. For each case of attacks on vertices and edges, four different attacking strategies are used: removals by the descending order of the degree and the betweenness centrality, calculated for either the initial network or the current network during the removal procedure. It is found that the removals by the recalculated degrees and betweenness centralities are often more harmful than the attack strategies based on the initial network, suggesting that the network structure changes as important vertices or edges are removed. Furthermore, the correlation between the betweenness centrality and the degree in complex networks is studied. We study the tolerance of random networks to intentional attack, whereby a fraction @math of the most connected sites is removed. We focus on scale-free networks, having connectivity distribution @math , and use percolation theory to study analytically and numerically the critical fraction @math needed for the disintegration of the network, as well as the size of the largest connected cluster. We find that even networks with @math , known to be resilient to random removal of sites, are sensitive to intentional attack. We also argue that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, @math , as @math , rather than as @math , as expected for random networks away from criticality. We study the stability of random scale-free networks to degree-dependent attacks. We present analytical and numerical results to compute the critical fraction @math of nodes that need to be removed for destroying the network under this attack for different attack parameters. We study the effect of different defense strategies, based on the addition of a constant number of links on network robustness. We test defense strategies based on adding links to either low degree, middegree or high degree nodes. We find using analytical results and simulations that the middegree nodes defense strategy leads to the largest improvement to the network robustness against degree-based attacks. We also test these defense strategies on an internet autonomous systems map and obtain similar results. In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model. Appears in Phys. Rev. E 60, 7332-7342 (1999).