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.

During the late 1990s, the advancement and popularity of computers (in particular PCs) changed our understanding of complex networks. The availability and power of computers made it possible to gather huge databases of network structures and to analyze them quickly and efficiently. This allowed, for the first time, the comparison of real network data with the existing models, and, in particular, the ER model. Another significant influence of the computing revolution was the creation of two huge and rapidly developing networks: the Internet and the World Wide Web (WWW).

Real-world complex networks

Below, we present a few examples of real-world networks, many of which are well approximated by a scale-free degree distribution. Many other examples that exist may be found in the recent literature (see e.g. [AB02, BBV08, BLM+06, DM03, New02b, PV03]).

Computer networks and the Internet

Computer networks are good candidates for studying the role they play in the Internet. The connections in this case are physical – a link exists between two nodes (computers) in the network if they are physically connected by a cable (usually copper or optical fiber, although some other connection types, such as satellites, exist). Various sizes of networks exist, ranging from a simple LAN (local area network) – where usually a small number of computers are all connected together – to wide area networks (WANs), which may consist of tens of thousands of computers.

Introduction

The study of the spread of epidemics is based on the notion that a disease is conveyed by contact between an infected individual and an uninfected individual who is susceptible to the disease. An endemic state is reached if a finite fraction of the population is infected. A state where (almost) all the population is infected is called a pandemic state. Similarly, this notion may describe the spread of a computer virus through a network of computers.

In previous chapters we surveyed the subject of attacks on networks, by targeting individuals either randomly or intentionally. In particular, the Internet and the WWW were shown to be robust to random breakdowns and vulnerable to targeted attacks, due to their broad distribution of node degrees. However, these chapters focused on the results of damaging computers by an outside source, and did not take into account the possibility of propagation of a problem throughout the connections among individuals in a population or among computers in a network, by way of the spreading of a disease or a computer virus.

Several models have been proposed for epidemic dynamics, differing in the disease stages, the dynamical parameters, and the underlying structure of contacts (see [AM92] for a survey). The most common models for disease dynamics are the susceptible–infected–recovered (SIR), susceptible–infected–susceptible (SIS), and susceptible–infected–recovered-susceptible (SIRS) models, which represent the stages of the disease for each individual in a network.

Introduction

A generalized random network is generally made up of several components. In the random generalized graph model, the structure of the network is determined only by the degree distribution, since no other structure or constraint is imposed on the network. In general, for many degree distributions the network is composed of many separate components, i.e., groups of nodes connected internally, but disconnected from other components. In each such component there exists a path between any two nodes, but there is no path between nodes in different components. When there is a component with size (the number of nodes) proportional to that of the entire network, it is called the giant component (sometimes also referred to as the infinite component or giant cluster or percolating cluster).

This chapter introduces a method for determining the component structure of a network, which is one of its most important structural properties. We will present a method for determining the existence of a giant component, and also a method for determining the sizes of all clusters using generating functions. The generating function method is a general and useful method for many probabilistic and combinatorial problems. An introduction to this method is given in Appendix A. The methods introduced in this chapter will be used in Chapter 10 to determine the robustness properties of networks and later in Chapters 14 and 15 to determine how epidemics propagate through networks and how they can be prevented by immunization.

Introduction

It is well known [AJB99, Bol85, CL01, BNKM01] that random networks, such as Erdős-Rényi networks [ER59, ER60] as well as partially random networks, such as small-world networks [WS98], have a very small average distance (or diameter) between nodes, which scales as d ˜ ln N, where N is the number of nodes. Since the diameter is small even for large N values, it is common to refer to such networks as “small-world” networks. Many natural and man-made networks have been shown to possess a scale-free degree distribution, including the Internet [FFF99], WWW [AJB99, BKM+00], metabolic [JTA+00] and cellular networks [JMBO01], as well as trust cooperation networks [GGA+02] and email networks [EMB02]. For more details, see Chapter 3.

The question of the diameter of such networks is fundamental. It is relevant in many fields regarding communication and computer networks, such as routing [GKK01b], searching [ALPH01], and transport of information [GKK01b]. All these processes become more efficient when the diameter is smaller (see, e.g., [LCH+06]). It might also be relevant to subjects such as the efficiency of chemical and biochemical processes and the spreading of viruses, rumors, etc. in cellular, social, and computer networks. In physics, the scaling of the diameter with the network size is related to the physical concept of the dimensionality of the system, and is highly relevant to phenomena such as diffusion, conduction, and transport in general.

Networks are present in almost every aspect of our life. The technological world surrounding us is full of networks. Communication networks consisting of telephones and cellular phones, the electrical power grid, computer communication networks, airline networks and, in particular, the world-wide Internet network are an important part of everyday life. The symbolic network of HTML pages and links – the World Wide Web (WWW) – is a virtual network that many of us use every day, and the list is long. Society is also networked. The network of friendship between individuals, working relations, or common hobbies, and the network of business relations between people and firms are examples of social and economic networks. Cities and countries are connected by road or airline networks. Epidemics spread in population networks. A great deal of interest has recently focused on biological networks representing the interactions between genes and proteins in our body. Ecological networks such as predator–prey networks are also under intensive study today. The physical world is also rich in network phenomena such as interactions between atoms in matter, between monomers in polymers, between grains in granular media, and the network of relations between similar configurations of proteins (i.e. between configurations that are in reach of each other by a simple move). Recently, studies have shown that polymer networks in real space can actually have a wide distribution of the branching factor, which is also similar to other real-world networks [ZKM+03].

Before 1960, graph theory mainly dealt with the properties of specific individual graphs. In the 1960s, Paul Erdős and Alfred Rényi initiated a systematic study of random graphs [ER59, ER60, ER61]. Some results regarding random graphs were reported even earlier by Rapoport [Rap57]. Random graph theory is, in fact, not the study of individual graphs, but the study of a statistical ensemble of graphs (or, as mathematicians prefer to call it, a probability space of graphs). The ensemble is a class consisting of many different graphs, where each graph has a probability attached to it. A property studied is said to exist with probability P if the total probability of a graph in the ensemble possessing that property is P (or the total fraction of graphs in the ensemble that has this property is P). This approach allows the use of probability theory in conjunction with discrete mathematics for studying graph ensembles. A property is said to exist for a class of graphs if the fraction of graphs in the ensemble which does not have this property is of zero measure. This is usually termed as a property of almost every (a.e.) graph. Sometimes the terms “almost surely” or “with high probability” are also used (with the former usually taken to mean that the residual probability vanishes exponentially with the system size).

Introduction

In this chapter we present studies of the optimal distance in networks, lopt, defined as the length of the path minimizing the total weight, in the presence of disorder [BBC+03]. Disorder is introduced by assigning random weights to the links or nodes. These weights may represent properties of the links and the transport in them. These properties may include the bandwidth of links in communication networks, delays in the transport of data or material, or the cost of traversing the link. Many real-world networks may be better described by introducing link weights, an example is the airline network where the frequency of flights is an important property (see, e.g., [BBPV04]).

An important quantity characterizing networks is the average distance (minimal hopping) lmin between two nodes in a network containing N nodes. For the Erdős- Rényi networks [ER59, ER60], and the related, more realistic Watts–Strogatz (WS) network [WS98], lmin scales as ln N [Bol85], which leads to the concepts of small world and “six degrees of separation,” while for scale-free networks lmin scales as ln ln N. See Chapter 6 for details.

In most studies, all links in the network are regarded as identical and thus the relevant parameter for information flow including efficient routing, searching, and transport is lmin. In practice, however, the weights (for example, the quality or cost) of links are usually not equal, and thus the length of the optimal path, lopt, minimizing the sum of weights is usually longer than the distance lmin.

One of the most important classes of network studied in the literature is biological networks. This class contains a large variety of naturally occurring networks, formed by the long course of evolution. The human (and animal) body contains a large number of networks, some of which occur in real space, such as the networks of blood vessels, the bronchi, and the nerve system. These networks have been studied for a long time, and many of them are known to be fractal objects, see, for example [BH94, BH96, WBE97]. Another class of network, on which we will focus in this chapter, is logical. These are the networks of gene–gene, gene–protein, and protein–protein interactions. A survey of networks in biology can be found, for example, in [BO04].

In the cell, the genetic information is stored in DNA strands sitting in the cell's nucleus. To pronounce the genetic information DNA is transcribed (copied) to messenger RNA by a protein called RNA polymerase. The messenger RNA is then translated by ribosomes, which form amino acids according to the information in the RNA. Every three letter sequence represents a single amino acid from the twenty amino acids existing in humans and most other known organisms. A chain of amino acids is then created from a sequence of letters and forms a protein. The protein folds into a minimal energy configuration, whose shape determines most of its biological function. The created proteins then interact with the genetic information in several ways.