In general, immunization can be seen as a site percolation problem. Each immunized individual can be regarded as a node that is removed from the network. The goal of the immunization process is to pass (or at least approach) the percolation threshold, leading to minimization of the number of infected individuals. The complete model of SIR and immunization can be considered as a site–bond percolation model, and the immunization is considered successful if the network is below the percolation threshold.

It is well established that immunization of randomly selected individuals requires immunizing a very large fraction, f, of the population, in order to arrest epidemics that spread upon contact with an infected individual [AJB00, AM92, CEbH00, HA87, MA84, PV01b, WY84]. Many diseases require 80%–100% immunization. For example, measles requires 95% of the population to be immunized [AM92]. The same is true for the Internet, where stopping computer viruses requires almost 100% immunization [AJB00, CEbH00, KWC93, PV01b]. On the other hand, targeted immunization of the most highly connected individuals [AJB00, AM92, CEbH01, CNSW00, LM01, PV02], while effective, requires global information about the network in question, rendering it impractical in many cases.

In this chapter we present a mathematical model and propose an effective strategy, based on the immunization of a small fraction of random acquaintances of randomly selected nodes [CHb03]. In this way, the most highly connected nodes are immunized, and the process prevents epidemics with a small finite immunization threshold and without requiring specific knowledge of the network.

Introduction

In this chapter we consider the behavior of some thermodynamic models on networks. Thermodynamic models attempt to describe the macroscopic (large-scale) properties of systems by their microscopic (small-scale) behavior. The microscopic behavior stems from the interactions between atoms or molecules in the material. In the nineteenth century a new branch in physics, called “statistical physics” or “statistical mechanics” appeared (mainly owing to the works of Gibbs, Maxwell and Boltzmann as well as later works by Einstein), which tried to explain the observed properties of materials (phase transitions, magnetism, heat capacity, pressure and temperature) by the behavior of the material at the microscopic level. These studies showed that the phenomena of heat and the material properties were not basic phenomena as thought before, but rather manifestations of the small-scale interactions in the material. The microscopic level interaction coupled with statistical analysis to describe the properties of large-scale samples could explain all these phenomena and account for the large differences between materials. A well-known example is the Ising model (see, e.g., [Bax82]), dating back to the early twentieth century, which tried to explain the phenomena of ferromagnetism (the formation of an internal macroscopic magnetic moment in materials) and the transition between paramagnetism and ferromagnetism.

In this appendix we will briefly describe probability theory and methods that will be used throughout the book. For a more complete treatment of probability theory, see any standard textbook on probability theory, such as [Fel68].

Probabilities and distributions

The main concept in probability theory is that of a probability space or an ensemble. The probability space consists of different objects or events, each of which has a measure – probability – assigned to it.

When each event is assigned a number, this number is termed a random variable. The random variable can be either discrete, in which case the measure is termed a probability distribution, or continuous, in which case the measure is termed “probability density.” The single events then have an extremely small probability of occurring and only the probability of a range of values, obtained through integration assuming that the probability density is finite.

When a finite number of events exists, say N events, the most common case is to assume they are equiprobable. Therefore, the probability of finding some property is P = M/N, where M is the number of events having the property. If P = 1 − f(N), where limN → ∞f (N) = 0, (i.e., the probability of finding the property approaches 1, when N becomes large) the property is said to hold almost always (or a.a.). In this book, when a property is said to hold, it actually means that it almost always holds.

Introduction

It is well known [BH96, SA94] that in grids and other organized lattices, in any dimension larger than one, a percolation phase transition occurs. The usual percolation model assumes that the sites (nodes) or bonds (links) in the lattice are occupied with some probability (or density), p, and unoccupied with probability q = 1 − p. The system is considered percolating if there is a path from one side of the lattice to the other, passing only through occupied links and nodes. When such a path exists, the component or cluster of sites that spans the network from side to side is called the spanning cluster or the infinite cluster The percolation phase transition occurs at some critical density pc that depends on the type and dimensionality of the lattice.

In networks no notion of side exists. However, as will be seen in this chapter, the ideas of percolation theory can still be applied to obtain useful results. The main difference compared to lattices is that the condition for percolation is no longer the spanning property, but rather the property of having a component (cluster) containing O(N) nodes, where N is the total original number of nodes in the network. Such a component, if it exists, is termed the giant component. The condition of the existence of a giant component above the percolation threshold and its absence below the threshold also applies to lattices, and therefore can be considered as more general than the spanning property.

Many properties of real-world networks have been considered so far: the degree distribution, clustering, diameter, etc. However, the treatment of these properties has been rather ad hoc, i.e., each new property found has been incorporated into a simple static model. This approach has several disadvantages.

1. • We cannot be sure that the ensemble we use is the correct one for the problem. Usually, we try to take the largest or simplest ensemble having the desired properties. However, this may not apply to real-world networks.

2. • Real-world networks are usually dynamical, whether over a short time span, such as the Internet and WWW, or over a long (evolutional) time span. The classes of networks discussed so far are static, and actually are distinct for each N. No dynamical evolution of the network is incorporated.

3. • The equilibrium models provide no indication as to why the network received its observed properties. So far, we have treated these properties as given.

In this chapter, we attempt to address these problems by presenting models for network creation and evolution. These growth models reproduce several observed properties of real-world networks using simple ideas. Most of these models are based on the simple Barabási–Albert model that is presented next.

In this chapter we discuss the spectral properties of networks, and their relation to dynamical properties such as diffusion. There are two main characteristic matrices for a graph, the adjacency matrix and the Laplacian. We discuss both of them and explain the relation to the dynamical properties. A good summary of results on the spectrum of networks can be found in [Chu97]. For a nice survey of random walks on graphs see [Lov96].

The spectrum of the adjacency matrix

As described in Chapter 1, the adjacency matrix, A, is an N × N matrix (where N is the number of nodes) whose entries are Ai, j = 1 if there is an edge between nodes i and j, and Ai, j = 0 otherwise. If the graph is not directed then the adjacency matrix is symmetric. In a directed graph it is not necessarily so.

The spectrum of this matrix is the collection of eigenvalues of the matrix. Since we refer to an ensemble of graphs rather than a single graph, we are interested in the distribution of eigenvalues when the entire ensemble is considered.

The study of the spectrum of random graphs is strongly related to the study of the spectrum of random matrices in general. The study of random matrix theory was initiated by Wigner [Wig55] in the 1950s. His main goal was to understand the energy levels of the nucleus. These levels are the eigenvalues of the Hamiltonian (energy) matrix.

In this chapter we present results for the robustness of complex networks under multiple waves of simultaneous targeted attacks in which the highest degree nodes are removed and random attacks (or failures), in which fractions pt and pr, respectively, of the nodes are removed until the network collapses [TPC+05]. It is shown that the network design, which optimizes network robustness, has a bimodal degree distribution, with a fraction r of the nodes having degree k2 = (
k‪ − 1 + r)/r and the remainder of the nodes having degree k1 = 1, where 
k‪ is the average degree of all the nodes. The optimal value of r approaches pt/pr for pt/pr ≪ 1.

Introduction

The resilience of real-world networks to random attacks or to attacks targeted at the highest degree nodes is of much interest [AJB00, CEbH00, CEbH01, CNSW00, Pax97, PSS05, VSS04]. Many real-world networks are robust to random attacks but vulnerable to targeted attacks on the most important nodes. It is important to understand how to design networks that are optimally robust against both types of attacks, with examples being terrorist attacks on physical networks and attacks by hackers on computer networks. In Chapter 10 we considered the case in which there was only one type of attack on a given network, that is, the network was subject to either a random attack or to a targeted attack but not subject to different types of attack simultaneously, which is a more realistic scenario.

We now address the geometrical properties of the networks, arising from their embedding in Euclidean space (see Section 4.6). For this purpose, it is useful to consider the spatial arrangement of the networks as measured both in a Euclidean metric and in chemical space. The chemical distance l between any two nodes is the minimal number of links between them (shortest path). Thus, if the distance between the two nodes is r, then l ˜ rdmin defines the shortest path exponent dmin. We will see that for scale-free networks embedded in d > 1 lattices, dmin < 1, contrary to all known fractals and disordered media where dmin ≥ 1. Nodes at chemical distance l from a given node constitute its lth chemical shell. Thus, the number of (connected) nodes within radius r scales as m(r) ˜ rdf, defining the fractal dimension df. Likewise, the number of (connected) nodes within chemical (hop) radius l scales as m(l) ˜ ldl, which defines the fractal dimension dl in chemical (hop) space. The two fractal dimensions are related: dmin = df/dl [BH96, bH00, SA94]. Note that dmin has a meaning only when the network is embedded in Euclidean space. In networks that are not embedded, the relation between M(l) and l exists, but it can only be a power law when the networks are fractals (Chapter 7) or at the percolation threshold (Chapter 10).

In this appendix we present efficient methods for simulating the networks discussed in the book and some efficient algorithms for analyzing their structure.

Simulation of generalized random graphs

To simulate general networks we have used the following algorithm.

1. (i) For each node choose a degree from the required distribution.

2. (ii) Create a list where each node is repeated as many times as the chosen degree.

3. (iii) Randomly choose pairs from the list and connect the chosen nodes (by storing for each node a list of neighbors, and adding each of the selected nodes node to the list of neighbors of the other node). Remove the chosen pair from the list (by replacing them with the last two entries in the list).

Double- and self-edges are ignored and if the number of entries in the list is odd (overall odd number of connections) one entry can also be discarded. This has aminor influence on the degree distribution if the network is large. Another possibility is to discard cases in which the sum of degrees is odd, and to rechoose the matching in case of a self loop or double-edge. Justification for the use of this algorithm for simulation and analysis as an algorithm generating the probability space of generalized random graphs can be found in [Bol80].

Many real complex networks have directed links, a property that affects the network's navigability and large-scale topology. Here we present the percolation properties of such directed scale-free networks with correlated in- and out-degree distributions [SCbA+02]. We derive a phase diagram that indicates the existence of three regimes, determined by the values of the degree exponents. In the first regime, we attain the known directed percolation mean-field exponents. In contrast, the second and third regimes are characterized by anomalous mean-field exponents that we calculate analytically. In the third regime the network is resilient to random dilution, i.e., the percolation threshold is pc → 0.

Introduction

Real networks are sometimes directed; for example, in social and economical networks, a node A gains information or acquires physical goods from node B, but node B does not necessarily get similar input from node A. Likewise, most metabolic reactions are one directional. Thus, changes in the concentration of molecule A affect the concentration of its product B, but the reverse is not true. Despite the directedness of many real networks, the modeling literature, with few notable exceptions [CRS+03, DMS01b, NSW01, SCbA+02], has focused mainly on undirected networks.

Introduction

One of the most important tasks in networks is searching for nodes when partial or no knowledge of their location is available. This task may be carried out in several different settings and may have many different applications. An example of searching in social networks was demonstrated in Stanley Milgram's famous experiment [Mil67], where individuals were requested to search for a path to other individuals chosen randomly from a phone book. The surprising conclusion of the experiment was that, on average, these random pairs of individuals were only separated by six nodes. However, another surprising result of the experiment was that the tested individuals were actually able to find such a short path easily in the complex network. A random walk on a network is expected to visit a large fraction of the nodes in the network before reaching the destination node. Nevertheless, the subjects of Milgram's experiment were able to locate the destination individuals with a number of steps near the actual network diameter. In this chapter we will discuss some aspects and techniques for searching nodes in complex networks.

Searching using degrees

In [ALPH01] a method is suggested for searching scale-free networks with exponent γ ≈ 2. More specifically, the following was suggested. Each node contains information not only on its neighbors, but also on its next nearest neighbors, the rationale being that the average number of next nearest neighbors diverges in networks with γ < 3, whereas the average number of nearest neighbors is a constant. The search itself is performed in two stages.

Introduction

In this chapter and the following one, we will discuss models for generating complex networks. These models describe the process of creating complex networks and thus also define probability spaces of random graphs. As expected, different methods of creation can lead to different classes of random graphs having completely different properties. We will discuss the properties of networks formed by some of these methods in the second part of this book. This chapter will mainly focus on static models, that is, models for building a complex network with a given set of nodes, and some wiring process (for connecting nodes by links), depending on the desired properties of the network.

It should be clarified that real networks are not random. Their formation and development are dictated by a combination of many different processes and influences. These influencing conditions include natural limitations and processes, human considerations such as optimal performance and robustness, economic considerations, natural selection and many others. Controversies still exist regarding the measure to which random models represent real-world networks. However, in this book we will focus on random network models and attempt to show how their properties may still be used to study properties of real-world networks.