Many of the networks around us continuously grow in time by the addition of new nodes and new links. One typical example is the network of the World Wide Web. As we saw in the previous chapter, millions of new websites have been created over recent years, and the number of hyperlinks among them has also increased enormously over time. Networks of citations among scientific papers is another interesting example of growing systems. The size of these networks constantly increases because of the publication of new papers, all arriving with new citations to previously published papers. All the models we have studied so far in the last three chapters deal, instead, with static graphs. For instance, in order to construct random graphs and small-world networks we have always fixed the number N of vertices and then we have randomly connected such vertices, or rewired the existing edges, without modifying N. In this chapter we show that it is possible to reproduce the final structure of a network by modelling its dynamical evolution, i.e. by modelling the continuous addition in time of nodes and links to a graph. In particular, we concentrate on the simplest growth mechanisms able to produce scale-free networks. Hence, we will discuss in detail the Barabási–Albert model, in which newly arrived nodes select and link existing nodes with a probability linearly proportional to their degree, the so-called rich gets richer mechanism, and various other extensions and modifications of this model. Finally, we will show that scale-free graphs can also be produced in a completely different way by means of growing models based on optimisation principles.

Citation Networks and the Linear Preferential Attachment

As authors of scientific publications we are all interested in our articles being cited in other papers’ bibliographies. Citations are in fact an indication of the impact of a work on the research community and, in general, articles of high quality or broad interest are expected to receive many more citations than articles of low quality or limited interest. This is the reason why citation data are a useful source not only to identify influential publications, but also to find hot research topics, to discover new connections across different fields, and to rank authors and journals [87, 194].

The term random graph refers to the disordered nature of the arrangement of links between different nodes. The systematic study of random graphs was initiated by Erdős and Rényi in the late 1950s with the original purpose of studying theoretically, by means of probabilistic methods, the properties of graphs as a function of the increasing number of random connections. In this chapter we introduce the two random graph models proposed by Erdős and Rényi, and we show how many of their average properties can be derived exactly. We focus our attention on the shape of the degree distributions and on how the average properties of a random graph change as we increase the number of links. In particular, we study the critical thresholds for the appearance of small subgraphs, and for the emergence of a giant connected component or of a single connected component. As a practical example we compute the component order distribution in a set of large real networks of scientific paper coauthorships and we compare the results with random graphs having the same number of nodes and links. We finally derive an analytical expression for the characteristic path length, the average distance between nodes, in random graphs.

Erdős and Renyi (ER) Models

A random graph is a graph in which the edges are randomly distributed. In the late 1950s, two Hungarian mathematicians, Paul Erdős and Alfréd Rényi came up with a formalism for random graphs that would change traditional graph theory, and led to modern graph theory. Up to that point, graph theory was mainly combinatorics. We have seen one typical argument in Section 1.5. The new idea was to add probabilistic reasoning together with combinatorics. In practice, the idea was to consider not a single graph, but the ensemble of all the possible graphs with some fixed properties (for instance with N nodes and K links), and then use probability theory to derive the properties of the ensemble. We will show below how we can get useful information from this approach. Erdős and Rényi introduced two closely related models to generate ensembles of random graphs with a given number N of nodes, that we will henceforth call Erdős and Rényi (ER) random graphs [49, 100, 101].

What are the building blocks of a complex network? We have seen in Chapter 4 that triangles are highly recurrent in social and biological networks, so that they can be considered as one of their elementary bricks. In this chapter we will discuss a general approach to define and detect the building blocks of a given network. The basic idea is to look not only at triangles but also at cycles of length larger than three, and at other small subgraphs, known as motifs, which occur in real networks more frequently than in their corresponding randomised counterparts. We will first derive a set of formulas to count the number of cycles in a graph directly from its adjacency matrix. As an application, we will use these formulas to find the number of cycles of different lengths in urban street networks and to compare various cities from all over the world. Notice that urban streets are a very special type of network. Their nodes have a position in Euclidean space and their links have a length, and as such they need to be described in terms of spatial graphs. The topology of spatial graphs is constrained by their spatial embedding, so that urban streets require special treatment. This will imply, in our case, the choice of appropriate spatial graphs to use as network null models when counting cycles in a city. In the second part of the chapter we will concentrate on other small subgraphs which are overabundant in some real networks and can therefore be very useful to characterise their microscopic properties. In particular, we will show that one specific motif, namely the so-called feed-forward loop, that emerges in the structure of the transcription regulation network of E. coli and of other biological networks, is there because it plays an important biological function. This relation between structure and function is the main reason why, by performing a so-called motif analysis and by looking at the profile of abundance of all possible subgraphs, it is possible to classify complex networks and to group them into different network superfamilies.

Problems, Algorithms and Time Complexity

We introduce here the elementary concepts of computer science and complexity theory which will be useful in understanding the material of the other appendices. This appendix is primarily intended for those readers who do not have a background in computer science. Its main aim is that of presenting basic notions about computational problems, the axiomatic definition of algorithms, the standard methods to represent algorithms, the concept of time complexity and a few useful tools to estimate the time complexity of simple algorithms. Whenever possible, the discussion has been intentionally left informal and all the unnecessary technicalities have been discarded, in order to allow the reader to focus on the essential concepts without being distracted by definitions and theorems. For a more formal treatment of the material presented in this appendix we encourage the interested reader to refer to any classical book on algorithms, such as the trilogy by Donald Ervin Knuth [181, 182, 183] or in Complexity Theory [250].

What Is a “Problem”?

Formally, a problem P is a pair (D,Q) of an abstract description D and a question Q requiring an answer. A simple example of a problem in graph theory is the Graph Connectivity Problem: “Given a graph G(N,L) where N denotes a set of vertices and L is the set of edges among vertices in N, is the graph G connected?” In this example, the description provides the context of the problem, which is usually represented as a class of objects (a generic graph G(N,L)), while the question to be answered (“is G connected?”) is a precise enquiry about a specific property of the class of objects under consideration.

The definition above is quite general and is given for an entire class of objects, without any specific connection to a particular object of that class. Conversely, an instance of a problem includes a full specification of one particular object of a class, which we indicate as x, and the solution P(x) is the answer to the question Q for the specific object x under consideration.

Explicit and Coarse-grained Molecular Models

The first NEMD simulations of molecular fluids were mostly performed with coarsegrained or simplified molecular models because simulations of more realistic, explicit models had high computational demands compared to the computing power then available. For simpler molecules, such as diatomic nitrogen and chlorine, nonequilibrium simulations of explicit molecular models were performed very early, but for more complicated molecules such as the n-alkanes, many of the earliest NEMD simulations were done with models that employed approximations such as the united atom approximation, where CH2 and CH3 groups were modelled as identical interaction sites with simplified intermolecular potentials. Furthermore, it was usually assumed that all bond lengths and bond angles were rigidly constrained and that dihedral angle potentials followed simplified functional forms. With the rapid growth in computational power, many of these assumptions have become unnecessary, but there are often good physical reasons for assuming that bond lengths should be constrained in classical molecular dynamics simulations. Therefore, constrained molecular models remain an important and useful part of the simulation toolkit, and we will devote some time to them in this chapter.

Many early attempts at coarse-graining were ad hoc and expedient, with little theoretical justification. This has recently changed quite dramatically, and the statisticalmechanical theory of coarse-graining and multiscale simulation is now an active field of research [266–268]. Here, we will only very briefly introduce a few simple coarsegrained models that are of interest mainly because they appear so prominently in the literature and they are so useful for simulating the general qualitative features of the dynamics of molecular fluids with minimal computational demands.

All-atom and United Atom Molecular Models

Explicit, all-atom molecular models and potential energy functions (force fields) are now available frommany different sources, such as the enormous literature on molecular dynamics packages for biomolecular simulations and computational materials science. Generally speaking, most users of these potential energy functions encounter them in packages, which are already well-documented and do not need to be discussed here.

In 2007 we wrote a review, entitled ‘Homogeneous nonequilibrium molecular dynamics simulations of viscous flow: techniques and applications’ [1]. Our aim then was to write a comprehensive review of the current state of the field. Though limited only to homogeneous fluids, it was clear to us then that such a review was necessary because of the growing popularity of nonequilibrium molecular dynamics (NEMD) as a powerful tool to study the transport of molecular fluids far from equilibrium. While NEMD is powerful, it is also subtle and it is often quite easy to make fundamental errors in the design and implementation of algorithms and, hence, generate results that are not what the researcher actually intends.

There are several books that deal with NEMD methods, but only the one by Evans and Morriss is entirely devoted to the field [2]. However, this influential book concentrates more on the theoretical foundations of the field, rather than providing broad algorithmic guidance for those interested in writing NEMD programs. Furthermore, the mathematical depth of the treatment presents the subject in a way that may not be readily absorbed or implemented by graduate students or nonspecialist scientists or engineers who wish to make use of reliable NEMD algorithms in their research.

It is with this point central in our thoughts that we felt it timely to write a book that could appeal to the general practitioner in the broader field of molecular simulation: not only one which builds upon previous knowledge, but also one that provides a more general overview of the field – its motivations and theoretical foundations – introduces state-of-the-art algorithms, and provides guidance on how to design reliable NEMD code for both atomic and molecular fluids. Furthermore, this book now addresses the shortcoming of our 2007 review, in that we discuss techniques to simulate highly confined fluids, thus enabling researchers to apply these methods to the realm of nanofluidics. In this realm, traditional concepts of local transport coefficients must be questioned, and the principles of generalised hydrodynamics embraced. Not every NEMD method is discussed, and at the outset we acknowledge this limitation; time and space restrictions make it impossible to condense all methods into a single book. But we have hopefully discussed many of the important methods used to simulate liquids far from equilibrium, as well as their strengths and limitations.

As we have shown in Chapter 2, the transport coefficients appearing in the entropy production of a simple, one component fluid are the bulk and shear viscosities and the thermal conductivity. We have already devoted considerable attention to the shear viscosity, because of its importance as a practical transport coefficient and as a test property for nonequilibrium statistical mechanics. The determination of the thermal conductivity by homogeneous nonequilibrium molecular dynamics techniques is also an interesting and subtle subject, leading to fundamental questions regarding the relationship between the synthetic heat field appearing in nonequilibrium molecular dynamics simulations and the temperature gradient, and the existence of “heat waves”. When binary and multicomponent systems are considered, new transport coefficients associated with diffusion and the Soret and Dufour effects appear, and additional questions regarding the application of linear response theory to equations of motion with phase-space compression arise.

The thermal conductivity can be determined by equilibrium molecular dynamics simulations using the Green–Kubo formula, by homogeneous molecular dynamics methods that introduce a synthetic “heat field”, or by inhomogeneous molecular dynamics methods that examine the heat flow between thermal reservoirs. Here, we will focus on the homogeneous nonequilibrium molecular dynamics methods, because the equilibrium methods have been described in detail elsewhere, and the reservoir methods suffer from the same problems as the “boundary-driven” methods for the determination of the shear viscosity. Reservoir methods work by directly inducing a temperature gradient which must be large due to the poor signal to noise ratio of the molecular dynamics methods. This large temperature gradient also inevitably leads to inhomogeneity of the density. In this case the value of the thermal conductivity obtained from the simulation is the average over a range of temperatures and densities. This is an even greater limitation if we wish to compute the thermal conductivity near the critical point or near a phase transition. Similar considerations apply to the determination of the diffusion coefficient of the binary fluid, and the Soret and Dufour coefficients. Fortunately, in all cases, there exist homogeneous nonequilibrium molecular dynamics algorithms for the determination of these transport coefficients. The equations of motion used in these algorithms generate the desired fluxes in homogeneous systems. In each case, there is a statisticalmechanical proof that the equations of motion lead to the correct determination of the corresponding linear transport coefficient.

A detailed microscopic description of nonequilibrium classical mechanical systems can be achieved through the methods of nonequilibrium statistical mechanics. Beginning with the development of the Green–Kubo relations in the 1950s, modern nonequilibrium statistical mechanics has now reached a high level of sophistication, culminating in time-dependent nonlinear response theory and the derivation of fluctuation theorems. Several different approaches to nonequilibrium statistical mechanics that have slightly different fundamental perspectives have been developed. Some examples of these differing approaches can be seen in the books by McLennan [37], Eu [38], Zwanzig [39], Zubarev [40] and Gaspard [41]. The methodology we will use closely follows Evans and Morriss [2]. It evolved in close connection with the development of many of the nonequilibrium molecular dynamics simulation algorithms discussed in this book, and it is particularly suitable for our discussion. Readers seeking a broader introduction to nonequilibrium statistical mechanics are advised to consult the references provided.

Fundamentals of Classical Mechanics

Equations of Motion

Before proceeding with our discussion of nonequilibrium statistical mechanics, we will introduce the main concepts of classical mechanics. This will allow us to establish our notation and some basic ideas before moving on to the more complex material that follows. The simplest and most familiar formulation of classical mechanics for a single particle is based on Newton's second law of mechanics,

where m is the particle's mass, r is its position and ris its velocity. The total force FT may be a function of the particle's position, velocity and may also be an explicit function of time. For a system of interacting particles, the equation of motion for particle i may be a function of the positions and velocities of all other particles in the system, as well as an explicit function of time. The Lagrangian and Hamiltonian formalisms are richer and more elegant formulations of classical mechanics.

Generalised Hydrodynamics

The realisation that classical Navier-Stokes hydrodynamics would fail at molecular length-scales is not new. It has long been expected that generalised hydrodynamics could play an important part in the prediction of transport properties of inhomogeneous fluids. In 1983 Alley and Alder [321] noted that generalised hydrodynamic models could be very useful to the development of molecular-level predictive tools. In generalised hydrodynamics, the transport coefficients are no longer regarded as constants, nor are they simply material properties of a fluid at the local thermodynamic state point. Transport now becomes a fully nonlocal property of fluids, and likewise all the transport “coefficients” now become nonlocal in both time and space. In other words, the transport “coefficients” are now replaced by kernels and the governing constitutive equations are integral functions (convolutions) over both space and time. The kernels themselves now have both a wavelength and frequency dependence. In fact, significant progress in the development of generalised hydrodynamics was made in the 1970s by Akcasu and Daniels [369] and Ailawadi et al. [370]. The books by Boon and Yip [371], Eu [372] and Hansen and McDonald [61] also treat this subject in considerable detail, and we refer readers to these references for a much more thorough theoretical foundation.

Our purpose is to show how generalised hydrodyamics can be used as a predictive tool for inhomogeneous fluids. In particular, we will show how classical Navier-Stokes hydrodynamics breaks down at molecular length scales when the spatial variation in the driving thermodynamic force (e.g. the strain rate) is significant over the range of molecular interactions. Such conditions can occur not only for highly confined fluids, but also for fluids under shock conditions [373–375], where moment and gradient expansions originally derived from gas kinetic theory are commonly employed [372, 376]. Nonlocal effects are also observed in shear-banding phenomena [377], micellar solutions [378], Brownian suspensions of rigid fibres [379] and jammed glassy systems [380] and may well play a significant role in turbulence.

We will first demonstrate where breakdown in classical theory occurs in both confined fluids and systems in which the curvature in the strain rate exceeds the width of the relevant transport kernel. We then express the governing constitutive equation in its generalised form and demonstrate several techniques to compute the transport kernels. Once the kernels are computed, it is a straightforward matter to use them to predict properties of interest.