Marc Barthelemy
email: marc.barthelemy@ipht.fr

Transitions in spatial networks

Networks embedded in space can display all sorts of transitions when their structure is modified. The nature of these transitions (and in some cases crossovers) can differ from the usual appearance of a giant component as observed for the Erdos-Renyi graph, and spatial networks display a large variety of behaviors. We will discuss here some (mostly recent) results about topological transitions, 'localization' transitions seen in the shortest paths pattern, and also about the effect of congestion and fluctuations on the structure of optimal networks. The importance of spatial networks in realworld applications makes these transitions very relevant and this review is meant as a step towards a deeper understanding of the effect of space on network structures.

INTRODUCTION

Even if networks became very fashionable these last two decades, there is even a longer history between networks and transitions. In their seminal paper Erdos and Renyi [1] showed at the end of the 50's the existence of a transition in random graph when the number of links increases. This Erdos-Renyi (ER) model [2,3] exists independently from space, but very early, Gilbert introduced a simple model of what we now call a spatial network [4]. In its simplest version, nodes in this model lie in the 2-dimensional space and are connected if their euclidean distance is less than a given threshold. This model also displays a transition for a specific value of the average degree and, similarly to the Erdos-Renyi model, this transition is of the percolation type characterized by the sudden appearance of a giant component connecting most nodes. Both these models triggered a lot of attention and many results were obtained, mosty by mathematicians (see for example [START_REF] Bollobás | Random graphs[END_REF][START_REF] Penrose | Random geometric graphs[END_REF]). More recently, networks embedded in space -spatial networks -became of interest as they describe many important systems in the real-world, ranging from transportation networks, infrastructures such as power grids, to biological structures such as the brain or veination patterns in leaves. For most of these networks, nodes are located in a two-dimensional space and links represent physical connections (cables, wires, axons, etc.). The central effect of space is then to associate a cost to the length of links and to the degree of a node: a long link is costly and is usually compensated by some advantage, and spatial constraints limit the degree and prohibits the appearance of broad distributions. It is this interplay that leads to the richness of these structures.

New network models were proposed that integrate the effect of space and are based in general on different mechanisms, from variants of the preferential attachment, to greedy models or optimal problems. Many of these models display various types of transitions or crossovers that we will describe here, but a clarification is needed at this point. In statistical physics, transitions are usually well defined: they describe how the system goes from one equilibrium phase to another one. These phases are usually described by different symmetries and the transition is characterized by a non-analytic behavior in the thermodynamic limit. We can also observe crossovers which in general involve a typical scale and which separate different regimes. The change is then more progressive and we don't have properties such as the loss of symmetry or non-analyticity. In 'non thermodynamical' (and in general 'complex') systems, the situation is not always clear and the meaning of the word transition is less strict. The absence of a free energy function for these sytems leaves the freedom to characterize its behavior by many other quantities that can display a change more or less abrupt. By accepting that the word transition can be applied to these cases, it can encompass many processes where a particular quantity undergoes a change when varying a control parameter. The change can be abrupt and would then correspond to the usual idea of transition with the existence of a critical value for the control parameter. In some cases however, the system can interpolate continuously between two extremes and it is probably better to speak of a crossover (that could take place in the infinite size limit and does not describe a change when the size is increasing), and is described in general by a scaling function. In this review we will mostly speak about abrupt changes between different regimes but we will also mention some examples of this sort of crossover.

Understanding these transitions (and crossovers) will help us to identify the control parameters for these systems and eventually to improve the modelling of realworld spatial networks. This review is thus an attempt to bring together these different models under the unifying concept of transition which might help us to construct a consistent framework for spatial network modelling.

We will review some classes of models recently developped and by no means we intended to be exhaustive, but rather tried to focus on results that might trigger further studies, or provoke thoughts and modelling of real-world networks. Also, we will mostly focus here on transitions about the structure of graphs and not transitions for processes that take place on networks. We will start this review with the percolation type of transition. This phenomenon is by now well-known and we won't insist on this part as many books and reviews already exist (see for the example [START_REF] Grimmett | Percolation[END_REF] and for a more statistical physics oriented book see [START_REF] Stauffer | Introduction to percolation theory[END_REF]). We will basically discuss the random geometric graph for which many results exist [START_REF] Penrose | Random geometric graphs[END_REF] and which represent a good example of a simple and rich model of a spatial network.

We will then discuss 'topological transitions' in various models of graphs that are characterized by a change in the structure of the graph, as measured by a specific quantity such as the average shortest path that can display either a small-or large world behavior. We illustrate this effect on the Watts-Strogatz model and its ddimensional variant, and also on a spatial variant of the preferential attachment where sharp transitions were observed. We will also discuss this sort of transition for a class of greedy models based on a cost-benefit analysis and that represent a good candidate for modelling various real-world systems.

In the next part we will discuss some sort of 'localization' transition where modifications are seen in the spatial organization of shortest paths, in particular with the concentration of bottlenecks (i.e. nodes with a large centrality) in a small region of space. In particular, for a toy model consisting of a ring and branches we observe a transition for which the ring becomes central in the organization of shortest paths. We will also discuss a more general model which include randomness and that exhibits this localization type of transition when the density of links increases. Finally we will discuss transitions in optimal networks, a very important and well-developped topic. After a short discussion about transitions between classical optimal trees, we will discuss some new results about the effect of congestion on topological transitions in optimal trees. We will end this part with a discussion about the effect of noise and fluctuations in the formation of loops.

PERCOLATION-TYPE TRANSITION

For this type of transition, a giant cluster that spans the whole system appears suddenly when we increase the fraction of existing links. In the standard percolation problem on a lattice (see [START_REF] Stauffer | Introduction to percolation theory[END_REF]) the control parameter is the probability of presence of a link and there is a sharp threshold that depends on the underlying lattice. For graphs, the first instance of this type of transition was described in the celebrated paper by Erdos and Renyi [1]. In this class of random graph models, we typically have a set of N vertices and a probability p that any pair is connected. For this model the degree distribution is binomial

P (k) = N k p k (1 -p) N -k (1)
which in the case of large networks with k = N p = const. for N → ∞, converges to the Poisson distribution

P (k) = k k k! e -k ( 2
)
where k is the average degree of the graph. The now standard result obtained by Erdos and Renyi in their 1960 paper [1] is the evolution of this graph when p is varied. For large N the only parameter is the average degree k and they obtained a transition for k c = 1. More precisely, they could show that:

• For k < 1, clusters have a typical size of order O(log N ).

• For k = 1, there is a giant cluster of size scaling as N 2/3 .

• For k > 1, there is a giant component of extensive size (a fraction of N ). In addition, no other component is larger than O(log N ).

Other results about the connectivity of this graph can be obtained. For example, if p < log N/N , the graph will contain isolated vertices and above this sharp threshold the graph is almost surely connected. Many other results were subsequently obtained for this graph and we refer the interested reader to the book [START_REF] Bollobás | Random graphs[END_REF].

In the case of spatial networks, one of the first example that displays this type of percolation-type transition is the random geometric graph [4], (also called the unit disk graph) which became an important model with many applications. 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 when a proximity rule is used which states that nodes only within a certain distance are connected. There is an extensive mathematical litterature (see the book [START_REF] Penrose | Random geometric graphs[END_REF] and references therein) on these graphs and they were also studied by physicists in the context of continuum percolation (see for example [START_REF] Balberg | [END_REF]10]). This process extends usual percolation theory to continous space where shapes are randomly positioned and can overlap [11,[START_REF] Meester | Continuum percolation[END_REF].

Random geometric graphs are probably the simplest models of spatial networks and they can be used to model or understand many real-world situations. This is the case of wireless networks, smart-grids, disaster relief, etc. (see [START_REF] Dettmann | [END_REF] and references therein). In particular, in adhoc networks [14] where users communicate by means of short range radio devices that can communicate with each other if their distance is less than their transmission range. The set of connected devices can be used to propagate information over a longer distance by going from the source to the destination hoping through intermediate nodes. If there is a large density of nodes, alternate routes are even available which allows to split the information into separate flows. Usually, the users are mobile and the network evolves in time and it is important to understand the condition for the existence of a giant cluster. The percolation threshold and other quantities have then a direct interest in this type of applications.

This model was introduced by Gilbert [4] who assumes that N points are randomly located in the plane and have each a communication range R. This also could be seen as a system of disks (or spheres in dimension d) of radius r. Two nodes are connected by an edge if they are separated by a distance less than R (or 2r for the distance between the centers of the disks). We show an example of such a network in Fig. 1.

FIG. 1: Example of a 2d random geometric graph obtained with a density and radius such that the average degree is k ≈ 6. Note that this is an example of a non-planar spatial network.

If we denote by ρ = N/A the density of nodes in area A in the d = 2 case, the average degree is given by

k = ρπR 2 (3)
Similarly to the Erdos-Renyi random graph, there are different quantities that we can compute. In particular, there is a percolation transition for a critical density and another transition to full connectivity (ie. there are no isolated nodes).

Most studies are conducted in the limit N → ∞ which can be achieved in different ways. A first way is to consider a finite total area A, an increasing density ρ but a range R that decreases with N such that k is fixed. Another way -mostly considered by mathematicians (see for example [START_REF] Penrose | Random geometric graphs[END_REF]) is to study this limit by considering a fixed R and a fixed density but an area that varies as N/ρ.

It has been demonstrated (see the book [START_REF] Penrose | Random geometric graphs[END_REF] and references therein) that for large N there is a critical density (at fixed R and area given by N/ρ) below which we have small components of typical size O(1) and of largest size ∼ log N , and a giant cluster of size ∼ N . Gilbert [4] discussed already the probability to belong to an infinite cluster P ∞ and found a critical average degree

k c ≈ 4.7 (4)
and later the authors of [15] found k c ≈ 4.52 (for N ≈ 10 6 nodes). Using analytical techniques the authors of [16] could show that with 99.99% confidence

4.508 ≤ k c ≤ 4.515, (5)
which is consistent with the numerical bounds found in [10].

4.51218 ≤ k c ≤ 4.51228 (6)
We can note here that this value is much larger than its counterpart obtained for the ER graph. It seems here that spatial constraints impose a larger average degree in order to create a giant cluster.

TOPOLOGICAL TRANSITIONS

For spatial networks, a fundamental quantity is the distribution P ( 1 ) of the length 1 of links. When this distribution is peaked with a fast decaying tail, we can expect a lattice-like behavior for most measures on this network: the average shortest path will be 'large' (in general scaling as a power of the number N of nodes) and most quantities such as the clustering are much larger than their random counterparts (ie. computed for a graph without space such as the ER graph). If in contrast, the distribution P ( 1 ) is broad, we have a few long links that can be of the order the system size and the most relevant quantities will be affected: the average shortest path will be much smaller than the lattice-like case (typically varying as log N ). For some models, varying a parameter can have a dramatic effect on P ( 1 ) and we can then observe a transition between different classes of networks with different large-scale behavior. We will speak here of a 'topological transition' and we will present two examples of such models that are based on preferential attachment and on a cost-benefit analysis.

Watt-strogatz small-worlds

Already in 1977, spatial aspects of the small-world problem were considered by geographers in [17] but we had to wait until 1998 when Watts and Strogatz (WS) proposed a simple and powerful network model [18] which incorporates both a spatial component and long-range links. This model is obtained by starting from a d = 1 regular lattice and by rewiring links at random with a probability p (see Fig. 2). The degree distribution of this network has essentially the same features as the ER random graph, but the clustering coefficient and the average shortest path depend crucially on the amount of randomness p. The average clustering coefficient has been shown to behave as [19] C(p)

3 4 k -2 k -1 (1 -p) 3 (7)
The average shortest path has been shown to scale as [20,21]

∼ N * F N N * (8)
where the scaling function behaves as

F(x) ∼ x for x 1 ln x for x 1 (9)
We thus observe a crossover between different network phases when the number of nodes increases. This change from a large to a small-world is typically a crossover between two structures and strictly speaking in the large N limit we are always in the small-world regime. These results show that the WS network can be seen as clusters of typical size N * connected by shortcuts. The crossover size scales as N * ∼ 1/p [19][20][21] which basically means that the crossover from a large-world to a smallworld occurs for an average number of shortcuts of the order of one

N * p ∼ 1 ( 10
)
We note that historically, the interest of these networks is that they can simultaneously present some features typical of random graphs (with a small-world behavior ∼ log N ) and of clustered lattices with a large average clustering coefficient (while for the ER random graph we have C ∼ 1/N 1).

d-dimensional generalization

One of the first variants of the Watt-Strogatz model was proposed in [22][23][24] and was subsequently generalized to higher dimensions d [25]. In this variant (see Fig. 3), nodes are located on a regular lattice in d-dimensions (with periodic boundaries or not). For each node, we add a shortcut with probability p which implies that on average there will be pN additional shortcuts. We now define two differents models A and B according to the choice of the length distribution of shortcuts. For the model A, the length r of these links follows the distribution

q A (r) ∼ r -α (11)
where α is independent from the dimension d. The main idea for justifying this choice is that if shortcuts have to be physically realized there is a cost associated with their length and thefore a probability that decreases with the length. In this model A the effect of dimensionality is limited: we choose a link length distributed according to q A (r) and this is independent from the dimension d of the underlying lattice. In contrast, in model B (considered for example by Kleinberg [23]) we first choose a node x in the d-dimensional lattice and an endpoint y with probability proportional to |x -y| -α . The length distribution is then

q B (r) ∼ r -α r d-1 (12)
where the last term comes from the volume element r d-1 dr. The conceptual difference between models A and B is that in A we choose a distance and then a vector with this length. In the model B we are choosing directly a vector with a endpoint density q B . We will therefore discuss these models separately but if we substitute α → αd + 1 in model A we should recover the results of model B 1 . There is then a correspondance between the regimes in the two models and we give it in Table I. It is clear that if α is large enough, the shortcuts will be small and the behavior of the average shortest path will be 'spatial' with ∼ N 1/d . On the other hand, if α is small enough we can expect a small-world behavior characterized by ∼ log N . Various studies [22,25,26] discussed the existence of a threshold α c separating the two regimes, small-and large-world and we will also discuss this result in the next section about preferential attachment and space. Here, we will follow the discussion of [27,28] who studied carefully the behavior of the average shortest path. The probability that a shortcut is 'long' is given by

Model A Model B α < 1 α < d 1 < α < d + 1 d < α < 2d d + 1 < α 2d < α
P c (L) = L (1-c)L q A (r)dr L m q A (
r)dr [START_REF] Dettmann | [END_REF] where c is small but non-zero and where the lower cutoff m goes in general to zero with N (typically, m ∼ 1/ √ ρ → 0 where ρ is the density increasing with N ).

Performing these integrals we obtain

P c (L) = L 1-α -(1 -c) 1-α L 1-α L 1-α -1-α m ( 14
)
We denote by p * the critical fraction of shortcuts and according to the discussion above about the condition for having a small-world (Eq. ( 10)), the fraction of 'long' shortcuts needs to be large enough and this reads here (with N ∼ L d )

P c (L)p * L d ∼ 1 ( 15
)
1 I thank P. Grassberger for discussions on this point

This condition means that if we have a fraction p > p * of long shortcuts, the system will behave as a small-world. If α < 1, the fraction P c (L) → 1 -(1c) 1-α when m → 0, and in this case, spatial fluctuations do not play a role and p * ∼ 1/L d . In contrast, if α > 1, the fraction P c (L) depends on density fluctuations via m and we have p * ∼ 1/L d-α+1 . To recap, we thus have the following behavior

p * (L) ∼ L -d if α < 1 L α-d-1 if α > 1 (16)
(and a logarithmic behavior of the form log L/L d for α = 1). For a given value of p we thus have a length scale

L * (p) ∼ p -1/d if α < 1 p 1/(α-d-1) if α > 1 (17)
a result obtained in [29] for the special case α = 0. We can then write the following scaling form for the average shortest path

= L * F α L L * (18)
where the scaling function varies as

F α (x) ∼ x if x 1 ln x if x 1 (19)
(it could be a function of the form (ln x) σ(α) with σ(α) > 0 for x 1). For α < 1, the characteristic length L * ∼ p -1/d (which is the result for α = 0) and implies that there are two regimes (small and large-world). For α > 1, the characteristic length behaves as

L * (p) ∼ p 1/(α-d-1) (20)
which displays a threshold value α c = d + 1, a value already obtained in [25]. In the case α < α c , the length L * (p) is finite and there are two regimes depending on the size Lversus L * . In contrast when α → α - c this length diverges and we always have L L * implying the network is in the large world regime. In other words, the links in this case are not long enough and the graph looks like a lattice at a coarse-grained scale.

Model B

A numerical study of this model was proposed in [30] and numerics for the related model of SIR with long range infection can be found in [31,32]. We have different regimes for this model. First, for α < d, the graph is in the small-world regime with ∼ log N . In the case α > d there are two regimes. First, for d < α < 2d we have a regime of the form

∼ (log N ) σ(α) (21)
where the exponent has been computed exactly [33]

σ = log 2 log 2d α , (22)
a result which has been confirmed numerically for d = 2 in [32] (and for d = 1 in [31]). The second regime is obtained for α > 2d where the 'spatial' behavior ∼ N 1/d is recovered.

A simple scaling argument was proposed in [30] in order to understand these results and we reproduce it here. It is based on the average shortcut size given by r = L m rq B (r)dr (23) and the largest link size r max defined by the relation

L rmax q B (r)dr ∼ 1 N (24)
with q B ( ) given by Eq. ( 12). After a simple calculation one obtains

r ∼      L α < d L d+1-α d < α < d + 1 const. d + 1 < α (25)
and

r max ∼ L 0 < α < 2d L d α-d α > 2d (26)
The picture that emerges from these results is then the following one. For α < d, both the average and the maximum link length is of order r ∼ r max ∼ L, and the network is a small-world characterized by ∼ log N . In the second regime d < α < 2d, the average shortcut length is small ( r L) but we still have a few very long shortcuts (r max ∼ L). If we want to connect a pair of points we will have to do more steps but eventually we will reach a long shortcut that allows to connect very quickly at destination. The network is therefore still in a small-world phase with a behavior of the form (log N ) σ . Finally, the third regime (α > 2d) is characterized by r , r max L and the network is lattice-like with a large-world behavior ∼ N 1/d . In addition, it was numerically shown [30] that the clustering coefficient is very small (of order 1/N ) for α < d and of order unity for α > d. The final picture for this model B is then the following one:

• For α < d the network is a random graph: the clustering coefficient is of order C ∼ 1/N and the average shortest path ∼ log N .

• For d < α < 2d, the average shortest path is still small ( ∼ (log N ) σ with σ = 1/ log 2 (2d/α) [32,33]), and the average clustering coefficient C is large which is a typical feature of small-world networks [18].

• For α > 2d, the average shortest path is of order the size of the system ∼ L ∼ N 1/d , a behavior typical of a lattice-like network (and C ∼ O(1)).

We recap all these different results in the table II.

α < d d < α < d + 1 d + 1 < α < 2d 2d < α r L L d+1-α const. const. rmax L L L L d/(α-d) log N (log N ) σ (log N ) σ N 1/d C 1/N ∼ O(1) ∼ O(1) ∼ O(1)
TABLE II: Behavior of various quantities versus α for the model B defined by the distribution Eq. ( 12): the average shortcut length r , the average maximum shortcut length rmax, the average shortest path , and the average clustering coefficient C .

Finally, we note that model B was also used in [23,34] where the goal was to reach a given target as fast as possible and using local information only (i.e. such as the distance to the target for the neighbors). The average number of hops T for reaching a target is then different from the average shortest path where the whole network is known. This quantity reaches its minimum for α = d where the diversity of links is the largest: long links are needed for going quickly to the neighborhood of the target, and short links are necessary for reaching the target in the final steps. In general, we have a scaling of the form T ∼ N s where the exponent depends on both the embedding dimension and α [23]:

s(α) =      d-α d+1 for α < d 0 for α = d α-d α-d+1 for α > d (27)
The exponent σ = 0 corresponds here to a logarithmic behavior of the form T ∼ (log N ) 2 [23].

Preferential attachment and space

Many networks, including spatial graphs, evolve and grow in time and understanding the main processes governing this growth and the resulting structure is crucial in many disciplines ranging from urban planning to the study of neural networks. There are essentially three ingredients for growing a network:

• At each time step, one node (or more) is added to the network

• New nodes are located according to a distribution that depends in general on the structure of the existing network.

• Once located in space, the new nodes are attached to the existing network according to a certain connection rule.

We will mostly consider here the case where nodes are uniformly located, and where the connection rule is governed by a 'spatial' variant of the preferential attachment [35,36] of the form

Π n→i ∝ k i F [d(n, i)] ( 28
)
where n is the new node and i a node that belongs to the existing network. The function F describes the effect of the euclidean distance d(n, i) between nodes n and i. This is a natural and simple model for spatial networks as it assumes that when long-range links exist, they usually connect to hubs -the well-connected nodes, unless the hub is too far. In order to have long links, the target node must have a large degree in order to compensate for a small F (d) such that kF (d) ∼ 1. This is for instance the case for airlines: Short connections go to small airports while long connections point preferably to big airports, ie. well-connected nodes. We note that when F = const. we recover the usual preferential attachment where space is absent [36] and produces a broad distribution of degree with exponent γ = 3.

A first simple case is to consider an exponential function

F (d) = e -d/d0 (29)
where d 0 sets the typical scale for links. There is therefore one parameter η = d 0 /L which governs the behavior of this model. The degree distribution is of the form [37]

P (k) ∼ k -γ f k k c (30)
where γ = 3 (the value for the 'pure' preferential attachment model). The cut-off is scaling in dimension d as k c ∼ (η d ) ν where the numerical analysis gives ν = 0.13 [37]. The scaling for the average shortest path is

= (N * ) ν g N N * (31)
where ν ≈ 0.3 and where the scaling function behaves similarly to the Watts-Strogatz case

g(x) ∼ x ν for x 1 log x for x 1 ( 32
)
The crossover size N * depends on the parameter η and its behavior in two extreme cases can be found by the following argument: for η 1 space is irrelevant and N * ∼ const., we are always in the small-world regime. In contrast, when η 1, space is relevant and we expect to have a crossover from a large to small-world regime.

We denote by a ∼ 1/N 1/d the typical internode distance and the transition will take place when

d 0 ∼ a(N * ) ⇒ N * (η 1) ∼ 1 η d (33)
For N > N * the network is in the small-world regime and its diameter is growing as ∼ log N . In the opposite case, the range d 0 is small and the network is much larger: to connect a typical pair of nodes we need to pass through ∼ N ν points which is found to be smaller than the lattice-like behavior N 1/2 for (d = 2), probably due to the existence of a few rare long links.

Another simple case was considered where

F (d) = d -α (34)
and which was studied in [38][39][START_REF] Yook | Proc. Natl. Acad. Sci[END_REF] and recently rediscussed in [START_REF] Balister | [END_REF]. The numerical study presented in [39] shows that in the one-dimensional case, for all values of α the average shortest path behaves as log N . The degree distribution is however different for α < 1 where it is a power law, while for α > 1, it is decreasing much faster and the numerical results in [39] suggest a stretched exponential behavior.

In [38], Manna and Sen study the same model but for various dimensions d and for values of α going from -∞ to +∞ where the node connects to the farthest and the closest node, respectively (Fig. 4). Note that in this study [38] the convention on α is different as they chose F (d) = d +α but here and in the following we stick to the definition Eq. (34). These authors found a transition for α = α c and degree distributions in agreement with the results of [39]. They also studied the behavior of the link length distribution P ( 1 ) and found a power law of the form

P ( 1 ) ∼ -δ 1 (35)
where δ = αd + 1 (which simply results from dimensional counting). From this result they define a critical value α * = d -1. Numerically, δ indeed behaves linearly up to α * and then saturates to the value δ m = d + 1 for α > α * . The following argument can be given for this value δ m in the limit α → ∞. In this case, a new node always connects to its nearest neighbor and the probability that the link length t+1 of the t + 1 th node is larger than 1 is given by

P ( t+1 > 1 ) = (1 -b d 1 ) t ( 36
)
where b d 1 is the probability to fall in the hypersphere of radius 1 and centered around the new node at time t+1. This implies that the probability to have a link of length [ 1 , 1 + d 1 ] at time t + 1 is given by and for all times up to t = T we obtain

P ( 1 ; t)d 1 = bdt d-1 1 (1 -b d 1 ) t-1 (37) α = + 8 α = - 8 α = +5 α 0 = α = -1 α = -2
P ( 1 ) = bd d-1 1 T t=1 t(1 -b d 1 ) t-1 ∼ 1 d+1 1 (38)
leading to δ m = d + 1. This study was complemented by another one by the same authors [START_REF] Sen | [END_REF] in the d = 1 case and where the probability to connect to a node i is given by

Π n→i ∼ k β i d(n, i, ) α (39)
They studied the phase diagram in the plane (α, β) and found transitions for the degree distribution as above, and also a change of behavior for the degree-dependent clustering coefficient C(k). They found numerically that it behaves as

C(k) ∼ k -ξ (40)
where ξ varies from 0 to 1 when α varies from +∞ to ∞.

We note here that this model was also studied numerically in [START_REF] Yook | Proc. Natl. Acad. Sci[END_REF] where a phase diagram in the space (d, β, α) is proposed.

The preferential attachment model with space was recently reconsidered in [START_REF] Balister | [END_REF] and the existence of the numerically observed transition was mathematically proven. In this work, the probability to connect to a node i is given by

Π n→i = k i d(i, n) -α Z n (41)
where the normalization constant Z n is

Z n = i <n k i d(i , n) -α (42)
and we refer the interested reader to the paper [START_REF] Balister | [END_REF] for more details. We reproduce here their heuristic argument which is in fact in the spirit of the one given above [28].

It is interesting to note that all these heuristic arguments are based on a discussion on the behavior of the normalization Z n , which is also the case for the demonstration of Kleinberg about navigability in small-worlds with distributed link lengths [23]. In the continuous limit the normalization constant reads

Z n ≈ L n r -α r d-1 dr (43) ≈ L d-α -d-α n d -α (44)
where n is the lower cut-off for node n and goes to zero with increasing density. If d > α the integral is convergent and we obtain Z n ∼ L d-α for n → 0. Spatial fluctuations are therefore irrelevant in this regime.

From the expression for Π n→i (Eq. ( 41)), the evolution of the degree distribution is then described by the following equation

dk i dt = m 1 t t n=1 k i d(n, i) -α Z n (45) ≈ σ(r i ) k i t (46)
where

σ(r i ) = m |r -r i | -α j k j |r -r j | -α ρ(r)dr (47)
This result allowed the authors of [START_REF] Balister | [END_REF] to show that the degree distribution is a power law P (k) ∼ k -γ where γ = 1 + 1/ sup r σ(r). In the case where ρ(r) = const., σ(r i ) = 1/2 and we recover the usual value γ = 3 for the preferential attachment. It is interesting to note that space heterogeneities with a non-uniform density ρ(r) will in general increase σ(r i ) and therefore lower the value of γ and favor the degree inhomogeneity.

In the opposite case d < α, the node (denoted by t) that arrives at time t will typically connect to a node i at a distance of order d(t, i) ∼ t -1/d (where t is then the current number of nodes in the network). The typical order of magnitude of Z t will then be Z t ∼ t α/d . If the node i has a (large) degree k i , the sum Z t will be dominated by the ti term and we will have

Z t ≈ k i d(t, i) -α which implies d(t, i) ∼ k 1/α i t -1/d
. Since nodes are located at random, the probability to connect to i is then of order

d(t, i) d : Π t→i ∼ d(t, i) d ∼ k d/α i /t.
The degree evolution equation is then of the form [START_REF] Balister | [END_REF]

dk i dt = C k d/α i t ( 48
)
which leads for the degree distribution to a stretched exponential of the form P (k) ∼ exp-k 1-d/α . Exact results [START_REF] Balister | [END_REF] confirm this heuristic argument and the existence of a sharp transition for α c = d. This transition can be seen in various quantities such as the degree distribution that goes from apower law to a stretched exponential when α crosses d. In other words, for α > d spatial constraints are important while for α < d the growth is mostly governed by the preferential attachment. We note here that the average path length does not display here the same behavior as models A and B above that undergoes a transition from a small-world to a large world regime characterized by N 1/d . Indeed in both phases here, the average shortest path is 'small': it varies as log N for α > d and as log N/ log log N for α < d [START_REF] Balister | [END_REF].

Greedy models: cost-benefit analysis

We will discuss in the next section 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. In general, if we denote by i the new node, it will connect to the node j (that belongs to the existing network) such that the quantity

Z(i, j) = Benefit(i, j) -Cost(i, j) (49)
is maximum. This quantity represents the balance between the cost of constructing the link ij and the benefit that it will create. The optimization is therefore not global -the resulting network does not necessarily optimize some quantity -but is local. In this respect these models can be qualified as 'greedy' as they rely on a local optimal choice, but with no guarantee that the system as a whole will reach a global optimum. This type of models was proposed by transportation scientists [43] and more recently by computer scientists [START_REF] Fabrikant | Papadimitriou[END_REF] for describing the Internet growth and which predicts correctly a scale-free degree distribution as observed empirically (see for example [START_REF] Pastor-Satorras | Evolution and structure of the Internet: A statistical physics approach[END_REF] and references therein). In this model, the functional maximized at each node addi-tion reads

Z(i, j) = -g(j) -λC(i, j) (50)
and if we allow only one link per new node the resulting network is a tree (if the initial conditions are tree-like). The quantity g(j) is in general a measure of the 'centrality' of the node j such as the average number of hops to other nodes, or to a given central node, etc. and that we wish to be small (and the benefit -g large). The quantity C(i, j) is a cost function, in general proportional to the euclidean distance d(i, j). The quantity λ controls the relative importance of centrality versus distance [START_REF] Fabrikant | Papadimitriou[END_REF]:

• For λ 1, only the cost (distance) is minimized and each new node will connect to the nearest node in the growing cluster; the resulting network will be akin to a dynamical version of the minimum spanning tree (MST).

• For λ 0, cost has no importance and the new node will connect to the most central node, producing in general some sort of star graph (i.e. the complete bipartite graph K N -1,1 ).

Since the euclidean distance between nodes is typically of order 1/ √ N the value that distinguishes large from small values of λ is O( √ N ). Fabrikant et al. [START_REF] Fabrikant | Papadimitriou[END_REF] also showed that if λ has some intermediate values, we obtain various networks, for example [START_REF] Fabrikant | Papadimitriou[END_REF]:

• if 1 λ √ N
, we obtain a graph with a degree distribution of the form P (k) ∼ k -γ where γ depends on λ.

• if λ ∼ N 1/3 there is an exact bound γ ≥ 1/6 and numerical results seem to indicate that 0.6 ≤ γ ≤ 0.9

More generally, we will observe a large variety of networks according to the choice of the functions g(j) and C(i, j) and we will consider here essentially an example of cost-benefit models [43,[START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF] which depends on a single scale and produces a family of networks which range from the star-graph to the minimum spanning tree and which are characterised by a continuously varying exponent [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]. More precisely, we assume that all nodes are distributed uniformly in the plane and are labelled by a quantity P i . For a rail network, each node corresponds to a city and has a population P i which is assumed to be distributed according to a power-law with exponent 1+µ with µ ≈ 1.0 (see [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF] for further details and discussions). The edges are added sequentially to the graph -as a result of a cost-benefit analysis -until all the nodes are connected. For the sake of simplicity, we describe here the growth of trees which allows to focus on the emergence of large-scale structures due to the cost-benefit ingredient alone. Motivated by transportation networks, the cost is chosen to be proportional to the euclidean distance d(i, j) between i and j C(i, j) = κd(i, j)

where κ represents the cost of a link per unit length. Benefits are more difficult to assess, and here also motivated by transportation networks, we assume that the benefit is proportional to the expected traffic between nodes. We then use the common and simple assumption of the so-called gravity law (see [START_REF] Erlander | The gravity model in transportation analysis[END_REF] and references therein) to estimate the traffic and we end up with the following expression for the cost-benefit budget (up to irrelevant factors) [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]

Z ij = K P i P j d(i, j) a-1 -βd(i, j) (52)
where β represents the relative importance of the cost with regards to the benefits and which is the main control parameter here (the constants are here a > 1, K > 0). If we denote by P the average population and we note that the typical inter-city distance is of order 1/ √ ρ (ρ = N/L 2 denotes the city density, and L is the typical linear size of the whole system), it is easy to see that the two terms of Eq. ( 52) are of the same order for β = β * defined as

β * ∝ P 2 ρ a/2 (53)
From Eq. ( 53) we can guess the existence of two different regimes depending on the value of β:

• β β * the cost term is negligible compared to the benefits term. Each connected city has its own influence zone depending on its population and the new cities will tend to connect to the most influent city. In the case where a ≈ 1, every city connects to the most populated cities and we obtain a star graph constituted of one single hub connected to all other cities.

• β β * the benefits term is negligible compared to the cost term. All new cities will connect sequentially to their nearest neighbour. If we select the node i such that the length of the link ij is the smallest, the algorithm is then equivalent to Prim's algorithm [START_REF] Prim | [END_REF], and the resulting graph is a minimum spanning tree (MST). Fig. 5 shows three graphs obtained for the same set of cities for three different values of β/β * (a = 1.1, µ = 1.1) confirming the discussion above about the two extreme regimes.

For β ∼ β * we observe a different type of graph, which suggests the existence of a crossover between the stargraph and the MST. This graph is reminiscent of the hub-and-spoke structure that has been used to describe

β/β * =0.0 β/β * =1.0 β/β * =1000.0
FIG. 5: Graphs obtained with the cost-benefit algorithm for the same set of cities (nodes) for three different values of β * (a = 1.1, µ = 1.1, 400 cities). On the left panel, we have a star graph where the most populated node is the hub and on the right panel, we recover the minimum spanning tree. Figure taken from [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF].

the interactions between city pairs [49,50], but it is important to note that this structure emerges naturally in the system and does not result from a global optimization. Also, we note that the graph corresponding to the intermediate regime β ≈ β * (see Fig. 5) exhibits a particular structure corresponding to a hierarchical organization observed in many complex networks [START_REF] Sales-Pardo | Proceedings of the National Academy of Sciences[END_REF] and which can be characterized quantitatively. In particular, the average euclidean distance d between the different hierarchical levels decreases with the level rank (for details, see [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]). An important difference between the star-graph and the MST lies in the scaling of the total length of the graph with its number of nodes. Indeed, in the case of the star-graph, all the nodes are connected to the same node and the typical edge length is L, the typical size of the system the nodes are enclosed in. We thus obtain

L tot ∼ L N (54)
On the other hand, for the MST each node is connected roughly to its nearest neighbour at a distance typically given by 1 ∼ L/ √ N , leading to

L tot ∼ L √ N (55)
More generally, we expect a scaling of the form

L tot ∼ N τ (56)
and on Fig. 6 we show the variation of this exponent τ versus β. For β = 0 we have τ = 1.0 and we recover the behavior L tot ∝ N typical of a star graph. In the limit β β * we also recover the scaling L tot ∝ √ N , typical of a MST. For intermediate values, we observe an exponent which varies continuously in the range [0.5, 1.0].

We can understand this crossover behavior as a consequence of the hierarchical structure of these graphs with a simple toy model [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]. More precisely, we consider the fractal tree depicted on Fig. 7 constructed recursively as a tree of connectivity z (in this figure only 3 levels are shown). For this model, the distance between the levels n and n+1 is given by n = 0 b n where b ∈ [0, 1] is the scaling factor. This scaling factor would then correspond to the average distance between successive hierarchical level d and thus decreases with the depth in the hierarchy. For a regular tree, each node at the level n is connected to z nodes at the level n + 1 which implies that N n = z n where z > 0 is an integer. A simple calculation shows that in the limit z g 1, the total length of the graph with g levels scales as

L tot ∼ N ln(b) ln(z) +1 (57)
where ln(b) ln(z) + 1 ≤ 1 because b ≤ 1 and z > 1. This simple model thus provides a simple mechanism where the exponent for L tot varies continuously and depends on the scaling factor b. The parameter z can be easily determined from the average degree of the network, and the parameter b can be related to our model by measuring the decrease of the mean distance d between different levels of the hierarchy [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]. This toy model thus provides a simplified picture of the graphs in the intermediate regime β β * and exhibits their key features in this regime: the hub structure reminiscent of the star graph and nodes connected to each hub forming geographically distinct regions and organized in a hierarchical fashion.

Finally, it is interesting to note that empirical networks seem to be in the range β ∼ β * suggesting that spatial hierarchy and other features not discussed here (see [START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF]) are relevant for real-world networks. It seems plausible that the general cost-benefit framework could be applied to the modelling of systems besides transportation networks: it captures the fundamental features of spatial network while being versatile enough to model the growth of a great diversity of systems shaped in part by spatial constraints. From this point of view, it would therefore be very interesting to understand the effect of other benefit functions and the conditions for observing crossovers and transitions.

LOCALIZATION TRANSITION

In general, the structure of a graph has naturally an effect on the pattern of shortest paths on it and we will illustrate this phenomenon on simple examples. We will first discuss a simple structure formed by a ring and radial spokes present with a probability p and we will compute the average shortest path. Beyond the average shortest path we will also characterize the effect of structural changes with the help of the betweenness centrality (BC), a simple proxy for traffic. In particular, we will discuss two examples where a variation in the structure induces dramatic changes in the pattern of congested nodes or 'bottlenecks' characterized by a large BC value.

Hub-and-spokes structure

In many real-world cases the 'pure' hub-and-spoke structure is not present and we observe in general a ring structure around a complicated core or an effective hub (see some examples in Fig. 8). We will however use this coarse-grained structure and present an interesting discussion proposed in [START_REF] Ashton | [END_REF]53] about centralization versus decentralization from the perspective of the average shortest path.

The main ingredient in these models is the competition between the centralized organization with shortest paths going through a single central hub and decentralized paths going along a ring and avoiding the central hub (in particular in presence of congestion). A simple model of hub-and-spoke structure together with a ring was proposed in [54] where N nodes are on a circle and a hub is located at the center of the circle (see Fig. 9). Each radial link -a spoke -is present with probability p.

FIG. 9: Models proposed and discussed in [54] and studied with congestion in [START_REF] Ashton | [END_REF]53]. A central site is connected to a site on a ring with probability p. In (a) all the links on the ring are directed and in (b) these links are not directed. Figure taken from [54].

We first consider this model and reproduce the results obtained in [54] for the average shortest path (p) and its distribution P ( ). We discuss the simpler case where the loop is oriented as shown in Fig. 9(a) (for undirected links calculations are more involved but results are similar). The central point is connected with undirected links of weight 1/2 added with probability p. This amounts to connect random pairs of nodes by undirected links of length 1. Obviously (p = 0) ∼ N while (p = 1) = 1 showing that we have for this simple model a crossover between a large and a small-world behavior when p is varied. In the case of directed links, the result for the shortest path distribution is [54]

P ( ) = 1 N -1 1 + ( -1)p + (N -1 -)p 2 (1 -p) -1 (58)
and the expression for the average shortest path =

N =1 P ( ) is = 1 N -1 2 -p p N - 3 p 2 + 2 p + (1 -p) N p (N -2 + 3 p ) ( 59
)
We can easily check that this expression is consistent with the two limiting cases For p → 0 :

P ( ) → 1/(N -1) ⇒ = N/2 (60)
For p → 1 :

P ( ) → δ ,1 ⇒ = 1 ( 61
)
As expected this simple model thus displays a crossover from a large to small-world when p increases. At small p most shortest paths go along the ring, while for p close to 1, most shortest paths go through the central hub.

An interesting observation made in [START_REF] Ashton | [END_REF] is that if we add a cost c each time a path goes through the central hub, we could expect some sort of transition between a decentralized regime where it is less costly to stay on the peripheral ring to a centralized regime where the cost is not enough to divert paths from the central hub. The cost could in general depend on how busy the center is and could therefore grow with the number of connections to the hub. In the case of a constant cost c (and in the directed case), we can estimate the shortest path distribution (N is here the number of nodes on the ring) and the result is [START_REF] Ashton | [END_REF]

P ( ) = 1 N -1 for ≤ c 1 N -1 [1 + b 1 p + b 2 p 2 ](1 -p) -c-1 for > c ( 62
)
where b 1 =c -1 and b 2 = (N -1 -)(c). For paths of length ≤ c, there is no point to go through the central hub. In the opposite case, when > c, we recover a distribution similar to the c = 0 case of [54].

The average shortest path is now

= (1 -p) N -c [3 + (N -2 -c)p] p 2 (N -1) + p[2 -2c + 2N -(c -1)(c -N )p] -3 p 2 (N -1) + c(c -1) 2(N -1) (63)
We can consider the continuous limit (p → 0, N → ∞, and z ≡ /N and ρ = pN fixed), the average shortest path is then a function of these parameters (ρ, c, N ). This analysis allows to show that there is an optimal number of connections to the central hub in order to minimize the average shortest path. For example for a cost increasing linearly as c = kρ the optimal value is ρ * ∼ N/k which corresponds to the simple condition pc(ρ) ∼ 1 (for more details see [START_REF] Ashton | [END_REF]55]). This study [START_REF] Ashton | [END_REF] was generalized in [53] to the case of a more complicated cost function such as c(ρ) = Cρ + Bρ 2 + Aρ 3 where the authors observe different behaviors and a phase transition according to the values of the coefficients A, B, and C. These studies on a simple toy model show how congestion could have an important impact on the a priori optimal hub-and-spoke structure and favorizes the transport along a ring. From a more general perspective it would indeed be interesting to observe the emergence of rings -as observed in real-world examples -without imposing it a priori.

A loop and branches toy model

We saw in the previous section how the density of spokes can influence the pattern of shortest paths. In order to go beyond the average shortest path, we will measure the variations of the shortest path pattern with the help of the betweenness centrality (BC). The BC is a measure of the importance of a node (or an edge) and is a very simple proxy for traffic on the network. More precisely, the betweenness centrality g(i) of node i is defined as [56][57][58][59][60].

g(i) = 1 N s =t σ st (i) σ st ( 64
)
where σ 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 (the normalization N is usually chosen as N = (N -1)(N -2) which counts the number of pairs and ensures that g(i) ∈ [0, 1]). This quantity g(i) thus characterizes the importance of the node i in the organization of flows in the network (note that with this definition, the betweenness centrality of terminal nodes is zero, and that a similar definition can be given for the BC of edges). The bottlenecks in the graph are therefore the nodes with a large BC. These nodes are critical The number of branches is here N b = 5, the number of nodes on each branch is n = 11 and the loop is located at a distance = 6 from the center 0. The node C is at the intersection of a branch and the loop and T is the terminal node of a branch. Figure taken from [61].

for shortest paths and their study allows us to highlight important structural changes.

We expect in general that the pattern of shortest paths on a network will be strongly affected by the link properties: if the links are weighted by the time needed to cross them, the quickest path will result from an interplay of the topology and the weight structure. In order to understand if we can observe transitions in the pattern of quickest paths on a network and motivated by the crossover described in the previous section, we will consider a simple model that incorporates (i) a center, (ii) radial links and (iii) a loop. Such a simple toy model was considered in [61] where the network is constructed on a star network composed of N b branches, each branch being composed of n nodes. We then add a loop at a distance from the center (see Fig. 10 for a sketch of this graph). We also consider the general case where links are weighted and have a weight equal to one for radial links, and a weight w for links on the loop (between two consecutive branches) -we can then recover the purely topological case by taking w = 1. The quantity w can be seen as the time spent on the segment and the weighted shortest path is then the quickest path. We compute the BC using weighted shortest paths (the 'quickest' paths) and this generalization allows us to discuss the impact of different velocities on a street network.

Within this simple toy model, we will discuss under which conditions the loop is more central than the 'origin' at the center. As above, the structure of the network is fixed and we focus on transitions in the spatial pattern of shortest paths when the weight w is modified. Intuitively, for very large w, it is always less costly to avoid the loop, while for w → 0, the loop is very advantageous. The two main quantities of interest are therefore the centrality at the center denoted by g 0 ( , n, w) and the centrality at the intersection C of the branch and the loop, denoted by g C ( , n, w). The interest of this toy model lies in the fact that we can estimate analytically these quantities and we will give here the main results and refer to [61] for more details. We want to understand here if the origin has always a larger BC than the loop, or if for some values of the parameters, this order can be inverted. We will then compute the difference δg = g 0g C and study under which condition it can be negative. We plot this quantity versus for different values of w and we observe the result shown in Fig. 11 This result shows For values less than a threshold (wc ≈ 4 here) there is a minimum that is negative. Figure from [61] that for w sufficiently small, δg can be negative. This demonstrates the existence of a threshold value w c such that at w = w c the minimum is min δg = 0. For w < w c , the minimum of δg is negative and we can define an optimal value opt which corresponds to this smallest value of δg. The quantity opt thus gives the position of loop that maximizes the difference between the BC of the loop and the center.

In [61], all the derivations for the quantities w c and opt can be found, and we restrict ourselves here to handwaving arguments. In order to determine opt , we note that when is small, most paths connecting nodes from different branches will go through 0 and we expect δg > 0. When is increasing more paths will go through the loop and will increase the value of g C . However, when is too large, paths connecting the (large) fraction of nodes located on the lower branches will go through 0 again.

In order to get a sufficient condition on opt , we consider the path between the node C on the branch '1' and the corresponding node C on the furthest branch (N b -1)/2 (for N b odd). The optimal value for opt is then such that the cost of the path from C to C through 0 which is given by 2 is equal to the cost on the loop equal to w(N b -1)/2. This leads to the result

opt ≈ w(N b -1) 4 ( 65
)
(which is the exact result). The threshold quantity w c is obtained by imposing that the minimum of δg( = opt ) is equal to zero, but we can understand the scaling for w c with the simple following argument. Indeed, a necessary condition on w is that opt must be less than n which leads to the condition

w < w c ∼ 4 n N b (66)
(the scaling n/N b is exact but the prefactor's value seems to be closer to 2/3 [61]).

If we come back to the 'topological' case where all weights are equal to 1, these results on this simple toy model show that the loop can be more central than the origin if w c > 1 which implies that n N b . It thus suggests that the number and the spatial extension of radial branches are crucial ingredients that control the existence of central loops. If the extension n of the network is large compared to the number of radial branches, w c can be larger than one w c > 1 and central loops can be observed for w = 1. In ordered systems -such as lattices -the effective number of branches is too large leading to a very small w c and therefore prohibits the appearance of central loops in the 'topological case (w = 1). In realworld planar graphs where randomness is present, the absence of some links can lead to a small number of 'effective radial branches which in the framework of the toy model implies a large value of w c and therefore a large probability to observe central loops.

Tuning the edge density

We considered previously a simple toy model and we now discuss a more general one where randomness is present. In particular, we want to understand the BC distribution P (g) and the spatial pattern of bottlenecks -the high BC nodes -when the density (of nodes or links) increases. For spatial networks that are trees the BC is very large and belongs in the range [N, N 2 ]: for terminal nodes and their neighbors, we have a g ∼ N behavior while for central nodes we expect the scaling g ∼ N 2 . In general networks are not trees and contain loops, and their presence creates alternate paths producing a wealth of nodes with a low BC. We thus expect the emergence of a low BC regime with increasingly sharp cut-offs with increasing density.

In order to discuss and confirm this idea, we discuss the simple model of planar graph proposed in [62]. We distribute uniformly N nodes in the 2d plane and generate the Delaunay triangulation on this set. We then remove at random links so that the edge density defined by

ρ e = E E DT , (67)
reaches a desired value. In this expression, we normalize the number of edges E by its value E DT for the Delaunay triangulation. For a maximally planar graph (i.e. one in which no more edges can be added without violating the planarity constraint), we have E DT ≈ 3N , which implies that the density captures a quantity proportional to the average degree. The density ρ e thus varies from ≈ 1/3 for the MST to 1 for the DT [63], and allows us to monitor changes in these graphs.

We show results obtained with this simple model (and for comparison, we also show the results for the minimum spanning tree) in Fig. 12. On the left panels, we show the BC distribution and on the right panels the corresponding network with the nodes having the largest BC (90 th percentile). As expected, the BC distribution for the MST (Fig. 12A) is peaked at N and is bounded by N 2 /2 (which corresponds here to the interval [10 4 , 10 8 ]). In this interval, the BC distribution follows a form close to a calculation on a Cayley tree (see [62] for more details). For increasing density ρ e , we have loops in the graph which induces the bimodal shape of the BC distribution (Fig. 12B-D). The low BC in the range [1, N 2 ] results from these loops that allow to bypass some of the high BC nodes. For larger values of ρ e the distribution gets progressively more homogeneous while keeping the peak around N even as we approach the limiting case of the DT (Fig. 12D).

These simulations also reveals an interesting spatial behavior. Nodes with a large BC are highlighted in the right-hand panels of Fig. 12 and display a change in their spatial pattern with increasing ρ e . In the MST case, the high BC nodes span the whole network, and for increasing density, we observe a localization trend where the high BC nodes cluster together around the barycenter. This suggests some sort of topological transition (or crossover) towards a spatial regime characterized by a clustering of the BC around the barycenter and which corresponds roughly to the regular lattice case where the BC is a smoothly decreasing function with the distance to the barycenter. We can quantify more precisely this transition by measuring various indicators (see [62]), and we will here discuss the clustering of BC nodes above the θ th percentile. We compute their spread around their center of mass normalized by the average distance of nodes to the center of mass where the average position is x cm = N θ i=1 x i , and where N θ is the number of high betweenness nodes at percentile θ (the quantities {x i } specify the coordinates of nodes). The clustering index (Eq. ( 68)) thus quantifies the extent of clustering of the high BC nodes relative to the rest of the nodes in the network, with increased clustering resulting in low values of C θ . In Fig. 13 we plot the average quantity C θ for various values of θ (90, 95, and 97) versus ρ e and we observe a clear decrease with the density ( . . . indicates averaging over realizations). Indeed the decrease is approximately by a factor of two from the MST to the DT, confirming the spatial clustering of the nodes to be a robust effect. We note here that in order to confirm if this is a transition or a crossover, a further analysis of finite size effect is needed. All the metrics point to the fact that the spatial location of a node has little relevance to its BC in a sparse network, whereas it assumes increasing importance for denser networks. This is confirmed by plotting the rescaled average BC of nodes as a function of the distance r from the barycenter (see [62]): for low values of ρ e there appears no distance dependence of the nodes, whereas for ρ e > 0.4, a clear r dependence emerges with the curves converging to the form seen for dense random geometric graphs as calculated in [START_REF] Giles | Communications (ICC), 2015 IEEE International Conference on[END_REF]. Interestingly emough, real-world cases are considered in [62] (street network of 97 world cities, and the evolution of central Paris), and are shown to display a behavior that is well described by this simple model (we refer the interested reader to the paper [62] for more details and discussion about real-world cases). This simple model seems thus able to describe the 'localization' transition of bottlenecks with increasing densities (Fig. 12), and can be thought of as a proxy for the evolution of a urban road network as it experiences refinements in infrastructure with increased connectivity.

C θ = N N θ N θ i=1 |x i -x cm | N i=1 |x i -x cm | (68)

OPTIMAL NETWORKS

An important class of networks are obtained by optimizing a functional of a graph. A simple and well-known example is the minimum spanning tree (MST) that minimizes the total length of a tree connecting together a given set of points. Even if most existing spatial networks in the real-world seem not to result from a global optimization but rather evolve through a progressive growth process, the interest in optimal networks lies in the fact that they constitute interesting benchmarks to compare actual networks with. For example, the comparison of a real-world network with the MST constructed over the same set of nodes indicates how far we are from the minimum cost possible, an important information for applications.

Here we will focus on a small set of examples and will leave aside the important litterature about practical applications of graph optimization. An important example in transport network applications is the hub-and-spoke structure (see for example [50] and references therein) where direct connections are replaced with fewer connections to hubs which form a network at a larger scale. The hub-and-spoke structure reduces the network costs, centralizes the handling and sorting, and allows carriers to take advantage of scale economies through consolidation of flows. Instead we will focus on transition aspects and we will essentially discuss a family of optimal networks that comprises the MST and the star graph. We will also discuss new results about the effect of congestion on some optimal networks and finally, how the existence of fluctuations can induce the emergence of loops in optimal networks.

A family of optimal trees

The minimum spanning tree is defined as the graph which minimizes the total cost given by a sum over all edges belonging to this tree. The weight of a link is in general a simple local function and does not depend on the other links. Another simple example of an optimal tree is the star graph (all nodes are connected to a single hub) that minimizes the average shortest path (if one moves a link from this configuration, it is easy to see that the average shortest path can only grow). At this point we could ask if there is a general framework for describing these different optimal trees and if there is a relation between them. In [START_REF] Barthelemy | [END_REF] it was suggested that these optimal trees can be viewed as particular cases of the minimization of the following quantity

E µν = e∈T g(e) µ d(e) ν (69)
where g(e) is the BC of edge e and d(e) is the length of this edge, and the sum is over all edges on the tree T . The exponents µ and ν control the relative importance of distance against topology as measured by centrality. Fig. 14 displays examples of spanning trees obtained for different values of (µ, ν). For (µ, ν) = (0, 1) we recover the euclidean minimum spanning tree (see Fig. the energy ( 69) is proportional to the average betweenness centrality which is also proportional to the average shortest path e b e ∝ (see for example [START_REF] Barthelemy | Morphogenesis of Spatial Networks[END_REF]). The tree (1, 0) shown in Fig. (14d) is thus the shortest path tree (SPT) with an arbitrary 'star-like' hub (a small non zero value of ν would select as the star the closest node to the gravity center). For intermediate cases such as (µ, ν) = (1/2, 1/2) we obtain the 'optimal traffic tree' (OTT) (see Fig. (14b)) which displays an interesting interplay between distance and shortest path minimization (see [START_REF] Barthelemy | [END_REF]). The spatial properties of the OTT are also remarkable, in particular it displays (Fig. 15) a hierarchical spatial organization where long links connect regional hubs, that, in turn are connected to sub-regional hubs, etc. This hierarchical structure can be probed by measuring the average euclidean distance between nodes belonging to the cluster obtained by deleting recursively the longest link. For the OTT, we observe a decrease of the region size, demonstrating that longer links connect smaller regions, a feature absent in non-hierarchical networks such as the MST, the shortest path tree or the random tree (see Fig. 16).

Finally, for (µ, ν) = (1, 1), the energy is proportional to the average shortest weighted path (with weights equal to euclidean distance (see Fig. (14c)) and in this case centrality dominates over distance and a 'star' structure emerges with a few dominant hubs.

The minimization of Eq. ( 69) thus provides a natural interpolation between the MST and the SPT, a problem which was addressed in previous studies [START_REF] Khuller | [END_REF]. The degree distribution for all cases considered above is not broad, possibly as a consequence of spatial constraints. We expect that when we vary continuously the parameters µ and ν, there will be transitions between these different structures and a complete inspection of the plane (µ, ν) would be very interesting.

Congestion-induced transition

Congestion will naturally act on the shortest paths organization. In the case where the network is fixed and has one hub, the study [START_REF] Ashton | [END_REF] demonstrated the existence of an optimal number of connections that minimizes the total traveling time. In another work [68], the authors studied the structure of networks optimizing the average search cost both in the presence and in the absence of congestion. They demonstrated the existence of a transition from a centralized structure for low congestion situations to a more decentralized topology for highly congested cases. Here, we will show that a transition from centralized to a decentralized network is actually present for the lowest non-trivial form of the cost which contains interactions between users, a way to describe congestion.

Capacity constraints (such as the number of cars on a given road) are important and result in an increase of time or cost. A popular form which expresses the travel time τ (e) on a link of length d(e) is given by the Bureau of Public Road (BPR) function [START_REF]of Public Roads, Traffic Assignment Manuel[END_REF] which can be written as

τ (e) = d(e) v 1 + T (e) q 0 φ ( 70
)
where φ > 0, v is the average velocity on links, and T (e) is the traffic on e. In our simplified model, we use the BC as a simple proxy for the traffic: T (e) = g(e). The quantity q 0 corresponds to the practical capacity of the link, and the exponent φ is usually large (some empirical studies display a value of order φ ≈ 4 [START_REF] Branston | [END_REF]) but we will consider here the lowest non-trivial value φ = 1. We consider the problem of finding the optimal graph that minimizes the total time (which we will also call 'energy') spent on the graph and given by E(q 0 ) =

If the capacity is very large g(e) q 0 , congestion effects are absent and we recover an optimal network corresponding to E ≈ e g(e)d(e) discussed above ((µ, ν) = (1, 1)) where centrality dominates over distance and with the presence of a few dominant hubs. In the opposite case where the capacity is very small g(e) q 0 , we obtain an energy of the form E ≈ e g(e) 2 d(e). Our numerical simulation indicates that the corresponding optimal network is a 'star-hub' where one node (the hub) is connected directly to all the other nodes. This is also the situation which corresponds to the shortest path tree obtained by minimizing the shortest path E ∝ (in the notation introduced above it corresponds to (µ, ν) = (1, 0)). The main difference here is that the distance term in Eq. ( 71) will select the hub as being the closest node to the gravity center of all nodes. When we increase the capacity, the optimal network will thus evolve from a star configuration to a spatially organized network. In order to monitor this topological transition, we can measure different quantities, and we will focus here on the degree q ⇤ FIG. 17: Degree dominance versus capacity. For a capacity of order q0 = q * ≈ 1 there is a sharp transition between a one star network to a multipolar structure (simulation obtained for N = 1, 000 nodes). FIG. 18: The network observed numerically right after the transition (here N = 1000 nodes and q0 = 0.95).

dominance d * defined as

d * = 1 (N -1)(N -2) i (k * -k i ) (72)
where k * = max i k i . For a star network we have d * = 1, and for an homogeneous network with a constant degree, the dominance is d * = 0. The evolution of the degree dominance when q 0 is increasing is shown for numerical simulations in Fig. 17. We observe in this figure a sharp transition in the dominance for q * ≈ 1. We can estimate where the transition takes place and we provide here this simple argument, valid for energies of the form

E = e g(e)d(e) 1 + g(e) q 0 (73)
Starting from the star graph situation at low q 0 , the transition occurs when a new hub appears, as shown in Fig. 18. In order to compute q * , we have then to estimate the energy difference between the one star system and the new two-stars network where the hubs are separated by some distance δ (see Fig. 19). For the one star system, all centralities are equal and given by

g ∼ N/N 2 ∼ 1/N (74)
(all BCs are normalized here by a factor 1/N 2 ). The energy of the one hub (A) configuration is thus

E ∼ 1 N + 1 N 2 q 0 e d(e) (75)
The length of links correspond to the distance to the hub 'A': e d(e) = N i=1 |r ir A | where r i denotes the position of node i. Numerical experiments suggest that a new hub 'B' appears (see Figure 19), and we denote the vector between A and B by δ. The simulations also suggest that the new hub is connected to a set of aN nodes comprised in an angle 2θ (see ( Figure 20). For networks large enough, when the density of nodes is uniform, the angle θ and the number of nodes can simply be related by aN = N 2θ/2π leading to a = θ/π. The links attached directly to A or B have a centrality which is of order ∼ 1/N , and only the centrality of the link A -B is different and is of the order a(1a). The energy of this new system is then

E = 1 N + 1 N 2 q 0 i∈A |r i -r A | + i∈B |r i -r B | +δa(1 -a) 1 + a(1 -a) q 0 ( 76
)
where i ∈ A(B) means that the summation is over the nodes directly attached to A(B). The energy difference ∆E = E -E at lowest non-trivial order in δ is then given by

∆E ≈ a(1 -a)δ 1 + a(1 -a) q 0 - 1 N + 1 N 2 q 0 i∈B δ • (r i -r A ) |r i -r A | + O(δ 2 ) (77)
By using a continuous approximation for computing the sum, we obtain at dominant order in δ and N

∆E ≈ δa(1 -a) 1 + a(1 -a) q 0 - δ π sin aπ + O(δ 2 , 1 N ) (78)
We can easily study this function and show that its sign depends on the slope at a = 0. An expansion around this point gives ∆E ≈ δa 2 1 q 0 -1 + O(a 3 ) (79) which shows that there is a transition for q 0 = q * = 1. If q 0 > 1, ∆E < 0 and a second hub can appear. This simple argument thus predicts that for large enough networks, the one star configuration is indeed stable up to a finite value of the capacity q 0 , and also predicts a value 1.0 which is in good agreement with the value observed in numerical simulations. We thus see in this simple toy model that congestion can induce transitions between the structure of networks. For large capacity, congestion is irrelevant while for smaller capacity, we observe a transition to a centralized organization with one main hub. Also, this formalism discussed here probably allows for other, more general studies about the effect of congestion in optimal networks. In particular, we could probably study the effect of a more general cost function (Eq. ( 70)), or at least the effect of other values of the exponent φ.

Fluctuations and the emergence of loops

In most examples studied in the literature, optimal networks are trees. However in many natural networks such as veins in leaves or insect wings, one observes many loops. In [71], the authors show that loops can emerge in optimal networks according to the convexity of the cost function. More precisely they consider the total transportation cost in the network given by where i e is the quantity of material along the link e, k e is the resistance and γ is an exponent (in the electric circuit case γ = 2, i e is the current, and E is the power dissipated). In addition, the total flow of injected currents is assumed to be equal to the outflow. For γ > 1, there is then a unique flow pattern with non-zero current along all links (and therefore with loops). In contrast, for 0 < γ < 1, the solution is not unique but all of them have a tree structure [71]. These results were confirmed in [72] where the authors show a transition from trees to graphs with loops and which corresponds to a discontinuity in the slope of the cost function. More recently, two studies which appeared simultaneously [73,74] rediscussed the problem of the existence of a non-zero (and sometimes high) density of loops in real optimal networks such as veination patterns in leaves. In particular, it seems that for real-world systems the existence of fluctuations is crucial in the formation of loops. In the context of the evolution of leaves, the resilience to damage also naturally induces a high density of loops (see [74] for an example of flow re-routing after an injury).

In these studies, the model is defined on an electrical network with conductances C e on each link and the total dissipated power where in this equation it is assumed that the cost of a conductance C kj is given by C γ kj where γ is a real number. This constraint can be interpreted as the limit of the amount of resources available to construct the network. The quantity V i is the potential at node i.

P = 1 2 k j∈Γ(k) C kj (V k -V j ) 2 (
Following [74], we can introduce two variants of this model. The first one which represents the resilience to damage is defined as follows. We cut a link e and compute the total dissipated power denoted by P e . The resilience to this damage can then be rephrased as the minimization of the functional

R = e∈E P e (83)
Note that if breaking the link e disconnects the network, it will lead to an infinite resistance and to an infinite value of the dissipated power P e : the finiteness of R implies the existence of loops in the optimal network. In another variant, [74] Katifori et al. introduces time fluctuating load by considering a system with one source at the stem of the leaf and one single moving sink at position a. For this system, one can compute the total dissipated power P a and the resilience to fluctuations can be rephrased as the minimization of the functional In these models, one observes the formation of loops (see Fig. 21), reminiscent of the ones seen in real leaves. These studies shed a new light in the formation and the evolution of real-world networks and open interesting directions of research. In particular, it would be very interesting to understand more quantitatively the condition of appearance of loops in spatial networks.

DISCUSSION

We tried here to review some examples of transitions in spatial networks. We didn't mean to be exhaustive and other models that display transitions or crossovers could have been discussed here. We saw that in some cases the transition can be percolation-like with the appearance of a giant cluster. In other cases we observe less common transitions with different phases that are characterized by a different scaling of some quantity with the system size (the average shortest path or the average link length, etc.). These 'topological transitions' between different structures can be of interest in real-world situations where it is not only the total connectivity that can vary (as it is the case for percolation) but other features connected to navigation over these networks. Some transitions can also be more subtle and concerns essentially the traffic on networks and the results about the localization of bottlenecks shed light on the organizaton of flows in spatial networks. In the different models that we described here, the spatial distribution of the betweenness centrality can indeed display some sort of localization transition when the density of edges increases with a concentration of bottlenecks around the gravity center of the system. Generally speaking, the study of high BC nodes is an important endeavor as it represents a generalization of studying the maximum BC nodes that governs the behavior of the system in saturated cases where the traffic exceeds the capacity of links.

All these examples show that spatial networks display a large variety of behaviors with crossovers or transitions that separate different regimes characterized by different large-scale properties. A more systematic study would be needed here in order to distinguish sharp transitions from crossovers and to understand if these phenomena can be understood in a more general framework, such as phase transitions in statistical physics.

FIG. 2 :

 2 FIG.2: Construction of the Watts-Strogatz model for N = 8 nodes. At p = 0 each node is connected to its four nearest neighbors and by increasing p an increasing number of edges is rewired. Adapted from Watts and Strogatz[18].

FIG. 3 :

 3 FIG. 3: Schematic representation of a spatial small-world in (a) one dimension and (b) two dimensions. The dashed lines represent the long-range links occurring with probability q( ) ∼ -α . Figure inspired from [25].

FIG. 4 :

 4 FIG. 4: Various networks obtained with the rule F (d) = d α . Figure taken from [38].

FIG. 6 :

 6 FIG.6: Exponent τ versus β. For β β * we recover the star-graph exponent τ = 1 and for the other extreme β β * we recover the MST exponent τ = 1/2. In the intermediate range, we observe a continuously varying exponent suggesting a non-trivial structure. The shaded area represents the standard deviation of τ . Inset: In order to illustrate how we determined the value of τ , we represent Ltot versus N for two different values of β. The power law fit of these curves gives τ . Figure taken from[START_REF] Louf | Proceedings of the National Academy of Sciences[END_REF].

FIG. 8 :

 8 FIG. 8: Examples of hub-and-spoke structures with rings. (a-c,e): Typical fungi networks, in (c) a schematic representation of the nutrient flow is shown. (d) The model studied in [52-54] with spokes radiating from a hub. (f) Road network in Houston showing an inner hub with a complicated structure. Figure taken from [53].

FIG. 10 :

 10 FIG.10: Representation of the toy model discussed here. The number of branches is here N b = 5, the number of nodes on each branch is n = 11 and the loop is located at a distance = 6 from the center 0. The node C is at the intersection of a branch and the loop and T is the terminal node of a branch. Figure taken from[61].

FIG. 11 :

 11 FIG. 11: Difference δg( ) = g0 -gC versus /n for N b and n fixed and for different values of w in the range [0, 12.5].For values less than a threshold (wc ≈ 4 here) there is a minimum that is negative. Figure from[61]

FIG. 12 :

 12 FIG. 12: Effect of edge-density ρe on the betweenness. (Left panels) BC distribution for the MST and for the model obtained by pruning the Delaunay triangulation for various values of the density (obtained for N = 10 4 and a hundred realizations). As a guide to the eye, the 'tree-like' region (shaded) is distinguished from the 'loop-like' region below N . (Right panels) Generated network with the corresponding edge density ρe. Shown in red are the nodes in the 90 th percentile and above in terms of their BC value. Figure taken from [62].

FIG. 13 :

 13 FIG.13: Behavior of high BC nodes. The clustering index C θ (for the θ percentile of high BC nodes) decreases for denser networks, capturing the tendency of the nodes to be increasingly clustered around their center of mass. Figure from[62].

FIG. 14 :

 14 FIG.14: Different spanning trees obtained for different values of (µ, ν) in Eq. (69) for the same set of N = 1000 nodes. (a) Minimum spanning tree obtained for (µ, ν) = (0, 1): in this case the total distance is minimized. (b) Optimal traffic tree obtained for (µ, ν) = (1/2, 1/2). In this case we have an interplay between centralization and minimum distance resulting in local hubs. (c) Minimum euclidean distance tree obtained for (µ, ν) = (1, 1). In this case centrality dominates over distance and a 'star' structure emerges with a few dominant hubs. (d) Optimal betweenneess centrality tree obtained for (µ, ν) = (1, 0). In this case we obtain the shortest path tree which has one star hub (for the sake of clarity, we omitted some links in this last figure). Figure taken from[START_REF] Barthelemy | [END_REF].

FIG. 15 :FIG. 16 :

 1516 FIG.15: Hierarchical organization emerging for the optimal traffic tree (µ, ν) = (1/2, 1/2) (for N = 1000 nodes). Longer links lead to regional hubs which in turn connect to smaller hubs distributing traffic in smaller regions. Figure taken from[START_REF] Barthelemy | [END_REF].

FIG. 19 :

 19 FIG.19: Simplified picture used for the theoretical calculation of q * . On the left, the initial star network has an energy E. On the right, the nearest site of the first hub becomes a hub itself. The energy of this configuration is E .

2 ABFIG. 20 :

 220 FIG.20:The nodes which are attached to the new hub B occupy a space of angle 2θ. The average number of nodes in this section is θN/π.

FIG. 21 :

 21 FIG. 21: Optimal networks obtained for different values of γ and for (left panels) the resilience to damage and (right panels) for a fluctuating load. We observe loops (γ < 1) and different structures according to γ. The thickness of links is a function of their conductance. Figure taken from [74].

TABLE I :

 I Correspondance between the regimes for models A and B obtained by replacing α with α -d + 1.

	Model A

Acknowledgments

I thank my colleagues and collaborators for many interesting discussions on various aspects of spatial networks: H. Barbosa, M. Batty, H. Berestycki, P. Bordin, J. Bouttier, C.P. Dettmann, P. Di Francesco, A. Flammini, G. Ghoshal, E. Guitter, P. Jensen, A. Kartun-Giles, E. Katifori, A. Kirkley, V. Latora, T. Louail, J.-M. Luck, J.-P. Nadal, V. Nicosia, K. Mallick, C. Roth, E. Strano, M.P. Viana. I also thank the geohistorical data group, in particular M. Gribaudi and J. Perret. I thank P. Grassberger for pointing out some mistakes and important references.