Navigation – Plan du site
Dossier: Analyse des réseaux sociaux en archéologie

Discussion: Social and spatial networks

Marc Barthelemy
p. 51-61

Résumés

La numérisation récente de diverses sources historiques ouvre la possibilité passionnante de discuter quantitativement d’un grand nombre de phénomènes en sciences sociales et humaines. En particulier, de nombreuses données sont structurées sous forme de graphes, telles les relations entre individus ou villages, les routes ou autres infrastructures, et sont de plus habituellement géoréférencées. Les graphes correspondants sont alors des «réseaux spatiaux» intégrés dans l’espace et contenant de l’information qui n’est pas uniquement topologique. Les réseaux spatiaux sont très fréquents et il est important de les reconnaître en tant que tels, car leurs propriétés sont très différentes de celles des réseaux complexes génériques. Dans ce chapitre, je présenterai les caractéristiques les plus importantes des réseaux spatiaux, ce qui les distingue des autres réseaux complexes et comment les contraintes spatiales induisent des propriétés spécifiques. Le but principal ici est de montrer ce qui leur est spé cifique et comment nous pouvons les caractériser quantitativement.

Haut de page

Texte intégral

The digitization of historical and archaeological data

1Recent digitization of various historical sources opens the exciting possibility of discussing quantitatively a large number of phenomena in the social and human sciences (Fig. 1). Geographical information systems then become a tool for scientists in many different disciplines. In particular, most of the data come under the form of networks, such as relations between individuals, or between settlements, roads or other infrastructures. The tools and ideas from studies on networks become central and an important effort is needed in order to diffuse this new knowledge among scientists working in various disciplines.

2The papers in this volume demonstrate how archaeologists and historians are now making increasing use of network methods to understand social dynamics. However, the data available in such contexts are invariably spatial in nature, and so what I wish to do in this paper is address some of the key issues in understanding and modeling spatial networks. More precisely, most archaeological datasets are georeferenced and the corresponding networks are embedded in space and as such are spatial networks. It is then a very common occurrence to encounter spatial networks and it is important to recognize them as such, as their properties are very different from generic complex networks. In particular, interesting information about a spatial network is very specific and different from generic complex networks. In this chapter, I will discuss the most salient facts about spatial networks, how they are different from complex networks and how spatial constraints induce specific properties. The main purpose is to contribute to an understanding of what is generic about spatial networks and how we can characterize them.

Fig. 1

Fig. 1

Thanks to the efforts of GIS scientists (Batty 2005), we now have digitized maps, combined with data from remote sensing, which allow the study of the time evolution of spatial networks such as roads and streets over long periods. We show here the evolution from 1833 to 2007 of a road network in Italy (for each map we show in grey all the nodes and links already existing in the previous snapshot of the network, and in dark the new links added in the time window under consideration). (b) Map showing the location of the studied area (Groane area in the metropolitan region of Milan). (c) Time evolution of the total number of nodes N in the network and of the total population in the area (obtained from census data). Figure taken from Strano et al. 2012.

Complex and spatial networks

3There has been an intense activity these last 10 years on complex networks (Albert & Barabási 2002 ; Barrat et al. 2008) with many new empirical results and models that are impossible to review thoroughly here. In fact, networks (or graphs) were for a long time the subject of many studies in mathematics, mathematical sociology, computer science and quantitative geography. The most important model of random networks was proposed by Erdös and Rényi (Erdös & Rényi 1960) at the end of the 1950s and was at the basis of most studies until recently. The interest in networks was renewed in 1998 by Watts and Strogatz, who extracted stylized facts from real-world networks and proposed a simple, new model of random networks (Watts & Strogatz 1998), and further reinforced a year later by the publication of an article by Albert and Barabási (Barabási & Albert 1999) on the existence of strong degree heterogeneities. Strong heterogeneities are in sharp contrast with the random graphs considered so far and the existence of strong fluctuations in real-world networks triggered a wealth of studies. A decade later, we can now find many books on this subject (Dorogovtsev & Mendes 2013 ; Barrat et al. 2008; Caldarelli 2007 ; Newman 2010 ; Cohen & Havlin 2010).

Spatial networks

4These books and most reviews usually only discuss spatial aspects of networks very briefly. However, for many infrastructures, communication or biological networks, space is relevant: power grids and transportation networks depend obviously on distance, many communication network devices have short radio range, the length of axons in a brain has a cost, and the spread of contagious diseases is not uniform across territories. In particular, in the important case of the brain, regions that are spatially closer have a higher probability of being connected than remote regions, as longer axons are more costly in terms of material and energy (Bullmore & Sporns 2009). Another particularly important example of a spatial network is the Internet, which is defined as the set of routers linked by physical cables with different lengths and latency times. More generally, the distance could be another parameter such as a social distance measured by salary, socio-professional category differences, or any quantity that measures the cost associated with the formation of a link.

5All these examples show that in many real-world cases, networks have nodes and edges which are constrained by some geometry and are usually embedded in a two- or three-dimensional space. This has important effects on their topological properties and consequently on processes which take place on them. If there is a cost associated to the edge length, longer links must be compensated by some advantage, such as being connected to a well-connected node – that is, a hub. The topological aspects of the network are then correlated to spatial aspects such as the location of the nodes and the length of edges.

6More generally, the term `spatial network’ has come to be used to describe any network in which the nodes are located in a space equipped with a metric (Barthelemy 2011). For most practical applications, the space is the two-dimensional space and the metric is the usual Euclidean distance. For these networks we thus need both the topological information about the graph (given by the adjacency matrix) and the spatial information about the nodes (given by the position of the nodes). Transportation and mobility networks, Internet, mobile phone networks, power grids, social and contact networks, neural networks, are all examples where space is relevant and where topology alone does not contain all the information.

7All planar graphs can be embedded in a two-dimensional space and can be represented as spatial networks but the converse is not necessarily true: there are some spatial and non-planar graphs. In general however, most spatial networks are, to a good approximation, planar graphs (Clark & Holton 1991), such as road or railway networks but there are some important exceptions such as the airline network (Barrat et al. 2004); in this case the nodes are airports and there is a link connecting two nodes if there is at least one direct connection. For many infrastructure networks, however, planarity is unavoidable. Power grids, roads, rail, and other transportation networks are to a very high level of accuracy planar networks. For many applications, planar spatial networks are the most important and most studies have focused on these examples.

Social networks and space

8Also, the above definition does not imply that the links are necessarily embedded in space. Indeed, in social networks, individuals are connected through a friendship relation, which is a virtual network of relations. However, it is reasonable to think that in order to minimize their effort to maintain social ties (Zipf 1949) most individuals will connect to their spatial neighbors. The consequence is that even social networks have an important spatial component and that they will not behave as complex networks where space is irrelevant.

9Recent studies on online communities confirmed that and showed that most of the people have their friends and relatives in their neighbourhood. More quantitatively, it has indeed been shown that the probability that individuals located in space are friends generally decreases with the distance r between them as (Liben-Nowell et al. 2005):

10It is important to realize here that when dealing with social networks, we are in fact usually working on a particular type of spatial network.

Spatial networks and Quantitative geography

11Spatial networks were actually the subject a long time ago of many studies in quantitative geography. Objects of studies in geography are locations, activities, flows of individuals and goods, and already in the 1970s scientists working in quantitative geography focused on networks evolving in time and space. One can, for example, consult books such as the remarkably modern ‘Network Analysis in Geography’ by Haggett & Chorley (published in 1969) to realize that many modern questions in the complex system field are actually almost 50 years old. In these books, the authors discuss the importance of space in the formation and evolution of networks. They develop tools to characterize spatial networks and discuss possible models. Maybe what was lacking at that time were datasets of large networks and larger computer capabilities, but a lot of interesting thoughts can be found in these early studies. Most of the important problems such as the location of nodes of a network, the evolution of transportation networks and their interaction with population and activity density are addressed in these earlier studies, but many important points still remain unclear and will certainly benefit from the current knowledge on networks and complex systems.

Tools for characterizing spatial networks

12We overview briefly here the main tools which can characterize quantitatively large spatial networks. More information can be found in the review by Barthelemy (2011). Graphs are usually characterized by the adjacency matrix A where the elements are Aij=1 if nodes i and j are connected (see for example a graph textbook, Clark & Holton 1991). This matrix completely characterizes the topology of the graph and is enough for most applications. This is however not the case for spatial networks where the spatial information is contained in the location of the nodes {xi}. Two topologically identical graphs can then have completely different spatial properties and this is at the heart of the richness and complexity of spatial networks. In this section we will discuss some tools that are helpful in characterizing some aspects of spatial networks and how we can distinguish them from generic, ‘non-spatial’ complex networks.

Degree distribution, Clustering and average shortest path length

Degree distribution

13In complex networks, the degree distribution, the clustering spectrum and the average shortest distance are of utmost importance (Albert & Barabási 2002). Their knowledge already gives a useful picture of the graph under study. A very important finding by Barabási in 1999, is the fact that the degree distribution can be very broad and behaves usually as a power law:

14where the exponent γ is usually in the range [2,3]. In particular when γ = 3, preferential attachment (Barabási & Albert 1999) can be a plausible model for the formation and evolution of the corresponding network. This form which contains no intrinsic scale (hence the name of scale-free networks) implies that the variance is very large and the average degree has no meaning : some nodes have very large degrees and are known as hubs. The existence of such hubs has important consequences on many processes taking place on networks, such as epidemic spread or synchronization, etc.

15In sharp contrast with most complex networks, the physical constraints existing in spatial networks determine some of their properties. In particular, there is usually a sharp cut-off on the degree distribution P(k) and is therefore peaked around its average (Amaral et al. 2000).

16In other words, the range of variation of degrees is usually very small, or equivalently, the maximum degree is not very different from the average degree. This is true for most spatial and planar networks such as power grids or transportation networks for example. For a spatial, non-planar network such as the airline network, the cut-off can be large enough and the degree distribution could be characterized as broad. In general however, the range of values of the degree k is very limited and we cannot observe scale-free features in spatial networks (Fig. 2).

Fig. 2

Fig. 2

On the left, a typical peaked degree distribution P(k) that can be found for most spatial networks : the dispersion around the average is small. For scale-free networks (right panel), the distribution is broad and usually is a power law (here shown in log-log with exponent 3). The dispersion is growing with the size of the network and the average has no meaning here.

Clustering

17The clustering coefficient of a node counts how its neighbours are connected with each other. For spatial networks, the dominant mechanism is usually to minimize a cost associated with length, and nodes have a tendency to connect to their nearest neighbours, independently from their degree. This in general implies that the clustering spectrum C(k) is relatively flat for spatial networks. The same argument can be used to show that the assortativity ‘spectrum’ defined as the function knn(k) is also approximately constant in general when spatial constraints are very strong (see Barthelemy 2011 for more details).

18Average shortest distance

19Usually, there are many paths between two nodes in a connected network and the shortest one defines a distance on the network:

20where the length |path| of the path is defined as its number of edges. This quantity is infinite when there are no paths between the nodes and is equal to one for the complete graph (for which l(i,j)=1 for all i and j).

21In most complex networks, one observes a small-world behavior (Watts & Strogatz 1998) of the form:

22where N is the number of nodes in the network. Even for large N, we still have a very small average shortest path (of order 6 for N of order a million), which justifies the name of small-world network. In contrast, for a real-world spatial network embedded in a d-dimensional space, we usually observe the very different behavior:

23where d is the dimension of the embedding space and is d = 2 for most cases. This result also means that to go from one node to another one, one has to cross a path of length of the order the diameter (which is not the case when shortcuts exist, such as in small-world networks). The measure of the average shortest path length could thus be a first indication whether a network is spatial and close to a lattice or if long-range links are important.

Organic ratio

24We note that more recently, other interesting indices were proposed in order to characterize specifically road networks (Xie & Levinson 2007). Indeed, the degree distribution is very peaked around 3-4 and interesting information is given by the ratio:

25where N(k) is the number of nodes of degree k. If this ratio is small the number of dead ends and of `unfinished’ crossing (k=3) is small compared to regular crossing with k=4, signalling a more organized city. In the opposite case of rN close to 1, there is a dominance of k=1 and k=3 nodes which signals a more ‘organic’ city.

Betweenness centrality

26The importance of a node is characterized by its so-called centrality. There are however many different centrality indicators such as the degree, the closeness, etc., but we will focus here on the betweenness centrality (BC) g(i) which is defined as (Freeman 1977):

27where σst is the number of shortest paths going from s to t and σst(i) is the number of shortest paths going from s to t through the node i. This quantity g(i) thus characterizes the importance of the node i in the flows in this network. Note that with this definition, the BC of terminal nodes is zero (also, the BC can similarly be defined for edges). The betweenness centrality of a vertex is determined by its ability to provide a path between separated regions of the network.

28Hubs are natural crossroads for paths and it is natural to observe a marked correlation between large values of the degree k of a node and its BC. We expect this correlation to be altered when spatial constraints become important and in order to understand this effect we consider a one-dimensional lattice, which is the simplest case of a spatially ordered network. For this lattice the shortest path between two nodes is simply the euclidean geodesic and for two points lying far from each other, the probability that the shortest path passes near the barycentre of the network is very large. In other words, the barycentre (and its neighbours) will have a large centrality as illustrated in Figure 3a.

29In contrast, in a purely topological network with no underlying geography, this consideration does not apply anymore and if we rewire more and more links (as illustrated in Figure 3b) we observe a progressive decorrelation of centrality and space while the correlation with degree increases. In a lattice, it is easy to show that the BC depends on space and is maximum at the barycentre, while in a network the BC of a node depends on its degree. When the network is constituted of long links superimposed on a lattice, we then expect the appearance of ‘anomalies’ characterized by small degree and large BC (or conversely).

Fig. 3a

Fig. 3a

(a) Betweenness centrality for the (one-dimensional) lattice case. The central nodes are close to the barycentre.

Fig. 3b

Fig. 3b

(b) For a general graph, the central nodes are usually the ones with large degree.

30The spatial distribution of the BC thus contains a lot of information about the global structure of the network. We illustrate this on the example of the evolution of the street network of Paris over more than 200 years with a particular focus on the 19th century, a period when Paris experienced large transformations under the guidance of Baron Haussmann. It would be difficult to describe the social, political, and urbanistic importance and impact of Haussmann’s works in a few lines here and we refer the interested reader to the existing abundant literature on the subject (see Jordan 1995 and references therein). Essentially, until the middle of the 19th century, central Paris had a medieval structure composed of many small and crowded streets, creating congestion and, according to some contemporaries, probably health problems. In 1852, Napoleon III commissioned Haussmann to modernize Paris by building safer streets, large avenues connected to the new train stations, central or symbolic squares (such as the famous place de l’Etoile, place de la Nation and place du Panthéon), improving the traffic flow and, last but not least, the circulation of army troops. By digitizing historical maps into a Geographical Information System (GIS) environment, we reconstruct the detailed road system (including minor streets) at six different moments in time: 1789, 1826, 1836, 1888, 1999, and 2010. For each time, we constructed the associated primal graph Gt (see Barthelemy 2011 ; Strano et al. 2012), i.e. the graph where the nodes represent street junctions and the links correspond to road segments. We have thus snapshots of the street network before Haussmann’s works (1789-1836) and after (1888-2010) which allows us to study quantitatively the effect of such central planning.

31Surprisingly enough, most quantitative measures on these networks reveal nothing but a natural evolution of the network. The average degree is roughly constant and the total length of the network scales as any almost regular lattice (Barthelemy et al. 2013). In sharp contrast, the spatial distribution of the BC reveals the important structural changes, as shown in Figure 4. In particular, we observe a very important redistribution of centrality during the Haussmann period with the appearance of a reticulated structure on the 1888 map. This example illustrates well the fact that interesting information lies in the interplay between space and topology of the network, and that this is revealed by simply mapping the BC.

Fig. 4

Fig. 4

Spatial distribution of the most central nodes (with centrality gv such that gv>max{gv}/10). We observe for the different periods important reorganization of the spatial distribution of centrality, corresponding to different specific interventions. In particular, we observe a very important redistribution of centrality during the Haussmann period with the appearance of a reticulated structure on the 1888 map.

Mixing space and topology

32All the previous indicators describe essentially the topology of the network but are not specifically designed to characterize spatial networks. We will here briefly review other indicators that provide useful information about the spatial structure of networks. Different indices were defined a long time ago mainly by scientists working in quantitative geography since the 1960s and can be found in Haggett & Chorley (1969 ; see also the more recent paper by Xie & Levinson 2007). Most of these indices are relatively simple but still give important information about the structure of the network in particular if we are interested in planar networks. These indices were used so far to characterize transportation networks such as highways or railway systems.

Alpha and Gamma indices

33The most important indices are called the ‘alpha’ and the ‘gamma’ indices. The simplest index is called the gamma index and is simply defined by:

34where E is the number of edges and Emax is the maximal number of edges (for a given number of nodes N). For non-planar networks, Emax is given by N(N-1)/2 for non-directed graphs and for planar graphs Emax=3N-6 leading to:

35The gamma index is a simple measure of the density of the network but one can define a similar quantity by counting, not the edges, but the number of elementary cycles. The number of elementary cycle for a network is know as the cyclomatic number (see for example Clark & Holton 1991) and is equal to:

36For a planar graph this number is always less or equal to 2N-5 which leads naturally to the definition of the alpha index:

37This index belongs to [0,1] and is equal to 0 for a tree and equal to 1 for a maximal planar graph.

Cell area and shape

38For planar spatial networks, we have faces (or cells, or blocks for road networks) which have a certain area and shape. In certain conditions, it can be interesting to characterize statistically these shapes and various indicators were developed in this perspective (see Haggett & Chorley 1969, for a list of these indicators).

39The first, simple important information is the distribution of the area P(A) which for many cases follows a power law (Lammer et al. 2006 ; Barthelemy 2011):

40where t @ 2. We can note here that a simple argument on node density fluctuation leads indeed to this value t =2 and further empirical analysis is needed to test the universality of this result. In addition to the area of the cell, its shape distribution is also interesting and contains a large part of the information about the structure of the network. A simple way to characterize the shape is given by the form factor f. If we denote by L the major axis, the shape ratio is defined as A/L2. In the paper (Lammer et al. 2006) on the road network structure, another definition is used:

41where pD2 is the area of the circumscribed circle. If this ratio is small, the cell is very anisotropic, while on the contrary if f is closer to one, the corresponding cell is almost circular. In many cases where rectangles and squares predominate (Lammer et al. 2006 ; Strano et al. 2012), we have f @ 0.5-0.6.

Detour index

42When the network is embedded in a two-dimensional space, we can define at least two distances between the pairs of nodes. There is of course the natural euclidean distance dE(i,j) which can also be seen as the ‘as the crow flies’ distance. There is also the total ‘route’ distance dR(i,j) from i to j by computing the sum of lengths of segments belonging to the shortest path between i and j. The detour index—also called the route factor—for this pair of nodes (i,j) is then given by (see Figure 5 for an example):

43This ratio is always larger than one and the closer to one, the more efficient the network.

44From this quantity, we can derive many others. The statistics of Q(i,j) are important and contain a lot of information about the spatial network under consideration (see Aldous & Shun 2010 for a discussion on this quantity for various networks) and one can define the interesting quantity for example (Aldous & Shun 2010):

45(where Nd is the number of nodes such that dE(i,j)=d) whose shape can help characterizing combined spatial and topological properties. This profile tells us, for various classes of euclidean distances, how efficient is the network.

Fig. 5

Fig. 5

Example of detour index calculation. The ‘as the crow flies’ distance between the nodes A and B is dE(A,B) = √10 while the route distance over the network is dR (A,B) = 4 leading to a detour index equal to Q (A,B) = 4 / √10 = 1.265.

Cost and Efficiency

46The minimum number of links to connect N nodes is E=N-1 and the corresponding network is then a tree. We can look for the tree which minimizes the total length given by the sum of the lengths of all links:

47where dE(e) denotes the length of the link e. This procedure leads to the minimum spanning tree (MST) which has a total length lTMST (see for example Clark & Holton 1991), and which can serve as a useful benchmark : it is the graph which connects all the nodes with a minimal cost. Obviously the tree is not a very efficient network (from the point of view of transportation for example) and usually more edges are added to the network, leading to an increase of accessibility but also of lT. A natural measure of the ‘cost’ of the network is then given by:

48Another measure of efficiency was also proposed in Latora & Marchiori (2001) and is defined as:

49where l  (i, j) is the shortest path distance from i to j. Combination of these different indicators and comparisons with the MST or the maximal planar network can be constructed in order to characterize various aspects of the networks under consideration (see for example Buhl et al. 2006).

Simplicity

50Shortest paths are not always simple. In planar networks, they can be very different from those with the smallest number of turns – the simplest paths. The statistical comparison of the lengths of the shortest and simplest paths provides non-trivial and non-local information about the spatial organization of these graphs. It tells us how the straight lines are organized in the system and in the case of time evolving networks, their simplicity is able to reveal important structural changes during their evolution.

51Generally speaking, we can define different types of paths for a given pair of nodes (i,j). A usual quantity is the shortest euclidean path of length l(i,j) which minimizes the distance travelled to go from i to j. We can however ask for another path which minimizes the number of turns – the simplest path, of length l*(i,j) (if there is more than one such path we choose the shortest one).

52To identify the simplest path, we first convert the graph from the primal to the dual representation, where each node corresponds to a straight line in the primal graph. These straight lines are determined by a continuity negotiation-like algorithm (Porta et al. 2006). Edges in dual space, in turn, represent the intersection of straight lines in the primal graph.

53We define the number of turns t of a given path as the number of switches from one straight line to another when walking along this path. This quantity is intimately related to the amount of information required to move along the path (Rosvall et al. 2005). This quantity is however not very useful for distinguishing different networks and contains very partial information about the spatial structure of the simplest paths. For navigation purposes and in order to understand the structure of the network, it is useful to compare the lengths of the shortest and the simplest paths with the ratio l *  (i,j)/l (i,j)>1. It is then natural to introduce the simplicity index S as the average:

54The simplicity index is larger than one and exactly equal to one for a regular square lattice and any tree-like network for example. Large values of S indicate that the simplest paths are on average much longer than the shortest ones, and that the network is not easily navigable. This metric is a first indication about the spatial structure of simplest paths but mixes various scales, and in order to obtain a more detailed information, we can use the simplicity profile:

55where dE(i,j) is the euclidean distance between i and j and where N(d) is the number of pairs of nodes at euclidean distance d. This quantity S(d) is larger than one and its variation with d informs us about the large scale structure of these graphs. We can draw a generic shape of this profile: for small d, we are the scale of nearest neighbors and there is a large probability that the simplest and shortest paths have the same length, yielding S(dg0)@1, and increasing for small d. For very large d, it is almost always beneficial to take long straight lines when they exist, thus reducing the difference between the simplest and the shortest paths. As a result we expect S(d) to decrease when ddmax (note that a similar behavior is observed for another quantity, the route-length efficiency, introduced in Aldous & Shun 2010). The simplicity profile will then display in general at least one maximum at an intermediate scale d* for which the length differences between the shortest and the simplest path is maximum. The length d* thus represents the typical size of domains not crossed by long straight lines. At this intermediate scale, the detour needed to find long straight lines for the simplest paths is very large.

56We can illustrate these measures on two datasets describing the time evolution of networks at different scales (see Figure 6). The first example of a time evolving network is the road network of the Groane region which is a 125km2 area located north of Milan (Strano et al. 2012). We have 7 snapshots of this network for different times from 1833 to 2007. This region evolved without central planning and is thus a good example of an `organic’ evolution of urban systems. The simplicity profile shown in Figure 6a allows us to distinguish two different periods. The first period from 1833 to 1955 displays a relatively small simplicity at all scales, while a distinct second regime appears from 1980 until now. In this latter regime, the simplicity profile is substantially larger for all scales. This is an effect of the massive urban densification, leading to a polycentric structure where the readability and the ease of navigation are drastically lowered.

Fig. 6

Fig. 6

Simplicity profiles for time-varying networks. We represent here the profiles for (a) the road network of the Groane region (Italy), (b) the street network of Paris (France) in the pre-Haussmannian (1789, 1836) and post-Haussmannian (1999) periods. We observe on (a) and (b) that the evolution of the profile can reveal important structural changes. Figure taken from Viana et al. 2013.

57At a smaller scale, we study the evolution of central Paris between 1789 and 1999. This dataset provides an interesting case study, as Paris experienced large changes due to Haussmann in the middle of the 19th century (see Barthelemy et al. 2013 for details and more references about this network). This is an opportunity to observe quantitatively the effect of top-down planning: until 1836, we are in the pre-Haussmann Paris, while from 1888 until now we are in the post-Haussmann period. The effect of Haussmann’s central planning is clearly visible on the network shown in Figure 6b. From 1789 to 1836, we have a relatively large simplicity at all scales and we observe a decrease in that period at small scales (d/dmax<0.4) which corresponds well to the fact that many religious and aristocratic domains and properties were sold and divided in order to create new houses and new roads, improving congestion inside Paris. The 1826-1836 transition displays a decrease of the simplicity for distance larger than roughly 5 kms (corresponding to d/dmax=0.6) indicating that long distance routes were simplified. It is interesting to note that during this period the eastern part of Paris experienced large transformations with the construction of the Canal St. Martin. Finally in the period 1836 to 1888, when Paris underwent Haussmann’s transformation, the simplicity profile is strongly affected: compared to 1836, the simplicity is improved in the range d/dmax in [0.3,0.8], which can be attributed to the construction of large avenues connecting important nodes of the city. In addition, we observe the surprising effect that at large scales d/dmax>0.8, the simplicity is degraded by Haussmann’s work: this however could be an artefact of the method and the fact that we considered a portion of Paris only and neglected the effect of surroundings.

Detecting communities

58Community detection in graphs became an important topic in complex network studies (see the review Fortunato 2010), but after almost a decade of efforts, there are no definitive methods of identification of communities. Loosely speaking, a community (or a ‘module’) is a set of nodes which have more connections among them than with the rest of nodes. One of the first and simplest methods to detect these modules is the modularity optimization and consists in maximizing the quantity called modularity and which is defined as (Newman & Girvan 2004):

59where the sum is over the nM modules of the partition, ls is the number of links inside module s, E is the total number of links in the network, and ds is the total degree of the nodes in module s. The first term of the summand in this equation is the fraction of links inside module s and the second term represents the expected fraction of links in that module if links were located at random in the network (and by keeping the same degree distribution). The number of modules nM is also a variable whose value is obtained by the maximization. If for a subgraph S of a network the first term is much larger than the second, it means that there are many more links inside S than one would expect by random chance, so S is indeed a module. The comparison with the null model represented by the randomized network is however misleading and small modules connected by at least a link might be seen as one single module. This resolution limit (see Fortunato 2010) states that modules of size E1/2 or smaller might not be detected by this method. Modularity detection was however applied in many different domains and is still used.

60When applied to the worldwide air transportation network, we obtain results shown in Figure 7 where each colour corresponds to a community. We immediately can see that most of these communities are actually determined by geographical factors and therefore are not very informative: the most important flows are among nodes in the same geographical regions. More interesting are the spatial anomalies which belong to a community from the modularity point of view but which are in another geographical region. For example, the ‘red’ community of Western Europe also contains airports from Asian Russia. More generally, it is clear that in the case of spatial networks, community detection offers a visual representation of large exchange zones. It also allows the identification of inter-community links which play probably a very important role in many processes such as disease spread for example.

Fig. 7

Fig. 7

Communities of the worldwide air transportation network obtained with modularity optimization. Each node represents an airport and each grey level corresponds to a community. From Guimera et al. 2005.

Summary: Existence of general features of spatial networks

61Through the different examples presented in this chapter, we see that some general features emerge. Space implies a cost associated to distance and the formation of long links must be justified for a ‘good economical’ reason, such as a large degree for example. This simple observation leads to various effects that we summarize here.

Network typology

62We can roughly divide spatial networks in two categories. The first one consists of planar networks. These networks possess many features similar to lattices but in some cases (such as the road network) possess very distinctive features which call for the need of new models. The other category consists of non-planar networks such as the airline network, the cargo ship network, or the Internet where nodes are located in spaces, edges have a cost related to their length, but where we can have intersecting links. We note here that in some cases such as for the Internet, the point distribution is not always uniform and could play an important role.

Effect of space on P(k)

63Spatial constraints restrict the appearance of large degrees and P(k) is usually peaked. Constraints are stronger for planar networks and for non-planar spatial networks such as airlines the degree distribution can be broad.

Effect of space on the link distribution

64Here also the spatial constraints limit severely the length of links. For planar networks such as roads and streets, the distribution is peaked, while in other networks, such as the Internet or the airline network, the distribution can be broader.

Effect of space embedding on clustering and assortativity

65Spatial constraints implies that the tendency to connect to hubs is limited by the need to use small-range links which explains the almost flat behaviour observed for the assortativity. Connection costs also favor the formation of cliques between spatially close nodes and thus increase the clustering coefficient.

Effect of space on the average shortest path

66The average shortest path for two dimensional planar networks scales as N1/2 as in a regular lattice. When enough shortcuts (such as in the Watts-Strogatz model) are present, this square root behaviour is modified and becomes logarithmic.

Effect of space embedding on centrality

67Spatial constraints also induce large betweenness centrality fluctuations. While hubs are usually very central, when space is important central nodes tend to get closer to the gravity centre of all points. Correlations between spatial position and centrality compete with the usual correlations between degree and centrality, leading to large fluctuations of centrality at fixed degree.

Communities in space

68Spatial constraints also induce some neighbourhood properties : a node will likely be connected to another one which is not too far. Communities will then naturally correspond to spatial delimitation or barriers for example. Nodes that belong to a given community but which are not trivially spatially related to it contain interesting information.

Discussion and outlook

69More and more historical data are being digitized and network science appears as an important tool for analyzing them. When the data are georeferenced, the networks that appear are actually spatial networks for which space is a very important component. Nodes such as homes, individuals, settlements, have a particular location in space and the relations between them imply the notion of distance : individuals are connected to their neighbours, and villages and cities develop for reasons of proximity. Roughly speaking, as soon as distance plays a role in the formation of links in a network, one has to be careful with its analysis. The spatial aspect determines the way we characterize these networks and how we extract useful information. For spatial networks, most of the richness and complexity actually comes from space, and the interplay between the topology and the spatial distribution of nodes is at the heart of the structure of these networks.

70For these spatial networks, it is important to distinguish the ‘pure’ spatial part which could have been expected for purely spatial reasons, from other reasons which may contain more interesting information (social, economic, etc.). Social networks for example are mostly spatial, and the probability that two individuals are connected usually decreases with distance. The study of spatial features of relations in a social network thus allows the identification of ‘anomalous’ relations whose probability—based on space only—is very low, but which nevertheless are observed in real situations. Such ‘unexpected’ links might play an important role in many phenomena such as migrations or relations between villages. Communities in networks will also contain a trivial spatial component and nodes which belong to a certain community without being in its neighbourhood, are ‘anomalies’ which contain interesting information (Barthelemy 2011). The importance of these meaningful links and nodes goes beyond social networks and could actually be very relevant in other, more abstract networks made of objects, texts, or places.

71One of the main goal is to disentangle the various effects in the formation and evolution of a network and to identify the hierarchy of mechanisms. This hierarchy in turn will then be hepful in constructing a model based on a minimal number of parameters and assumptions.

72In summary, we presented briefly in this chapter some of the tools that can help in recognizing these networks and to characterize them, and we tried to illustrate that through various examples. The application of these tools to archaeological studies seems promising in meeting some of the current challenges in historical network studies (Collar et al., Rivers & Evans, this volume). For example, the diffusion of cultural traits or dialects (Bevan & Crema, this volume) happens because of the movements of individuals which is controlled by a network of friendship and commercial relations. The structure of these spatial networks is crucial as it will have a profound influence on the velocity of such diffusion. Obviously, the list of tools given here is not exhaustive, and maybe more crucially it is important to keep in mind that in many situations one has to create new tools or to adapt existing ones to the questions asked and to the dataset studied.

Haut de page

Bibliographie

Aldous D.J. & Shun J. 2010. “Connected spatial networks over random points and a route-length statistic”, Statistical Science, 25: 275-288.

Albert R. & Barabasi A.L. 2002. “Statistical mechanics of complex networks”, Reviews of modern physics, 74: 47.

Amaral L.A.N., Scala A., Barthelemy M. & Stanley H.E. 2000. Classes of small-world networks. Proceedings of the National Academy of Sciences, 97(21), 11149-11152.

Barabasi A.L. & Albert R. 1999. “Emergence of scaling in random networks”, Science, 286(5439): 509-512.

Barrat A., Barthelemy M. & Vespignani A. 2008. Dynamical processes in complex networks. Cambridge University Press.

Barrat A., Barthelemy M., Pastor-Satorras R. & Vespignani A. 2004. The architecture of complex weighted networks. Proc. Natl. Acad. Sci. USA, 101: 3747.

Barthelemy M. 2011. “Spatial Networks”, Physics Reports, 499:1.

Barthelemy M., Bordin P., Berestycki H. & Gribaudi M. 2013. “Self-organization versus top-down planning in the evolution of a city”, Nature Scientific Reports, 3:2153.

Batty M. 2005. Cities and complexity. The MIT Press, Cambridge, MA, 2005.

Buhl J., Gautrais J., Reeves N., Solé R.V., Valverde S., Kuntz P. & Theraulaz G. 2006. “Topological patterns in street networks of self-organized urban settlements”, The European Physical Journal B-Condensed Matter and Complex Systems, 49(4): 513-522.

Bullmore E. & Sporns O. 2009. “Complex brain networks: graph theoretical analysis of structural and functional systems”, Nature Reviews Neuroscience, 10(3): 186-198.

Caldarelli G. 2007. Scale-free networks : Complex Webs in Nature and Technology. Oxford Finance, Oxford University Press.

Clark J. & Holton D.A. 1991. A first look at graph theory. World Scientific Publishing Company Incorporated.

Cohen R. & Havlin S. 2010. Complex Networks - Structure, Robustness and Function. Cambridge University Press.

Dorogovtsev S.N. & Mendes J.F. 2013. Evolution of networks: From biological nets to the Internet and WWW. Oxford University Press.

Erdos P. & Rényi A. 1960. “On the evolution of random graphs”, Publ. Math. Inst. Hung. Acad. Sci, 5: 17-61.

Fortunato S. (2010). ”Community detection in graphs”, Physics Reports486(3), 75-174.

Freeman L.C. 2007. “A set of measures of centrality based on betweenness”, Sociometry, 40,1: 35-41.

Guimerà R., Mossa S., Turtschi A. & Amaral L. N. 2005. The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles. Proceedings of the National Academy of Sciences, 102(22), 7794-7799. Haggett P. & Chorley R.J. 1969. Network analysis in geography. Edward Arnold, London.

Jordan D. 1995. Transforming Paris: The Life and Labors of Baron Haussmann. University of Chicago Press, Chicago.

Lammer S., Gehlsen B. & Helbing D. 2006. “Scaling laws in the spatial structure of urban road networks”, Physica A: Statistical Mechanics and its Applications, 363(1): 89-95.

Latora V. & Marchiori M. 2001. “Efficient behavior of small-world networks”, Physical Review Letters, 87: 198701.

Liben-Nowell D., Novak J., Kumar R., Raghavan P. & Tomkins A. 2005. Geographic routing in social networks. Proceedings of the National Academy of Sciences of the United States of America, 102: 11623-11628.

Newman M. 2010. Networks: an introduction. Oxford University Press.

Newman M. E. & Girvan M. 2004. “Finding and evaluating community structure in networks”, Physical review E, 69(2), 026113.

Porta S., Crucitti P. & Latora V. (2006). “The network analysis of urban streets: a dual approach”, Physica A: Statistical Mechanics and its Applications369(2): 853-866.

Rosvall M., Trusina A., Minnhagen P. & Sneppen K. 2005. “Networks and cities: An information perspective”, Physical Review Letters, 94(2), 028701.

Strano E., Nicosia V., Latora V., Porta S. & Barthelemy M. 2012. “Elementary processes governing the evolution of road networks”, Nature Scientific Reports, 2: 296.

Viana M. P., Strano E., Bordin P. & Barthelemy M. 2013. The simplicity of planar networks. Scientific reports, 3.

Watts D. & Strogatz S. 1998. “Collective Dynamics of Small-World Networks”, Nature, 393: 440-442.

Xie F. & Levinson D. 2007. “Measuring the structure of road networks”, Geographical Analysis, 39: 336-356.

Zipf G.K. 1949. Human behavior and the principle of least effort. Addison-Wesley.

Haut de page

Table des illustrations

Titre Fig. 1
Légende Thanks to the efforts of GIS scientists (Batty 2005), we now have digitized maps, combined with data from remote sensing, which allow the study of the time evolution of spatial networks such as roads and streets over long periods. We show here the evolution from 1833 to 2007 of a road network in Italy (for each map we show in grey all the nodes and links already existing in the previous snapshot of the network, and in dark the new links added in the time window under consideration). (b) Map showing the location of the studied area (Groane area in the metropolitan region of Milan). (c) Time evolution of the total number of nodes N in the network and of the total population in the area (obtained from census data). Figure taken from Strano et al. 2012.
URL http://nda.revues.org/docannexe/image/2374/img-1.jpg
Fichier image/jpeg, 472k
URL http://nda.revues.org/docannexe/image/2374/img-2.jpg
Fichier image/jpeg, 16k
URL http://nda.revues.org/docannexe/image/2374/img-3.jpg
Fichier image/jpeg, 16k
Titre Fig. 2
Légende On the left, a typical peaked degree distribution P(k) that can be found for most spatial networks : the dispersion around the average is small. For scale-free networks (right panel), the distribution is broad and usually is a power law (here shown in log-log with exponent 3). The dispersion is growing with the size of the network and the average has no meaning here.
URL http://nda.revues.org/docannexe/image/2374/img-4.jpg
Fichier image/jpeg, 224k
URL http://nda.revues.org/docannexe/image/2374/img-5.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-6.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-7.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-8.jpg
Fichier image/jpeg, 28k
URL http://nda.revues.org/docannexe/image/2374/img-9.jpg
Fichier image/jpeg, 24k
Titre Fig. 3a
Légende (a) Betweenness centrality for the (one-dimensional) lattice case. The central nodes are close to the barycentre.
URL http://nda.revues.org/docannexe/image/2374/img-10.jpg
Fichier image/jpeg, 112k
Titre Fig. 3b
Légende (b) For a general graph, the central nodes are usually the ones with large degree.
URL http://nda.revues.org/docannexe/image/2374/img-11.jpg
Fichier image/jpeg, 128k
Titre Fig. 4
Légende Spatial distribution of the most central nodes (with centrality gv such that gv>max{gv}/10). We observe for the different periods important reorganization of the spatial distribution of centrality, corresponding to different specific interventions. In particular, we observe a very important redistribution of centrality during the Haussmann period with the appearance of a reticulated structure on the 1888 map.
URL http://nda.revues.org/docannexe/image/2374/img-12.jpg
Fichier image/jpeg, 1,3M
URL http://nda.revues.org/docannexe/image/2374/img-13.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-14.jpg
Fichier image/jpeg, 24k
URL http://nda.revues.org/docannexe/image/2374/img-15.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-16.jpg
Fichier image/jpeg, 24k
URL http://nda.revues.org/docannexe/image/2374/img-17.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-18.jpg
Fichier image/jpeg, 20k
URL http://nda.revues.org/docannexe/image/2374/img-19.jpg
Fichier image/jpeg, 28k
URL http://nda.revues.org/docannexe/image/2374/img-20.jpg
Fichier image/jpeg, 36k
Titre Fig. 5
Légende Example of detour index calculation. The ‘as the crow flies’ distance between the nodes A and B is dE(A,B) = √10 while the route distance over the network is dR (A,B) = 4 leading to a detour index equal to Q (A,B) = 4 / √10 = 1.265.
URL http://nda.revues.org/docannexe/image/2374/img-21.jpg
Fichier image/jpeg, 60k
URL http://nda.revues.org/docannexe/image/2374/img-22.jpg
Fichier image/jpeg, 28k
URL http://nda.revues.org/docannexe/image/2374/img-23.jpg
Fichier image/jpeg, 24k
URL http://nda.revues.org/docannexe/image/2374/img-24.jpg
Fichier image/jpeg, 28k
URL http://nda.revues.org/docannexe/image/2374/img-25.jpg
Fichier image/jpeg, 36k
URL http://nda.revues.org/docannexe/image/2374/img-26.jpg
Fichier image/jpeg, 40k
Titre Fig. 6
Légende Simplicity profiles for time-varying networks. We represent here the profiles for (a) the road network of the Groane region (Italy), (b) the street network of Paris (France) in the pre-Haussmannian (1789, 1836) and post-Haussmannian (1999) periods. We observe on (a) and (b) that the evolution of the profile can reveal important structural changes. Figure taken from Viana et al. 2013.
URL http://nda.revues.org/docannexe/image/2374/img-27.jpg
Fichier image/jpeg, 236k
URL http://nda.revues.org/docannexe/image/2374/img-28.jpg
Fichier image/jpeg, 32k
Titre Fig. 7
Légende Communities of the worldwide air transportation network obtained with modularity optimization. Each node represents an airport and each grey level corresponds to a community. From Guimera et al. 2005.
URL http://nda.revues.org/docannexe/image/2374/img-29.jpg
Fichier image/jpeg, 228k
Haut de page

Pour citer cet article

Référence papier

Marc Barthelemy, « Discussion: Social and spatial networks », Les nouvelles de l'archéologie, 135 | 2014, 51-61.

Référence électronique

Marc Barthelemy, « Discussion: Social and spatial networks », Les nouvelles de l'archéologie [En ligne], 135 | 2014, mis en ligne le 01 janvier 2016, consulté le 25 mai 2017. URL : http://nda.revues.org/2374 ; DOI : 10.4000/nda.2374

Haut de page

Auteur

Marc Barthelemy

Institut de Physique Théorique, Cea et Centre d’Analyse et de Mathématiques Sociales, Ehess,
marc.barthelemy@cea.fr

Haut de page

Droits d’auteur

© FMSH

Haut de page
  • Logo Éditions de la Maison des sciences de l'homme
  • Revues.org