A relatively recent development in applied mathematics is the theory of networks. Networks represent connections between multiple physical or virtual entities. In the simplest case, a network is a collection of nodes, representing the different elements of the system, connected by edges, representing the existence of a relationship between elements.

A network of family relationships for famous people with the surname Marx. Each person is represented by a node, and a family relationship is represented by an edge. The network is disconnected as Karl Marx and his two daughters have no family relationship with the five Marx brothers. This network has two components.

A network can be also represented by matrices. The elements of the matrix indicate whether pairs of nodes are connected or not in the network. For simple networks with no special orientation between nodes, the adjacency matrix is a matrix of zeros and ones. The element (i, j) and( j, i) is equal to one if there is an edge between node i and node j, and zero otherwise, as shown in Figure 39. Therefore, problems in network theory can be recast as problems on matrices and vectors, and most of network analysis is done by manipulations of (very) large matrices. Historically, the study of networks was initiated by Euler via the famous Königsberg bridge problem and further developed by mathematicians studying the mathematical structure of ordered and random graphs (the Königsberg problem is how to devise a walk through the city of Königsberg that would cross each of the bridges once and only once). In the 1950s, sociologists started to use networks to study social interactions and the formation of small interacting communities within larger social groups. But the subject really became prominent with the Internet and data revolution that led both to the creation of large networks (such as the World Wide Web and the social network of Facebook) and the availability of large data sets.

Matrices and networks. A network can be coded by a matrix representation. Each column and line of a matrix represents a node. A value of 1 at place (i, j) indicates that there is an edge between node i and node j.

Since a network is an abstraction of relationships between discrete elements, networks are ubiquitous in science and society. They are found in social systems (friendship networks, collaboration networks, human languages, …), biological systems (gene regulatory networks, metabolic networks, protein interaction maps, ecological interactions, evolutionary trees, …) and engineering systems (physical networks, power grids, metro stations, airline routes, web links, …).

Network theory really took off at the end of the 1990s when scientists from different communities realized the importance and ubiquity of networks. A key problem is to understand the structure of networks found in nature and society. Are they regular (e.g. every node is connected to its two neighbours) or random (nodes are randomly connected)? It turns out that most networks around us are neither regular nor random, as demonstrated by the small‐world or six‐degrees‐of‐separation effect. In social networks people seem to be connected to people they do not know directly through only a few connections (the popular idea is that it would only take a chain of six people to connect you to Stephen Hawking through common acquaintances, or to connect the actor Kevin Bacon to any other actor through a chain of movies and cast members).

This small‐world effect was formalized in 1998 by Steven Strogatz from Cornell University and his doctoral student at the time, Duncan Watts. In their seminal paper ‘Collective dynamics of “small‐world” networks’, they explained that there are two important measures to quantify the connectedness of networks. The first one is the average path length, the average number of steps along the shortest paths for all possible pairs of network nodes. The second metric is clustering, measuring the degree to which nodes in a graph tend to cluster together. In a network of friends, high clustering means that there is a high probability that your friends also know each other. A regular network has a long path length but high clustering. A random network has a short path length and low clustering. Watts and Strogatz showed that real networks have both short average path lengths and high clustering: nearby members are closely connected but also connected to far‐away members. In the finest tradition of applied mathematics, they considered an extremely simple toy model by building a family of networks ranging from regular to random as shown in Figure 40. They showed that by rewiring a few elements of a regular network to allow for random long distance connections, the average path length is dramatically reduced: a few long‐distance shortcuts in a regular network brings all edges much closer, explaining the small‐world effect.

The small‐world effect. Starting from a regular network (left), each link is rewired with increasing probability (middle) up to a fully random model where each node is randomly connected to other nodes (right). If elements represent individuals and edges represent acquaintances: in the regular network, each element knows its two nearest neighbours on each side, whereas with added connections, some people know a few distant people.

Watts and Strogatz’s work was immensely influential and marked the start of network science as a mainstream mathematical discipline. Since then, the field has exploded and there is considerable interest in better understanding, designing, and controlling networks. For instance, the Internet can be modelled as a network where each webpage is a node and an edge exists between links if there is a weblink between the two. It is particularly important for web users to be able to navigate this giant network and find the page they want. The page ranking algorithms, used by big search engine companies to present the most relevant weblinks to users, are based on the analysis of networks and the relative importance of different sites based on their connections. In their simplest form these algorithms can be understood as a mathematical problem involving rather large matrices (that can have billions of entries).

Another interesting application of networks is in epidemiology: understanding how diseases spread on a network. The traditional models for the propagation of an infection take the form of a system of differential equations, similar to the ones seen in Chapter 4 for rabbits and wolves, but coupled to diffusion. These models describe the progression of a disease in a local population by computing the rate of change of infected people. The disease spreads spatially from direct contact, resulting in a propagating wave of infection. This approach is valid for the spreading of diseases from neighbour to neighbour. However, human mobility has completely changed, and we know that diseases can also spread by occasional contacts with people not living in close proximity. In trying to predict pandemics, we have to consider the possibility that an infected person could carry the disease to another continent through the air‐transport network (see Figure 41). For instance, in 2003 the severe acute respiratory syndrome virus (SARS) was first observed in China, then moved to Hong Kong, then jumped to Europe, Canada, and the United States. These long‐range connections change the dynamics by allowing for shortcuts in disease propagation. Network analysis shows that there is a critical number of these shortcuts that would change the progression from a localized epidemic to a global pandemic. These effects are now taken into account in order to pinpoint the origin of an outbreak and to formulate optimal public health policy in the case of future outbreaks.