Skip to main content
main-content

About this book

This book develops a morphodynamical approach of spatial networks with a particular emphasis on infrastructure networks such as streets, roads and transportation networks (subway, train). The author presents the mathematical tools needed to characterize these structures and how they evolve in time. The book discusses the most important empirical results and stylized facts, and will present the most important models of spatial networks. The target audience primarily comprises research scientists interested in this rapidly evolving and highly interdisciplinary field, but the book may also be beneficial for graduate students interested in large networks.

Table of Contents

Frontmatter

Chapter 1. From Complex to Spatial Networks

The study of spatial networks – networks embedded in space – started essentially with quantitative geographers in the 60–70 s who studied the structure and the evolution of transportation systems. The interest for networks was revived by Watts and Strogatz who opened the way to a statistical physics type of analysis and modeling of large networks. This renewed interest, together with an always growing availability of data, led to many studies of networks and their structures. Most of these studies focused on the topological properties of networks, leaving aside their spatial properties. It is only recently that researchers realized the importance of geometry – as opposed to topology – for spatial networks. In this chapter, we first describe briefly the evolution of these fields and ideas about spatial networks. Most of these objects are planar and in the second part of this chapter, we give basic definitions and results for planar graphs.

Marc Barthelemy

Chapter 2. Irrelevant and Simple Measures

Many studies on complex networks were about how to characterize them and what are the most relevant measures for understanding their structure. In particular, the degree distribution and the existence of the second moment for an infinite network were shown to be critical when studying dynamical processes on networks. These behaviors are therefore strongly connected to degree fluctuations and the existence of hubs. In the case of spatial networks, the physical constraints are usually large and prevent the appearance of such hubs. These constraints also impact other quantities that are nontrivial for complex networks but that become irrelevant for spatial networks. We review here these measures that are essentially useless for spatial networks and we then discuss older, simple measures that were mostly introduced in the context of quantitative geography.

Marc Barthelemy

Chapter 3. Statistics of Faces and Typology of Planar Graphs

From a theoretical point of view, an important problem amounts to understand the structure of random planar graphs and eventually to propose a classification of these objects. In this chapter, we will discuss three different approaches. In the first one, we discuss the statistics of the area and shape of faces, and we apply this to street networks. The possibility of defining a distance between two graphs allows to propose a first simple typology of planar graphs and in particular of street networks. In a second approach, a decimation process is used in order to constructing an approximate mapping from a (weighted) planar graph to a tree. Finally, in a third part, we discuss a more mathematical approach based on an exact bijection between a planar graph and a tree.

Marc Barthelemy

Chapter 4. Betweenness Centrality

There are many centralities that characterize the importance of a node (or an edge) in a large network. Among all these centralities, the betweenness centrality (BC) captures important aspects of the network and its structure. For complex networks, the BC generally scales with the degree, showing that in general central nodes are the hubs. In spatial networks, however, we do not have hubs and the degree is in general not equivalent to the BC. Generally speaking, for a lattice we expect the BC to decrease with the distance to the barycenter of all nodes, while the disorder introduces fluctuations that can dramatically alter this effect of distance and create nontrivial patterns. In this respect, the pattern of the BC for spatial networks is an interesting interplay between space and topology and a priori contains a lot of information about the structure of these networks. In this chapter, we will first discuss general properties of the BC and then address more advanced questions.

Marc Barthelemy

Chapter 5. Simplicity and Entropy

Despite a large number of studies on planar networks, there is still a lack of global, high-level metrics allowing to characterize their structure and geometrical patterns.

Marc Barthelemy

Chapter 6. Spatial Dominance and Community Detection

Nodes in networks are in general defined by their connectivity properties but could also carry another type of information. In the case where nodes represent cities, the population is a natural attribute that can be attached to each node. In the case of spatial networks with attributes on nodes, we can foresee the problem of correlating their topological properties, their location, and their attribute.

Marc Barthelemy

Chapter 7. Measuring the Time Evolution of Spatial Networks

We discussed in the previous Chaps. (1–6) how to characterize the structure of spatial networks. In many instances, however, these networks are evolving in time, growing, and expanding in space. This is typically the case of transportation networks such as roads, subways, and railways, but also for biological networks. It is therefore important to be able to characterize the evolution of these networks, and to detect crucial changes and distinguish them from ordinary growth. In this chapter, we will address such problems for the road networks and we will try to highlight the major differences between an “organic” growth from systems that experiences major changes due to planning decisions. We will illustrate these two types of evolution on the example of the region of Groane (Italy) and the example of central Paris which experienced major large-scale planning operations during the nineteenth century (the “Haussmann” period). In this latter case, usual network measures display a smooth behavior and the most important quantitative signatures of central planning are the spatial reorganization of centrality and the modification of the block shape distribution. Such effects can only be obtained by structural modifications at a large-scale level, with the creation of new roads not constrained by the existing geometry. The evolution of the road network thus appears here as resulting from the superimposition of continuous, local growth processes, and punctual changes operating at large spatial scales.

Marc Barthelemy

Chapter 8. Tessellations of the Plane

Another way to think of planar networks is by focusing on their faces and how to generate them. An example is given by tessellations of a plane that are divisions of the plane into polygons. There is a vast literature on tessellations (see [188] and references therein) and in this chapter, we will discuss selected examples only. Many tessellations are constructed from a random set of points and we will first focus in this chapter on the well-known Voronoi tessellation and its dual, the Delaunay graph. We then discuss briefly another class of tessellation obtained by growing lines from points (with the Gilbert model) or obtained by adding random lines (STIT models). Finally, we briefly discuss the case of planar fragmentation, and in the last section how we can use Delaunay graphs for constructing a null model of spatial multilayer networks.

Marc Barthelemy

Chapter 9. Random Geometric Graphs

In this chapter, we discuss the random geometric graph (also called the unit disk graphUnit disk graph) which is an important model for spatial networks. We will also introduce and discuss some of the variants of this model. The random geometric graph is obtained from a random distribution of points in the plane and a geometric rule for connecting these points and creating edges. The simplest case is obtained when a proximity rule is used and which states that nodes only within a certain distance are connected.

Marc Barthelemy

Chapter 10. Spatial Generalizations of Random Graphs

The most important model of a random graph where nodes are connected at random was proposed by Erdos and Renyi [242] and constitutes an archetype—or at least a benchmark—for constructing more complex random graphs. It is then natural to ask if we can extend this model to the case where nodes are located in space. In this chapter, we will discuss some of the possible extensions that were proposed in the literature. In particular, we will discuss the Waxman graph which was proposed as a model for intra-domain Internet network. Another important model is the Watts–Strogatz graph [7] which interpolates between a lattice and the Erdos–Renyi random graph and is able to produce graphs with simultaneously a large clustering coefficient and a small diameter (varying as $$\log N$$). In this model, there is an underlying lattice and it can thus be considered as a spatial network. We will discuss some of the properties of this network and end this chapter with a presentation of navigability problems and the demonstration of Kleinberg’s result [243].

Marc Barthelemy

Chapter 11. Loops and Branches

A problem that can be faced when studying networks is the abundance of measures. This is particularly true for spatial networks where the combination of spatial and topological metrics contributes to the explosion of possible measures, and it is obviously worse when these networks evolve in time. In order to select the most relevant tools for characterizing these networks it is then important to have in mind a benchmark graph. We will illustrate this in the case of evolving subway networks which are spatial, time-evolving networks and whose growth can be difficult to understand without an appropriate template.

Marc Barthelemy

Chapter 12. Optimal Networks

Variational approaches have been largely disregarded in complex network studies although they frequently provide an alternative and possibly more meaningful point of view. This important class of network models is obtained by looking for graphs that optimize a given quantity, functional of the graph. The simplest case is, for example, the minimum spanning tree (MST) that minimizes the total length for a given set of points. Most existing spatial networks in the real-world do not seem to result from a global optimization, but rather from the progressive addition of nodes and segments resulting from a local optimization (see next chapters). By modeling (spatial) networks as resulting from a global optimization, one overlooks the usually limited time horizon of planners and the self-organization underlying their formation. The interest of these optimal networks lies then rather in the fact that they constitute interesting benchmark to compare actual networks with. The comparison with the MST, for example, indicates how far we are from the minimum cost possible, and is, therefore, a very important example and was largely studied. In particular, there is an extensive mathematical literature on this graph and we will try to discuss here the most important results on this case. We will also discuss other optimal trees that generalize the MST to the case where a more complex quantity than the total length is minimized.

Marc Barthelemy

Chapter 13. Models of Network Growth

Most networks, including spatial graphs, evolve and grow in time. Understanding the main processes governing this growth and the resulting structure is, therefore, crucial in many disciplines ranging from urban planning to the study of neural networks.

Marc Barthelemy

Chapter 14. Greedy Models

In Chap. 12, we discussed models of networks defined by the optimization of a single quantity that depends on the global structure of the network. In contrast, we consider here the growth of networks where nodes are added one by one, located at random and connected to the network in an optimal way.

Marc Barthelemy

Chapter 15. Discussion and Future Directions

As we saw throughout this book, despite the many studies in graph theory and combinatorics, neurophysiology, botanic, geography, and transport studies among others, we do not have a full understanding of the structure and evolution of spatial networks. In addition, these networks are not just simple structures embedded in a substrate but constitute the support for dynamical processes: it can be the traffic on transport networks, electric flow on power grids, or the spread of nerve impulses in neural networks.

Marc Barthelemy

Backmatter

Additional information