5.2.1 Peer‐to‐Peer Networks

This is a topology that consists of two nodes that are connected to each other. In general, a peer‐to‐peer network with the size is composed of links, where each node is only connected with another node. In this case, all nodes have degree one, i.e. . This can be seen as an extreme case of a disconnected network. For example, the communication proposed by Shannon presented in the previous chapter with a transmitter and a receiver can be seen as a peer‐to‐peer network with with one directed link.

5.2.2 One‐to‐Many, Many‐to‐One, and Star Networks

The one‐to‐many topology is a directed network where one “central” node is connected to all other nodes. If the network has size , then we can assume without loss of generality that node 1 is the central one. Because the network is directed, the degree of the node can be categorized as out‐ and in‐flows, and thus, and . For all the other nodes, we have: and . The many‐to‐one topology can be understood as a mirrored version of the one‐to‐many. In this case, the central node have in‐flow links from all the other nodes. Then, and , while and . The star network has the same topology as the one‐to‐many and the many‐to‐one but with undirected links. In this case, we have , while . In all three cases, .

5.2.3 Complete and Erdös–Rényi Networks

A undirected network where all nodes are connected is called complete or fully connected. In a network with size , with a cluster coefficient . In this case there will be links in the network.

Erdös–Rényi (ER) networks were introduced by Hungarian mathematicians Erdös and Rényi in [7] to study random graphs with nodes, which is a fixed number. The uncertainty in this network is related to the randomness of (i) the number of links, and (ii) the connection between nodes created by these links. Extreme cases are when the network has no links (i.e. it is only a collection of disconnected points) and a complete network where all the nodes are connected.

Without loss of generality, consider any two nodes and and a potential link between them. The existence of is associated with a random variable with a sample space where is associated with the absence of while denotes the existence of such a link. The probability mass function of is and . In ER networks, the existence of a link between any two nodes in the network is determined by the outcomes of the independent outcomes of the random variable .

In this case, a probabilistic characterization of the graph is possible. For example, each node in the network has links on average. If , the ER network is reduced to a complete graph. Likewise, if , the ER network is just a collection of points. They are the aforementioned extreme cases, which are actually deterministic. Note that the ER network is completely characterized by it size and the probability . A formalization of ER networks is the target of Exercise 5.1. A detailed mathematical analysis of ER networks can be found in [1, 2, 5, 7].

5.2.4 Line, Ring, and Regular Networks

The line network is defined when the nodes are connected to form a line, and thus, all nodes have two neighbors except the border nodes. If its size is , then the network will have links. If we assume that the border nodes are nodes 1 and , then the node degrees are and . This network is connected and the cluster coefficient is . The diameter of the network is , determined by the distance between the two extremes.

If the ring topology is similar but the border nodes are connected, then and . If , then . The diameter of this network considering both directed and undirected links is part of Exercise 5.2, and thus, we will not present it here.

Regular topologies are a broader term that usually refers to any topology that has a deterministic pattern. The already discussed line and ring topologies, as well as the star topology, can be classified as regular. Other regular grids are, for example, a rectangular, or a hexagonal grid, and also variations of the ring topology where nodes are symmetrically connected with neighbors. Regular networks are deterministic and symmetric in contrast to random networks like ER.

5.2.5 Watts–Strogatz, Barabási–Albert and Other Networks

Watts–Strogatz (WS) networks are random graphs proposed by Watts and Strogatz in a paper published in 1998 [8]. The idea was to capture the small‐world phenomena illustrated by the famous study by Milgram [9], which indicated that, even in very large social networks, the average path lengths between nodes are small. Watts and Strogatz proposed a method to generate networks with such a characteristic starting from a variation of a ring topology where nodes are connected with neighbors. From the initial regular topology, nodes are randomly rewired with a given probability . In the extreme cases, the WS network is a regular grid if , and a ER network is . The example presented by the authors is a pedagogical way to explain how a WS network can be generated [8]:

Random rewiring procedure for interpolating between a regular ring lattice and a random network, without altering the number of vertices or edges in the graph. We start with a ring of vertices, each connected to its nearest neighbors by undirected edges. (For clarity, and in the schematic examples shown here, but much larger and are used in the rest of this Letter.) We choose a vertex and the edge that connects it to its nearest neighbor in a clockwise sense. With probability , we reconnect this edge to a vertex chosen uniformly at random over the entire ring, with duplicate edges forbidden; otherwise we leave the edge in place. We repeat this process by moving clockwise around the ring, considering each vertex in turn until one lap is completed. Next, we consider the edges that connect vertices to their second‐nearest neighbors clockwise. As before, we randomly rewire each of these edges with probability , and continue this process, circulating around the ring and proceeding outward to more distant neighbors after each lap, until each edge in the original lattice has been considered once. (As there are edges in the entire graph, the rewiring process stops after laps.) Three realizations of this process are shown, for different values of . For , the original ring is unchanged; as increases, the graph becomes increasingly disordered until for , all edges are rewired randomly. One of our main results is that for intermediate values of , the graph is a small‐world network: highly clustered like a regular graph, yet with small characteristic path length, like a random graph.

This text refers to Figure 5.4, which is adapted from the original paper.

Barabási–Albert (BA) networks were proposed in [10] considering a scenario where new nodes are added over time by a probabilistic mechanism called preferential attachment. The idea behind this approach is that any new node has higher chances to be connected with the nodes that have higher degrees, which leads to the emergence of hubs (i.e. nodes that are highly connected).

In fact, BA networks are a particular case of scale‐free networks, defined when the degree distribution of nodes follows a power law probability distribution. Mathematically, a power law distribution is defined as with , being then a heavy‐tailed distribution (i.e. it is not exponentially bounded like Gaussian or Poisson distributions). Power laws have also the interesting property of scale invariance: for a given function with being an arbitrary constant and a scaling factor , we have .

Although scale‐free networks have received attention as a tool to model real‐world interactions, recent results indicate that the scale‐free property might not be as widespread as initially thought [11]. Besides, there are several other alternatives of networks such as tree, mesh, and bus, as well as hybrid topologies or those without a specific type.

Such a structural characterization is important when describing processes that happen on networks, such as transference of data packets on the Internet, possible flight routes between two cities, or propagation of viruses. This is the focus of the next section.

5.3.1 Communication Systems

As indicated by Shannon's model [12], the peculiar function of a communication system is to transfer data from one point in space and/or time to another. Details of communication and computer networks can be found in textbooks, such as [13, 14]; detailed historical notes can be found in [15]. Consider two persons: Amanda and Bob. Amanda is willing to tell Bob that she will take a new course on cyber‐physical systems.

If both Amanda and Bob are in the same room, she can just tell it in a peer‐to‐peer link. However, if they are in a lecture room far from each other, Amanda decides to write this on a piece of paper and send it to him through a path with two other nodes that relay the message. In this last case, the message is routed in a regular grid. If Amanda and Bob are in their own houses, Amanda decides to call Bob by a landline phone that is connected through a public switched telephone network (PSTN), which has a hierarchical tree‐like topology with levels of switching systems. Amanda could also use her connection to the Internet either by sending an instant message from her computer, or by calling Bob by a Voice over Internet Protocol (VoIP) using her mobile phone connected to a cellular network of fourth generation (4G). The Internet forms a dynamic decentralized network with hubs, which could be characterized under some conditions as scale‐free that may follow a BA network, e.g. [2].

Each real‐world situation has characteristics of its own. For example, if Amanda is telling the news to Bob in the same room, there might be more people talking, or loud music, and thus, the peer‐to‐peer link may break. In this case, the two nodes are not connected and the network stops functioning. As a consequence, we can say that the network is not robust against this missing link. The situation described in the lecture room is different: the written message can reach its final destination through several paths, not necessarily the shortest one. If a link is broken because an absent node (i.e. no one is sitting at that table to forward the message to the destination), alternative routes may still be possible. We can then say that this network has a certain level of resilience with respect to missing links, i.e. even without a few links, the function of the communication network can be accomplished. However, if certain links are absent, the network may not percolate, and thus, the message cannot reach its final destination.

We could also compare the difference of calling by using PSTN and VoIP. Without going into technical details, PSTNs are based on a dedicated hierarchical network that resembles a star topology, and thereby, with important central nodes that connect Amanda and Bob by multiple circuit switches. The robustness of the network as a whole is highly dependent on its central nodes. Once established, this link is exclusive with quality guarantees. VoIP, in its turn, runs on the Internet, which is a dynamic network‐based data multiplexing using packet switching technology, without explicit quality guarantees. VoIP “slices” the voice into smaller data packets that travel through the network in different routes to reach the address of the final destination, multiplexed with all other possible data packets (e.g. other VoIP, videos, and text files). At the destination, the packets are grouped together and decoded as voice. The quality of a VoIP call is usually worse than that of PSTN calls, but the network is more resilient because of the existence of several hubs and many possible routes.

5.3.2 Transportation in Cities

The case studied by Euler presented in Figure 5.1 can be seen as an example of how transportation networks could be modeled as a graph. This was clearly a toy example, but very illustrative because it indicates the impossibility of a solution to the Seven Bridges problem. One of the classical problems in the literature of transportation networks is the traveling salesman problem [16]. The problem is the following: Given a list of cities with their connections, what is the shortest possible route that visits each city exactly once and returns to the origin city? This problem can be formulated as a graph with weighed edges, which results in a combinatorial optimization problem; in the literature of computer sciences, this is known as a typical example of a problem that cannot be solved in polynomial time.

Without going into the details of NP‐hardness and its importance for operational research and logistics, we will focus on topological aspects of the network and how this affects transportation in cities. Consider the Berlin S‐Train map presented in Figure 5.5. Each station is a node connected by edges, which are associated with different train lines. Outer stations have a low degree while central stations high, resembling a star topology. Around the center of the network there are also lines forming a ring topology. Putting together, this hybrid topology is built to have not only one overcrowded central hub, but also a few smaller hubs where the radial lines cross with the ring. In this way, the traffic of the transportation network could be balanced between different routes.

This simple daily life example illustrates how networks are part of our lives. It is interesting to mention that studying cities through the lenses of network sciences has been a tendency for a few years. For interested readers, the reference [17] is a milestone in the field by empirically showing how different characteristics of cities scale with their size along with a formalism derived from network sciences and dynamical systems.

5.3.3 Virus Propagation and Epidemiology

The COVID‐19 pandemic has led to a widespread interest in epidemiological models of how viruses and other infectious deceases propagate. In the literature there are three basic models [2], namely Susceptible‐Infected (SI), Susceptible‐Infected‐Susceptible (SIS), and Susceptible‐Infected‐Recovered (SIR). The premise employed in those models is that individuals can be classified with respect to a given pathogen as:

• Susceptible: Healthy individuals that have not yet contacted the pathogen;
• Infected: Individuals that carry the pathogen and can infect susceptible individuals if they are in contact;
• Recovered: Individuals who have been infected before, but are healthy, and thus, cannot propagate the pathogen.

Without going into the mathematical characterization based on differential equations and random walking theory, the idea of SI, SIS, and SIR basic models is to analytically assess when a disease will be spread over all population, or the effect of the spreading rate – the famous that dominated the news in 2020 during the COVID‐19 pandemic, which, in the words of Barabasi [2], is the number of new infections each infected individual causes under ideal circumstances.

The SI model is the one that assumes that there is no recovery, and thus, it indicates how long a given population will be fully composed of infected individuals. The SIS model assumes that individuals can recover, but they are immune and they can become infected once again. In this case, two outcomes at the population level may happen: (i) an endemic state where there is an equilibrium so that there is always a given ratio of the population infected, or (ii) a decease‐free state where the pathogen cannot propagate and fades away from the population. The situation (i) is associated with , while (ii) with . The SIR model adds another class of individuals that are not susceptible to the pathogen and also do not transmit it. These are recovered individuals, who are immune to the pathogen after infection. In this basic SIR model, all the elements of the population will be eventually recovered. Those models could also be adapted to include immunization and individuals that died.

Once again, it is interesting to quote Barabasi [2]:

In summary, depending on the characteristics of a pathogen, we need different models to capture the dynamics of an epidemic outbreak. (…) [T]he predictions of the SI, SIS, and SIR models agree with each other in the early stages of an epidemic: When the number of infected individuals is small, the disease spreads freely and the number of infected individuals increases exponentially. The outcomes are different for large times: In the SI model everyone becomes infected; the SIS model either reaches an endemic state, in which a finite fraction of individuals are always infected, or the infection dies out; in the SIR model everyone recovers at the end. The reproductive number predicts the long‐term fate of an epidemic: for the pathogen persists in the population, while for it dies out naturally.

For this reason, we can see the importance of the factor so highly discussed during the COVID‐19 pandemic.

In a seminal paper [18], Pastor‐Satorras and Vespignani expanded those basic epidemiological models from generic dynamical equations to scenarios with a networked structure. In this case, individuals are nodes in the network whose links refer to pairwise contacts between individuals. The propagation of a pathogen is actually a result of social interactions, including transportation networks in cities and daily activities, as well as international traveling and popular sports or music events. As indicated by studies of cities and transportation networks, epidemiological networks are usually associated with scaling laws, and thus, there will be some nodes with a very high degree. Such nodes are super‐spreaders. Although each pathogen is different, understanding the networked dynamics of its propagation is essential to design proper interventions to combat epidemics [2, 19].

Figure 5.6 illustrates the propagation of different flu strains using the open‐source tool called Nexttrain [20]. It is interesting to see how different strains propagate as a network connecting different regions. The granularity of this tool is not enough to capture the networked dynamics of the SI, SIS, and SIR models, but it illustrates the effects of international traveling in flu epidemics. Note that an additional aspect can be added in the model to include exposures, defined as the immediate neighbors of a given infected node. This model is known as Susceptible‐Exposed‐Infected‐Susceptible (SEIR) [21].

5.4.1 From (Big) Data to Mathematical Abstractions

Big data and data‐driven approaches where “machines learn” patterns from data are widespread. As indicated by Nextstrain and [2], empirical data can be used to build mathematical models capable of predicting events such an outbreak. However, as reported in [11], modeling (big) data related to complex networks is not straightforward and may create a tendency of empirically finding scale‐free networks. Such an approach may lead to empirical scaling laws that may lead to inaccurate predictions. Besides, if the predictive model affects the dynamics of the network evolution, the mathematical abstraction may become intrinsically incorrect because of a feedback loop.

5.4.2 From Mathematical Abstractions to Models of Physical Processes

Generative mathematical models that assume an ideal, purified object to characterize complex real‐world networks may also be problematic. Similar to what we have described before about empirical data being “forced” to fit the characterization of scale‐free networks, generative mathematical models for networks may likewise be misleading. For instance, predictions for COVID‐19 based on generative models can be wrong but useful as discussed in [22]. What should be highlighted is that mathematical models cannot impose itself on the reality of the process under consideration. If the data obtained from the real world network do not behave as expected by the generative model, the evaluation ought to be fair and not blame the reality for not being the ideal model. As indicated in Chapter 1, a consistent and elegant mathematical model is neither a necessary nor a sufficient condition for being a scientific theory of a given object, including networks.

5.4.3 Universality and Cross‐Domain Issues

The two limitations just presented can, in fact, be summarized in one problem: universality. This is closely related to the discussions introduced by Broido and Clauset [11] in contrast to the view that scale‐free networks are everywhere, defended by Barabasi [2]. The question was an interesting one posed by Holme [23], as a comment about such a controversy. Similar questions might be considered by the science of cities defended by Bettencourt [17] utilizing network sciences to derive the characteristics of complex urban formations.

The question is the following: are power grids, cities, epidemics, social relations, and air traffic all following a hidden pattern revealed by network sciences? This is controversial and, for the reasons stated in Chapter 1, the position taken by this book leads to a no as the answer, although the models are indeed useful if understood a tool, not as a scientific representation of reality. Note that some objects can be scientifically characterized as networks, but it is not a universal characterization. Most of the time, network sciences provides a potentially useful model, not a scientific theory of the phenomenon under investigation.

Inga Holmdahl and Caroline Buckee precisely indicate in [22] five questions about models for COVID‐19, also stating how their results should be used. Such precautionary propositions touch the key issues mentioned above by identifying two classes of models, namely data‐driven predictive models and mechanistic mathematical models. This is what they wrote:

FIVE QUESTIONS TO ASK ABOUT MODEL RESULTS

1. What is the purpose and time frame of this model? For example, is it a purely statistical model intended to provide short‐term forecasts or a mechanistic model investigating future scenarios? These two types of models have different limitations.
2. What are the basic model assumptions? What is being assumed about immunity and asymptomatic transmission, for example? How are contact parameters included?
3. How is uncertainty being displayed? For statistical models, how are confidence intervals calculated and displayed? Uncertainty should increase as we move into the future. For mechanistic models, what parameters are being varied? Reliable modeling descriptions will usually include a table of parameter ranges – check to see whether those ranges make sense.
4. If the model is fitted to data, which data are used? Models fitted to confirmed Covid‐19 cases are unlikely to be reliable. Models fitted to hospitalization or death data may be more reliable, but their reliability will depend on the setting.
5. Is the model general, or does it reflect a particular context? If the latter, is the spatial scale – national, regional, or local – appropriate for the modeling questions being asked and are the assumptions relevant for the setting? Population density will play an important role in determining model appropriateness, for example, and contact‐rate parameters are likely to be context‐specific.

(…)

Unlike other scientific efforts, in which researchers continuously refine methods and collectively attempt to approach a truth about the world, epidemiologic models are often designed to help us systematically examine the implications of various assumptions about a highly nonlinear process that is hard to predict using only intuition. Models are constrained by what we know and what we assume, but used appropriately and with an understanding of these limitations, they can and should help guide us through this pandemic.

We think that the argument put forth by the authors is also valid across several other domains in general and network sciences in particular, also including the aforementioned debate about whether scale‐free networks are rare or everywhere [23].

Exercises

1. 5.1 Formalization of ER networks.  ER networks are presented in Section 5.2.3. Consider a network with nodes and a probability that a link between two nodes exists.
   1. If represents a random variable associated with the degree of a given node, compute the probability mass function , i.e. the probability that a given node in the network has connections.
   2. Compute the expected value of , i.e. .
   3. Compute the variance of , i.e.
   4. Interpret such theoretical results considering two scenarios: (i) varies from two to infinity, and (ii) varies from zero to one. Write this answer with your own words supported by the mathematical findings.
2. 5.2 Network topologies.  Consider a network with a ring topology of nodes with links that are unweighted and undirected. Present the results as a function of .
   1. Compute the degrees of the nodes.
   2. Present the adjacency matrix.
   3. Compute the network diameter.
   4. Compute the cluster coefficients of the nodes.
   5. Analyze the ring topology with as a communication network (i.e. how data travel to a point to another in the network) based on the node degree, the network diameter, and the cluster coefficient.
   6. Consider that you are a designer who wishes to improve the communication network described in (e). Your task is to change the ring network topology by adding only one new node and an unlimited number of links connected to it. Justify your decision and identify a vulnerability of this topology.

      

3. 5.3 Networks in the real world.  Consider the world airline routes presented in Figure 5.7.
   1. Provide a qualitative assessment of this network by, for instance, commenting about its topology and node degree distribution.
   2. How many clusters could you visually identify in this network?
   3. Consider that a new infectious disease transmitted by airborne droplet like flu appeared in the world. Which continent would be easiest to isolate? Justify.