The kinetics of first-order phase transitions involves the separation of an initially one-phase system into two coexisting phases. The formation and coarsening of domains of the coexisting phases as the system evolves are of central interest. The phase segregation process is usually studied by first preparing the system in a region of the phase diagram where the homogeneous state is stable. The system is then suddenly quenched into the two-phase region, and segregation into domains of the two stable phases takes place. Such phase segregation arises in a variety of physical contexts, including binary alloys and fluid mixtures, ferromagnetic systems, superfluids, polymer mixtures, and chemically reacting fluids. The temperature– composition (T, c) phase diagram for a binary mixture composed of constituents A and B is shown in Fig. 2.1. For low enough temperatures, in the region bounded by the coexistence curve the binary mixture will segregate into A-rich and B-rich phases.

A quench that takes the system from a homogeneous to a two-phase region is often performed by changing temperature suddenly at fixed concentration. Such a quench from the one-phase state at high temperatures may be carried out either along the critical isoconcentration line that passes through the critical point (path a), or along off-critical paths (path b). Phase segregation may be monitored by the changes in the local concentration of the binary mixture. In general, the variable that signals the passage from the one-phase to two-phase regions is called the order parameter ø.

Many natural systems can be described as a collection of oscillators coupled to each other via an interaction matrix. Systems of this type describe phenomena as diverse as earthquakes, ecosystems, neurons, cardiac pacemaker cells, or animal and insect behavior. Coupled oscillators may display synchronized behavior, i.e. follow a common dynamical evolution. Famous examples include the synchronization of circadian rhythms and night/day alternation, crickets that chirp in unison, or flashing fireflies. An exhaustive list of examples and a detailed exposition of the synchronization behavior of periodic systems can be found in the book by Blekhman (1988) and the more recent reviews by Pikovsky, Rosenblum and Kurths (2001), and Boccaletti et al. (2002).

Synchronization properties are also dependent on the coupling pattern among the oscillators which is conveniently represented as an interaction network characterizing each system. Networks therefore assume a major role in the study of synchronization phenomena and, in this chapter, we intend to provide an overview of results addressing the effect of their structure and complexity on the behavior of the most widely used classes of models.

General framework

The central question in the study of coupled oscillators concerns the emergence of coherent behavior in which the elements of the system follow the same dynamical pattern, i.e. are synchronized. The first studies were concerned with the synchronization of periodic systems such as clocks or flashing fireflies.

Undeniably, the visualizations of the Internet or the airport network convey the notion of intricate, in some cases haphazard, systems of a very complicated nature. Complexity, however, is not the same as the addition of complicated features. Despite the fact that there is no unique and commonly accepted definition of complexity – it is indeed very unlikely to find two scientists sharing the same definition of complex system – we discuss from what perspectives many real-world networks can be considered as complex systems, and what are the peculiar features signaling this occurrence. In this chapter we review the basic topological and dynamical features that characterize real-world networks and we attempt to categorize networks into a few broad classes according to their observed statistical properties. In particular, self-organized dynamical evolution and the emergence of the small-world and scale-free properties of many networks are discussed as prominent concepts which have led to a paradigm shift in which the dynamics of networks have become a central issue in their characterization as well as in their modeling (which will be discussed in the next chapter). We do not aim, however, at an exhaustive exposition of the theory and modeling of complex networked structures since, as of today, there are reference textbooks on these topics such as those by Dorogovtsev and Mendes (2003), Pastor-Satorras and Vespignani (2004), and Caldarelli (2007), along with journal reviews by Albert and Barabási (2002), Dorogovtsev and Mendes (2002), Newman (2003c), and Boccaletti et al. ([2006]).

Statistical mechanics has long studied how microscopic interaction rules between the elements of a system at equilibrium are translated into its macroscopic properties. In particular, many efforts have been devoted to the understanding of the phase transition phenomenon: as an external parameter (for example the temperature) is varied, a change occurs in the macroscopic behavior of the system under study. For example, a liquid can be transformed into a solid or a gas when pressure or temperature are changed. Another important example of phase transition is by the appearance in various metallic materials of a macroscopic magnetization below a critical temperature. Such spontaneous manifestations of order have been widely studied and constitute an important paradigm of the emergence of global cooperative behavior from purely local rules.

In this chapter, we first recall some generalities and definitions concerning phase transitions and the emergence of cooperative phenomena. For this purpose we introduce the paradigmatic Ising model, which is a cornerstone of the statistical physics approach to complex systems and, as we will see in other chapters, is at the basis of several models used in contexts far from physics such as social sciences or epidemics. After a brief survey of the main properties of the Ising model, we show how the usual scenarios for the emergence of a global behavior are affected by the fact that the interactions between the microscopic elements define a complex network.

Although we have reviewed or mentioned more than 600 scientific works on equilibrium and non-equilibrium processes in complex networks, the present book is by no means intended as an exhaustive account of all research activities in network science. It would have been extremely easy to list more than twice as many scientific papers and, as we have stressed in several passages of this book, we have decided to focus our attention on that subset of network research that deals with dynamical processes in large-scale networks characterized by complex features such as largescale fluctuations and heterogeneities. This implies the selection of studies and approaches tailored to tackle the large-scale properties and asymptotic behavior of phenomena and, as a consequence, models that usually trade details and realism for generality and a high level of abstraction. This corresponds to a methodological approach that has its roots in statistical physics and has greatly contributed to generate an entire research area labeled in recent years as the “new science of networks” (Watts, 2004). As network science is an interdisciplinary endeavor, however, we do not want to overlook the criticisms raised by several authors to this “new science of networks” and to the statistical physics and complex systems approaches. These criticisms are articulated around several key points that are echoed in several commentaries and essays (see for instance Urry [2004], Keller [2005] and Mitzenmacher [2006]), and at the end of 12 long chapters we believe we are obliged to provide a discussion of some of these key points.

In this chapter we introduce the reader to the basic definitions of network and graph theory. We define metrics such as the shortest path length, the clustering coefficient, and the degree distribution, which provide a basic characterization of network systems. The large size of many networks makes statistical analysis the proper tool for a useful mathematical characterization of these systems. We therefore describe the many statistical quantities characterizing the structural and hierarchical ordering of networks including multipoint degree correlation functions, clustering spectrum, and several other local and non-local quantities, hierarchical measures and weighted properties.

This chapter will give the reader a crash course on the basic notions of network analysis which are prerequisites for understanding later chapters of the book. Needless to say the expert reader can freely skip this chapter and use it later as a reference if needed.

What is a network?

In very general terms a network is any system that admits an abstract mathematical representation as a graph whose nodes (vertices) identify the elements of the system and in which the set of connecting links (edges) represent the presence of a relation or interaction among those elements. Clearly such a high level of abstraction generally applies to a wide array of systems. In this sense, networks provide a theoretical framework that allows a convenient conceptual representation of interrelations in complex systems where the system level characterization implies the mapping of interactions among a large number of individuals.

The mathematical modeling of epidemics is a very active field of research which crosses different disciplines. Epidemiologists, computer scientists, and social scientists share a common interest in studying spreading phenomena and rely on very similar models for the description of the diffusion of viruses, knowledge, and innovation. Epidemic modeling has developed an impressive array of methods and approaches aimed at describing various spreading phenomena, as well as incorporating many details affecting the spreading of real pathogens. In particular, understanding and predicting an epidemic outbreak requires a detailed knowledge of the contact networks defining the interactions between individuals. The theoretical framework for epidemic spreading has thus to be widened with opportune models and methods dealing with the intrinsic system complexity encountered in many real situations.

In this chapter, we introduce the general framework of epidemic modeling in complex networks, showing how the introduction of strong degree fluctuations leads to unusual results concerning the basic properties of disease spreading processes. Using some specific examples we show how plugging in complex networks in epidemic modeling enables one to obtain new interpretative frameworks for the spread of diseases and to provide a quantitative rationalization of general features observed in epidemic spreading. We end the chapter by discussing general issues about modeling the spread of diseases in complex environments, and we describe metapopulation models which are at the basis of modern computational epidemiology.

In Chapter 6, the case of percolation and resilience of undirected graphs has been considered. Various authors have tackled the problem of its generalization to directed networks (Newman et al., 2001; Schwartz et al., 2002; Dorogovtsev et al., 2001a; Boguñá and Serrano 2005).

As seen in Chapter 1, directed networks are topologically richer and more complex than their undirected counterparts. The links attached to a node can be either incoming or outgoing. The number of in-links is the in-degree kin, and the number of out-links is the out-degree kout. Since some pairs of nodes can be linked by two directed links pointing in the opposite directions, it is also possible to distinguish between strictly incoming, strictly outgoing or bidirectional links, the total degree being the sum of their respective numbers ki, ko, kb, with kin = ki + kb and kout = ko + kb. The degree distribution is thus the joint distribution of these degrees. Most often, strictly directed networks are considered, with no bidirectional links: kb = 0. Note that by a simple conservation rule, the averages of ki and ko are then equal: 〈ki〉 = 〈ko〉. Each (weakly) connected component (WCC) of a directed graph has also an internal structure as described in Chapter 1, and is composed of a strongly connected component (SCC), an in and an out components, tendrils and tubes.

In this chapter we present a review of network models that will be used to study dynamical processes in the context of computational approaches. These different models will also help to determine the influence that specific network features have on the various phenomena that will be considered in the next chapters. To this end, we will discuss the different modeling approaches and put the activity focused on each of the different dynamical models into the proper perspective. Particular emphasis will be devoted to models which have been developed as theoretical examples of the different specific classes of real-world networks empirically observed.

Randomness and network models

Static random graph models and topology generators such as the paradigmatic Erdős–Rényi model (Erdős and Rényi, 1959; 1960; 1961) and the network generation algorithm of Molloy and Reed (1995) are the simplest network models to include stochasticity as an essential element. They are characterized by an absolute lack of knowledge of the principles that guide the creation of edges between nodes. Lacking any information, the simplest assumption one can make is to connect pairs of nodes at random with a given connection probability p. In its original formulation, an Erdős–Rényi graph GN, E is constructed starting from a set of N different vertices which are joined by E edges whose ends are selected at random among the N vertices.