A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, $P\left(k\right){=ck}^{-\alpha }$. We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, $p_c$, that needs to be removed before the network disintegrates. We show analytically and numerically that for $\alpha \le 3$ the transition never takes place, unless the network is finite. In the special case of the physical structure of the Internet $\left(\alpha \approx 2.5\right)$, we find that it is impressively robust, with $p_c>0.99\mathrm{}$.

We study the tolerance of random networks to intentional attack, whereby a fraction $p$ of the most connected sites is removed. We focus on scale-free networks, having connectivity distribution $P\left(k\right)\sim k^{-\alpha }$, and use percolation theory to study analytically and numerically the critical fraction $p_c$ needed for the disintegration of the network, as well as the size of the largest connected cluster. We find that even networks with $\alpha \le 3$, 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, $M$, as $\sqrt{M}$, rather than as ${log}_{k}M$, as expected for random networks away from criticality.

We present an effective immunization strategy for computer networks and populations with broad and, in particular, scale-free degree distributions. The proposed strategy, acquaintance immunization, calls for the immunization of random acquaintances of random nodes (individuals). The strategy requires no knowledge of the node degrees or any other global knowledge, as do targeted immunization strategies. We study analytically the critical threshold for complete immunization. We also study the strategy with respect to the susceptible-infected-removed epidemiological model. We show that the immunization threshold is dramatically reduced with the suggested strategy, for all studied cases.

We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k) proportional, variant k(-lambda), i.e., the probability of having k links outgoing from a site. In contrast to the diameter of regular random networks or small-world networks, which is known to be d approximately ln(N, we show, using analytical arguments, that scale-free networks with 23, d approximately ln(N. We also show that, for any lambda>2, one can construct a deterministic scale-free network with d approximately ln(ln(N, which is the lowest possible diameter.

Examining important results and analytical techniques, this graduate-level textbook is a step-by-step presentation of the structure and function of complex networks. Using a range of examples, from the stability of the internet to efficient methods of immunizing populations, and from epidemic spreading to how one might efficiently search for individuals, this textbook explains the theoretical methods that can be used, and the experimental and analytical results obtained in the study and research of complex networks. Giving detailed derivations of many results in complex networks theory, this is an ideal text to be used by graduate students entering the field. End-of-chapter review questions help students monitor their own understanding of the materials presented.

We study the behavior of scale-free networks, having connectivity distribution $P\left(k\right)\mathrm{}\sim k^{-\lambda },$ close to the percolation threshold. We show that for networks with $3<\mathrm{}\lambda <4,$ known to undergo a transition at a finite threshold of dilution, the critical exponents are different than the expected mean-field values of regular percolation in infinite dimensions. Networks with $2<\mathrm{}\lambda <3\mathrm{}$ possess only a percolative phase. Nevertheless, we show that in this case percolation critical exponents are well defined, near the limit of extreme dilution (where all sites are removed), and that also then the exponents bear a strong $\lambda$ dependence. The regular mean-field values are recovered only for $\lambda >4.\mathrm{}$