<figure><img src="image_1.png" /></figure>

HAL
open science

# A spatial multi-scale object to analyze road networks

Claire Lagesse, Patricia Bordin, Stéphane Douady

► To cite this version:

Claire Lagesse, Patricia Bordin, Stéphane Douady. A spatial multi-scale object to analyze road networks. Network Science, 2015, 3 (1), pp.156-181. 10.1017/nws.2015.4. hal-05038332

HAL Id: hal-05038332

https://hal.science/hal-05038332v1

Submitted on 26 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A spatial multi-scale object to analyze road networks

## C. LAGESSE

Université Paris Diderot, Sorbonne Paris Cité, Matière et Systèmes Complexes (MSC), UMR 7057, Paris, France

## P. BORDIN

Université Paris-Est, Institut de Recherche en Constructibilité, ESTP, Cachan, France.
Université Paris Diderot, Sorbonne Paris Cité, Institut des Energies de Demain (IED), UMR 8236, Paris, France

## S. DOUADY

Université Paris Diderot, Sorbonne Paris Cité, Matière et Systèmes Complexes (MSC), UMR 7057, Paris, France
(e-mail: lagesse.claire@gmail.com)

### Abstract

City road networks have been extensively studied for their social significance or to quantify their connections and centralities, but often their geographical origin is forgotten. This work focuses on the spatial-geographical and geometrical aspects of the road network skeleton. Following previous work, a multi-scale object, the way, is constructed, based only on the local geometry at road crossings. The best method to reconstruct significant elements is investigated. The results show that this object is geographically meaningful, with many particular characteristics. A new indicator, structurality, is introduced and compared with previous indicators, on the cities of Paris and Avignon. Structurality appears to be stable over the borders of the map sample, and is able to reveal the underlying coherence of the road network. This stability can be interpreted as coming from the particular way the network developed in time, and was later preserved. This link with the historical development of the cities, which deserves to be further studied, is exemplified in the cases of Villers-sur-Mer (France) and Manaus (Brazil). The construction method, the results, and their potential meaning are discussed in detail so that they can be used in various related disciplines, such as sociology, town planning, geomatics, and physics.

Keywords: road network, graph theory, spatial analysis, city modeling, morphogenesis

### 1. Introduction

Cities can be seen as the epitome of complex systems. Like living organisms they are born, develop, need constant external influx, spread some of this influx around to develop suburbs, and sometimes decline and die. They have been the subject of research for a long
time. Of the three elements that fill the city space—buildings, space division properties, and road networks—buildings are the least persistent and road networks are the most. While buildings are destroyed and reconstructed, with possible property recomposition, roads have to remain functional to give access to every occupied space, and allow permanent circulation through the whole space.

City road networks are a key example of a spatial network. They develop in time and, with minimal reorganization, their particular configuration is a record of their history. In this sense, road networks are a perfect example of networks developing both in space and time.

Road network graphs have been studied for a long time, first by town planners, who developed good intuitions for their analysis. But this was based on their own practice and personal knowledge. On a more abstract level, city maps were the origin of network theory, starting with Euler's problem of the seven bridges of Konigsberg." Since then, many measures have been developed to characterize networks (Albert & Barabasi, 2002; Boccaletti et al., 2006). One proposed measure is called betweenness centrality (Freeman, 1977). It counts how many times an element of the graph is used when traveling between any pair of elements through a certain type of minimal path. In these studies, the spatial nature and particular geometry of the network is often discarded (O'Sullivan, 2014). In the computation of betweenness, even if the actual length can be taken into account, the topological aspect remains the only one investigated. The road network is then reduced to the intersections as nodes and the road segments as connections between them. In this way its treatment is similar with non-geographical networks such as social networks. This is a major loss for a spatial network: the link between two objects in this kind of network is not only abstract, it is a geographical connection with a proper shape, an environment, and a neighborhood, which make each link unique and more complex than a simple topological connection.

Topologically, the road network appears to be rather homogeneous, with nearly identical meshes where each node is connected to a small mean number of other nearby nodes (between 3 and 4), similar to regular grids (see Figure 1) (Cardillo et al., 2006; Crucitti et al., 2006). Other indicators seem to vary only a little between extreme cases such as tree-like slums or perfectly regular Manhattan grids (Buhl et al., 2006). This is very different from exhibiting organizing properties such as small-world networks, which are found in so many other instances, where the network has a biased growth toward the most connected nodes.

Roads are geographical elements used by humans for their displacement. Their straightness is a key feature, for both visibility and conservation of energy. The expansion of vision through straight street segments has been emphasized in the “space syntax” concept developed by Hillier et al. (1993). It postulates that people move according to the perception they have of the surrounding space. Vision of distant elements, made possible with a straight empty space, favors displacement. Locally-straight elements are then distinguished in the network, and correlated with actual displacements of people (Genre-Grandpierre, 2001; Genre-Grandpierre & Foltete, 2003). Contrary to previous approaches, the “space syntax” one introduces the perception of the network by its users and develops a quantitative tool to correlate its measurements with observed behavior. However, constructing the straight elements is not straightforward when the width of the street is taken into account. These works perform a morphological interpretation of the city through local perspectives. The reconstructed straight parts do not preserve the exact network
geography and geometry: the elements constructed could include several road segments, and also end within road segments (at a turn).

<figure><img src="image_3.png" /><figcaption>Fig. 1. Histogram of vertex degree, left, and of length of arcs, right, in the cities of Paris (circles) and Large Avignon (triangles). Left: the two cities have nearly the same number of end points. The most numerous degree is 3, and it decreases a bit more quickly than an exponential with a characteristic number of 0.8 for Paris, and 0.5 for Avignon. This means that crossings with more than 3 + 0.8 (4) or 3 + 0.5 (4) become very rare. The average is 3.08 for Paris and 2.72 for Avignon, and the organic ratio (see text) is 0.76 for Paris and 0.9 for Avignon. Right: the distribution of length of the arcs is roughly exponential, with a very similar characteristic length of 60 m, and supernumerary long arcs especially for Avignon corresponding to countryside roads.</figcaption></figure>

The idea of continuity and larger elements was further developed by Jiang and Claramunt (Jiang & Claramunt, 2004) following the actual toponymy of roads as they are used in cities. The new elements (the named roads) are geographically welldefined and offer another vision of the spatial organization, as they can be much larger than road segments (up to the city width). From this geographical information they construct a “dual” network, which represents how each road is connected to others. They study this new abstract graph, ignoring its spatial properties. This approach presents small-world characteristics. It is slightly weakened by relying on GIS information of street names, which can be incomplete, and also depends on administrative borders creating artificial change of name of continuous roads.

This led Porta, Latora, and co-workers to propose a quantitative method of constructing the road continuity, through the observation of connecting roadsegment angles at a crossing, grouping the most aligned in a method they called Intersection Continuity Negotiation (ICN) (Porta et al., 2006). They further studied the small-world aspects of cities, showing a global similarity of their structure (Cardillo et al., 2006; Crucitti et al., 2006; Scellato et al., 2006).

In this article, following Porta, Latora, and co-workers, we explicitly take into account the geographical characteristics of road networks, in particular their geometry at intersections. We revisit the ICN method to study what is the best way to reconstruct the road’s continuity. To further emphasize the straightness, we define a distance measure which is the minimal number of turns to go from one road to another. We use this to construct an indicator, the structurality, which is how many turns it takes on average to go from a given road to the rest of the city. This indicator is shown to be different than the betweenness, and also robust to the delimitation of the network sample. This robustness can be interpreted as the trace of the historical development of the network with the
addition only of smaller elements, without reorganization. The comparison of the actual
historical road pattern development and the analysis developed here is a promising future
avenue for research.

We show that the traditional method of naming roads, further developed algorithmically
in the ICN method and refined here, leads to a geographical element that is not only useful
for statistical computation, but has geographical and historical meaning. This study deals
with the modeling process at the intersection of different fields that require a link between
scientific theory and social interpretation (Bordin, 2006). Our aim is to propose a cross-
disciplinary object which brings relevant information to a physicist, a geometrician, an
archeogeographer, or a town planner.

Our main result is that the reconstructed geographical element, the way, not only has a
geographical and social meaning but also a historical one, allowing us to discuss the city
growth history. This property can be linked to the city's particular dynamics of expansion.
The efficiency of this originally traditional description might be based on the fact that it
corresponds not only to the network construction in time, but also to the actual way it is
perceived and used.

2. Way definition and construction

The notion of “way” is polysemous, with different meanings such as “road”, “street”,
“path”, etc. It can cover very different concepts from the point of view of a town planner,
a sociologist, an archeogeographer, a geometrician, or a physicist. One will consider the
detailed object, with a width, a surface, a sidewalk; another will think over a place of social
exchange and perception, with different uses; a third will refer to a two-dimensional object
with attributes; and the last one will discuss of a subset of a graph. The term “way” carries
the idea of continuity, perspective, and path between two points. So, it contains the ideas
of aim and ultimately straightness.

Here, we restrict ourselves to the center line of streets, the wired network. We do not
consider the characteristics of the road available in modern GIS like their surface (or
width), their name, use, or other attributes. In particular, we do not consider the distinction
between “roads” (for countryside), “streets” (for urban settlement), or “paths” (for
pedestrian or bike ways). We remove all these aspects to see what information can be
extracted with minimal spatial (geographic) information.

A road network is usually approximated with linear segments linking crossing points.
Thus, a normal graph G that consists of edges E (links) connecting nodes N (crossings) can
be defined by G = (N, E). However, the connecting points of degree 2, connecting only 2
linear segments, have no fixed meaning and depend on the degree of approximation of the
drawing (Courtat et al., 2011). We remove the connecting points of degree 2, as side points,
and consider only end-points or crossing nodes with 3 or more links as vertices. Between
two vertices we have groups of segments (linear links) connected to each other to form an
arc. A graph is then defined by its arcs A, connecting the vertices V, G = (V, A). The main
point here is that arcs, as a group of segments between end points, are not necessarily
straight. At a vertex, the first straight segment (taken between the vertex and the first side
point) indicates the angle at which the curved arc connects to another one at the crossing.
Considering arcs as the aggregation of segments between two vertices is the introduction
of the geographic aspect in a topological representation. It allows us to work with a network
anchored in space, coherent with reality.
A graph, embedded in a two-dimensional space, is not necessarily planar: two arcs crossing each other will form a vertex only if they are on the same plane in reality. For example, most city maps are planar as being laid on the earth surface, but few streets can pass over each other (bridges) without connections between them (as do “rue Pascal” and “Boulevard de Port-Royal” in Paris).

We test our measures on the city of Paris, an urban space with a long history, with 19,423 vertices and 32,173 arcs, and a large territory around Avignon (in the South of France), mixing territories of all ages of urbanization and some agricultural areas, with 9,742 vertices and 14,531 arcs.

Studying the road network graph $G = (V, A)$ reveals a planar structure with homogeneous connections around 3 (see Figure 1 left). We can define an organic coefficient, giving the predominance of degree 3 and 1, corresponding to successive connecting roads, compared to degree 4 or more (planned grid city), computed as

$$ \frac{\#[1]+\#[3]}{\#[V]} \quad \text{(Courtat et al., 2011). This coefficient is 0.75 for Paris, showing that only 1/4 can be considered as planned, and 0.9 for Avignon, showing a strong predominance of organic growth, coherent with its preserved middle age center and agricultural surroundings.} $$

To further study the road network, we will keep aggregating the arcs to form larger elements. Following previous work (Hillier et al., 1993), we emphasize the notion of straightness, as used traditionally and in the space syntax. It defines straight elements—straight portions of the network—which cut the arcs in pieces as the segments, but can also join different segments if they are aligned at a crossing. Here, as in the work of the Porta et al. (2006) we reconstruct elements similar to the common use of “streets”, keeping the graph structure. We thus create a hypergraph of *ways*, which are ensembles of arcs.

We want *ways* to be generic objects which allow us to broaden the quantitative analysis from the local city block to the whole city. To remain simple and efficient, their construction should be local, with simple rules applied to each vertex and the segments linked to it. We will test three construction methods to identify the best manner to create *ways* and to ensure their relevance.

The three different methods tested are all based on defining the aggregation of two segments at a crossing. Each possible pair at each crossing is then constructed, ending with a table of couples. This table is then followed to reconstruct *ways*. Because pair construction is local, the reconstruction will give the same results independently of the order of the segments considered. To connect pairs, we only consider local geometric information: the angles between the last segments connecting to the crossing. If the segments are aligned, then the two arcs extending them are considered part of the same way.

* Method 0, or “M0”: The first method selects the pair of segments forming the minimal deviation (complementary angle at 180°), and associates them. Then it checks if another pair with minimal deviation can be associated among remaining segments, until all the possible pairs are made. This method minimizes the deviations for each pair.

* Method 1, or “M1”: The second method builds the ensemble of pairs that globally minimizes the deviations. For this, at each crossing, an aggregation by pairs is made
and the sum of the deviation angles for all the pairs is calculated. All the possible aggregations by pairs are computed, and the one that minimizes the sum of the deviations is selected. This method minimizes the deviations globally.

* Method 2, or “M2”: The third method aggregates the segments by pairs randomly, without considering the actual connection angles. It is used as a calibration.

The “straight” or “aligned” notion is either a strict mathematical condition, that has no chance to happen in reality, or it has a vague meaning. In any case, we have to determine a limit of deviation angle after which roads are no longer “aligned”. We thus introduce a threshold angle $\alpha$, to see its influence on the results. For method 0, each minimal pair is aggregated only if the deviation is smaller than this threshold value. The same is done for method 2, which is a way to re-introduce the condition of “alignment”, even if the pair is taken randomly and is not the one minimizing the deviation. With method 1, the aggregation is made for the minimal global mean of deviation, and the threshold is applied to the sum of angles.

The deviation angle is determined by considering the complement to 180° of the angle formed by the two aggregated segments at the crossing. If $\alpha_t = 0°$, arcs have to be exactly aligned to be coupled. On the other hand, if $\alpha_t = 180°$, there is no angle constraint. This unconstrained situation was used before in M0 in Porta et al. (2006), while (Courtat et al., 2011) used an $\alpha_t = 90°$, meaning that a way is straight at a crossing as long as it doesn’t go backward.

### 3. The multi-scale nature of the way

On the original distribution of angles of the segments, one observes a peak at 0°, and a slightly smaller one at 90° (see Figure 2). These two peaks, with the function of probability decreasing around them as negative power laws, reflect the tendency to create straight streets and perpendicular crossings. The asymmetric distribution around these peaks, with an exponent twice as big for 0° than for 90°, shows that straight streets are more enforced than perpendicular crossings. In other words, the road construction is more sensitive to alignment than perpendicularity. The distribution of the selected angles along the ways for the random method M2 is very close but not exactly proportional to the original distribution because selecting pairs at a crossing removes potential angles for the remaining segments. When the two distributions for M0 and M1 are renormalized by this random selection, they form a Gaussian curve for angles smaller than 90°. It thus seems that, once removed the basic asymmetric preference for alignment and perpendicularity, the selection of angles among the normalized possibilities is simply a normal distribution with a wide standard deviation of 40°. In other words, streets are aligned up to a deviation angle of 40° in Paris (36° in Avignon), which is quite large.

The histogram of arc length appears to have a roughly exponential distribution (Figure 1 right), with a very similar characteristic length for Paris and Avignon (60 m and 59 m respectively). This corresponds to the typical size of a city block in French cities. There are few arcs over the exponential in both distributions corresponding to highways, such as surrounding belts, and rural roads for Avignon (in proportion more numerous).
<figure><img src="image_4.png" /></figure>

Fig. 2. Left: Histograms of the angles at the crossings in Paris for the original segments (full triangles), for the random method M2 (empty triangles), and for the methods M0 and M1 (full circles and empty squares, respectively). The original distribution can be fitted with two different power laws (dashed lines), with an exponent -1.25 around 0° and -0.625 around 90°, giving this asymmetric distribution. The random one is close to a reduced original distribution, and the distributions for the two other methods constantly decrease for large angles, except for a small peak around 90°. Right: the two distributions for M0 and M1 when renormalized by the random distribution for M2. For angles smaller than 90°, it becomes a Gaussian distribution of maximum 0° and width 40°, and some remaining noise after 90°.

<figure><img src="image_5.png" /></figure>

Fig. 3. Histogram of the length of the ways, reconstructed with M0, left superposed to the histogram of the arcs for Paris, and right the histogram for the logarithm of the same lengths. Left: the characteristic length of the exponential is now increased from 60 m for the arcs to 150 m for the ways, so in average 2.5 blocks, but the supernumerary of long ways become very important. Right: on the histogram of the logarithm of the lengths (normalized by 10 = 1 m), one can see that the distribution for the arcs is very asymmetric, with two Gaussian parts of very different width (corresponding to a variation of factor 6 on the left and only 2.6 on the right, for a maximum still around 67 m). The successive histograms of the logarithm of the way lengths—corresponding to threshold angles of (20°, 60°, 120°, and 180°) for M0, in circles from empty to full—are closer to a Gaussian, except for a part at higher length that is now supernumerary. The maximum correspond to a characteristic length of 135 m with a width corresponding to a factor 4.

The histogram of the lengths of the ways appears to have a much wider distribution, with a more extended tail toward very long ways (Figure 3 left and 4). This is the aim of the aggregation process, to construct larger elements that can extend across the map considered.

The logarithm histograms show many different things. The first is that they are generally close to Gaussian curves, meaning the lengths are actually log-normal distributions. This corresponds perfectly to a random space dividing process, where a new segment cuts a surface between two previous segments, and also cuts those
<figure><img src="image_6.png" /></figure>

Fig. 4. Histogram of the logarithm of the length of the ways, reconstructed with M1, squares, left, and M2, triangles, right, superposed to the histogram of the log the length of the arcs for Paris. The method M1 converges toward the same distribution as M0, but more slowly, in particular for the right supernumerary large lengths. The method M2 seems to converge only for the final threshold angle of 180°, with a larger characteristic length around 180 m and width corresponding to a factor 7, keeping in particular more small elements of the original arc distribution. Contrary to M0 and M1, there are still less large lengths than a Gaussian would predict.

in two. The new smaller segments from the cut are thus fractions of the previous length. If this fraction is purely random, the final lengths are products of random numbers. Their logarithm is the sum of the logarithm of the random numbers, which gives a Gaussian curve. For such processes, as observed in ceramic cracks, quadrangular block are obtained after enough divisions (Bohn et al., 2005a; Strano et al., 2012). In cities, with triangular junctions, we observed here (see Figure 1 left) the same process, allowing us to recover in part their history of construction (Bohn et al., 2005b).

From this general principle, which is compatible with a basic mechanism of creation of street patterns, the deviations that we observed from the Gaussian curves are significant and reproducible (as we found the same for Paris and Large Avignon). First, the distribution of arc lengths shows that there is a strong lack of long arcs. The random method M2 is able to create the longest ways, but it also keeps the smallest ones (having a larger distribution). It excludes long ways compared with the Gaussian distribution. In this way, it is able to construct large elements, without changing its qualitative aspects. On the contrary, the two other methods, M0 and M1, converge toward tighter distributions, with typical supernumerary long ways compared with the Gaussian distribution. Between these two methods, M0 converges the most quickly (already for 60°), while M1 converges to supernumerary long ways around 120°.

The speed of transition is revealed by looking at the mean of these distributions while increasing the threshold angle from 0° to 180° (Figures 5 and 6). The results are comparable between Paris and Large Avignon, taking into account the difference in number of points, which makes the histograms better defined for Paris, and the dependence on the threshold angle easier to compute for Avignon. The first method thus converges more quickly around 60 to 80°, and is more efficient in creating longer ways with smaller deviation angles.

Together with the length of the ways, another characteristic can be introduced, called the *connectivity* of a way, which is the number of segments from other ways connected to it. This is not exactly the number of vertices (or number of arcs +1), as
<figure><img src="image_7.png" /><figcaption>Fig. 5. Left: decrease of the numbers of ways as the threshold angle increase for the three methods (M0 circles, M1 squares, M2 triangles), for Avignon, with negative power law fits. The first method M0 is the quickest to decrease, by a factor 2, while the numbers of ways decrease only slightly with M2, before a second jump when crossing the 90° limit. The same step at 90° can be visible even if much smaller on the two other curves. Right: the average number of arcs in one way, for the three methods, as a function of the threshold angle, for Avignon, with logarithm fits. Similarly, M0 converges quicker around 3, and there is the same step around 90°.</figcaption></figure>

there are variable numbers of segments connecting at intersections. It is close to but not exactly the degree of the vertex (Albert & Barabasi, 2002), in the dual space (the´ way) (Cardillo et al., 2006; Crucitti et al., 2006; Scellato et al., 2006), as one crossing way can give two possible new directions (right or left, for a junction of degree 4), or only one (for a junction of degree 3). This corresponds to the number of direction changes offered by a way (a change of direction is considered, if it does imply a change of way). The value of the connectivity indicator, as well as the length, are local indicators of the way, independent from the network sample chosen, as long as the reconstructed way does not cross the sample border. Thus, the only condition is that its geometric identity remains the same from one sample to another.

In practice, the connectivity of a way w<sub>ref</sub> is calculated by taking each vertex of w<sub>ref</sub> and summing their degree without taking into account the edges of w<sub>ref</sub>. For an intermediary vertex on the way, one has to remove two edges, but only one is removed for the first and last vertex. This gives:

$$ connectivity(w_{ref}) = \sum_{v \in w_{ref}} [deg(v) - 2] + 2 \quad (1) $$

The case in which the way makes a loop has to be treated specially, as formula's final "+2" is no longer necessary, since the degree of the last (and the first) vertex does include two edges of the way. Only the degree of the first vertex is considered.

The distributions of connectivity (Figure 7 left) reveal a qualitative difference between the methods. The random method gives an exponential distribution with a small value of characteristic connectivities, around 2. The other two methods present no characteristic connectivity and extend very far (over 100 for Paris) as a negative
<figure><img src="image_8.png" /><figcaption>Fig. 6. Average angle selected along the ways, for the three methods, as a function of the threshold angle, for Avignon. Left: The random method M2 increases quickly, present the same step around 90° and converge toward a large value of 60°. Right:—zoom for lower angles—M0 converges quicker toward a smaller value, around 5°, compared to 6° for M1, before showing the same 90° step and converging both around 8°. The first increase of M0 and M1 are compatible with a square root (dashed lines).</figcaption></figure>

power law. This shows that they are able to reconstruct very large, coherent ways. The corresponding reconstructed way can be observed in Figure 7.

When resulting maps are compared for the same small set, one can observe the origin of the difference between M0 and M1. Degree 3 vertices are not impacted as the result of the aggregation of segments at a degree 3 vertex will be the same with the two methods. The main difference appears for vertices of degree 4, in the particular type of figure similar to a “K” (see Figure 8). This is a configuration with one main straight axis and two others ending on the crossing from the same side. The minimum angle method M0 favors the straight line (the I part of the K), so creates a couple with the two most aligned arcs and forms another couple with the two remaining arcs (the < part of the K) according to the threshold angle. Method 1 splits the straight line to create two couples with optimized angles. The creation of two deviating crossing ways does not correspond to the intuition we have of the continuity of streets, and makes the way generally less straight.

This situation occurs preferentially at large squares and roundabouts. It emerges precisely as a result of cutting the continuity of the street segments and forcing the travelers to turn around. In this way, it is normal that this structure actually breaks the continuity of the ways. Nevertheless, it could be interesting to remove those disturbances in the analysis in future work.

We can also compare the result of method M0 with the actual street identification in cities. What is found is a good correlation, except that a way is often cut in several streets. This happens for two main reasons. The first is that streets usually change names when crossing an administrative border. The second and more common reason, is that it is tradition that a secondary street, when crossing a principal one, changes its name to distinguish it from the main one. Here, we do not make these
<figure><img src="image_9.png" /><figcaption>Fig. 7. Top Left: Histograms of the connectivity of the ways for the three methods (M0 circles, M1 squares, M2 triangles) for a threshold angle of 60°, for Paris the distribution for M2 is compatible with an exponential of characteristic number of connectivity of 2.1, while the distribution for M0 and M1, very close, have no characteristic number and are more compatible with a negative power law of exponent - 2.7. Top Right and Bottom: Ways connectivity for Paris with M0, M1, and M2 and a common threshold angle of 60°. In dark color the ways with the larger connectivity. The connectivity is much lower for M2, with a very diffused homogeneous background. M1 is similar to M0, but with more contorted ways (a curved way with a loop is visible around "place de l'etoile" for instance). For M0, one can recognize some historical ways and observe a structured background, while the background is diffused for M2. (Color online)</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8. Illustration of the “K” crossing situation. The impact on the structurality (see below for definition) from the different ways reconstruction is clearly visible, with a way abruptly changing of direction and the continuous half losing its structurality quality. (Color online)</figcaption></figure>

distinctions because we do not take into account any characteristics other than the geometry of the skeleton.

All measures indicate that the method M0 is the best for reconstructing significant multi-scale structures from the road network: it converges more quickly, and creates longer ways with low deviation angles and high connectivity. From the above measurements, we conclude that the best method is M0, with a threshold angle around 60°–70°, where the distributions converge before the random transition around 90°.
To further study reconstructed ways, we build other indicators that depend on the global graph. To do so the notion of distance between points of the graph is introduced, so centralities measure can be computed, which is the distance of the city viewed from one element. The graph centers are then the elements with the minimal average distance.

The first intuitive distance is the Euclidian distance between two points of the network. This distance is measured as the crow flies between two elements of the network.

A second distance is the geographical distance between two points of the network. This distance is measured as the pedestrian walks along the network. It is the length of a possible path along the network. This allows us to define a minimal length path connecting two elements. Using the minimal paths a more particular centrality can be defined, the betweenness centrality (Freeman, 1977). For each element of the network, it counts the number of minimal paths passing through it, when all the possible pairs of elements are investigated. The places with the highest number of paths passing through are then the most in-between.

A third distance is the topological distance, where just the number of nodes passed is considered. The centrality derived from this topological distance is called the closeness.

The ways have been built in order to respect the optimum alignment. To reinforce this idea another type of distance can be defined, similar to the topological one described above. If alignment and straight lines are preferred, it means that the cost of passing a crossing is zero when going straight, but is large when making a turn. So there is no cost while staying on the same way, while having one when changing. This is a topological distance in an abstract graph, where nodes are ways, and the connections between these graph nodes are road crossings—as the Euclidean length along the way is not considered a cost. In pattern theory, this graph is called the dual of the original one (Porta et al., 2006). This distance can be called the simplicity distance, $d_{simple}$, because the path between two points with such a minimal distance is also the simplest one, i.e., the shortest to describe with a minimal number of turns (Courtat et al., 2011).

This distance is a complex one, which mixes topology with underlying geometry. The topological distance between the ways is based on the geometrical information used to reconstruct the ways (do we have to change of way or not). Using this distance on the ways, counting just the number of turns, a centrality can also be defined. To take into account the number of possible original and destination points, we weight a destination way by its length. This can be interpreted as counting the number of addresses (destinations) on this way. For reasons exposed below, we call this centrality the structurality of a way :

$$ \text{structurality}(w_{ref}) = \sum_{w \in G} [d_{simple}(w, w_{ref}) * \text{length}(w)] \quad (2) $$
<figure><img src="image_11.png" /><figcaption>Fig. 9. Structuralities of the ways reconstructed with M0, and a threshold angle of 60° for Paris. To enhance the visualization of the indicator, ten length classes of equal total length have been created. Each way have thus an attribute from 0 to 9 to characterize its structurality, 0, the lower values, being the most structural ways. (Color online)</figcaption></figure>

Similar to the distance-based centralities, the more structural ways are those with the minimum value for their structurality measure. From those structural ways it is easier to reach any other point of the network with a minimum topological distance (minimum number of turns, or way change).

With this topological distance in the dual space, a betweenness can also be introduced by counting the number of shortest topological paths that pass through a given way. This betweenness can be called the dual betweenness or betweenness in the dual space. Conversely, the closeness can be interpreted as a type of structurality computed on the arcs.

To plot a centrality value in contrasted maps, one has to take into account the large distribution of values, but also the large distribution of the element (way or arc) lengths. There is a correlation, as most of the very long ways tend to have the lowest (best) structurality, especially if they have a high connectivity. If no care is taken, plotting the values of the structurality in color results in maps which are homogeneous (Scellato et al., 2006). To avoid this, we classify the centralities such that each class has the same total length, thus giving the same visual signal on the maps. With such care, the reconstructed ways and their structurality produce contrasted maps (see Figure 9).

## 5. Comparison and spatial robustness of centralities

Contrary to the previous local indices, such as the length and connectivity of ways, the main problem with any global measure on a geographical graph is that they should be sensitive to the study area chosen. In other words, they might indicate the center of the selected surface, with just some weighting considering the inhomogeneous densities of the network. A striking illustration of this can be found in Hamaina et al. (2012). For the same topological system, the arc network
<figure><img src="image_12.png" /></figure>

Fig. 10. Histogram of the structuralities of the ways (reconstructed with M0, and a threshold angle of 60°) for Paris. One find a Gaussian for lower (interesting) values, and an exponential tail for high (uninteresting) values.

<figure><img src="image_13.png" /></figure>

Fig. 11. The four map samples used to compare the centralities and explore their stability. Left: the first one (S1) in black is the historical center of Avignon, within the late middle age walls. The next one extend to the modern periphery belt (S2) in grey. Right: it is further extended down to the durance (S3), in black, and then further to the East (S4), in grey.

was replaced by either the minimal spanning tree or the over connected Delaunay triangulation, which connects all the vertices with triangles. Each are very different networks in structure and geometry (except the unchanged vertices), but computation of the centralities shows very similar results, indicating the center of the sample.

To investigate this effect as well as the similarity of the structurality and the betweenness, we compute the closeness (structurality on the arcs), the betweenness (on the arcs), the dual betweenness (on the ways), and the structurality for several map samples around the historical center of Avignon (see Figure 11). Avignon is a good study case because its historical center is located on a side of the map, due to the natural obstacle of the Rhone river.

Several cuts of Avignon road network are studied here (see Figure 11). The results computed on sample S4, but restricted to sample S2, are shown in Figure 12. We apply the same process of drawing ten classes with the same total length for each class (as in Figure 9), to provide a meaningful visual comparison. The four results
<figure><img src="image_14.png" /><figcaption>Fig. 12. Maps of the four centralities restricted on sample S2, after being computed on S4. Upper right: the betweenness computed on the dual space (ways). Upper left: the structurality computed on the ways. Lower left: the betweenness computed on the arcs (normal space). Lower right: the closeness (equivalent to the structurality computed on the arcs). The four results are different, but there are some similarities: the betweenness are very contrasted, with high betweenness being next to a very low one, on a noisy background, while the structuralities, being the result of a mean distance measure, are by nature continuous and more diffuse. In the same time, the betweenness and structurally on the ways reveal some similar underlying structure, with converging axes toward the historical center of Avignon, while the ones computed on the arcs reveal more the peripheral ways. (Color online)</figcaption></figure>

appear clearly different, but common characteristics for indicators computed on the ways (or arcs) can be seen. For a further quantitative comparison, we have to take into account that structurality and closeness give very different results than betweenness (in the dual and normal space). The first is a calculus of a radius on a surface element, so the order of magnitude is $N^{1/2}$, where N is the number of elements in the graphs (arcs or ways). The most central element is the element with minimum radius. The betweenness is the number of minimal paths passing through an element, so its order of magnitude is $N^2$, the number of possible pairs with N elements. The most central element is the element with maximal number. In order to compare these measures in a quantitative way we take the fourth root of the betweenness, thus also of order $N^{1/2}$, and we subtract the structurality from twice its

average S, so that the average remains the same but now the most central element is also the maximum value:

$$B^* = B_{1/4}, \qquad (3)$$

$$S^* = 2S - S \qquad (4)$$
<figure><img src="image_15.png" /><figcaption>Fig. 13. Left: probability density functions of the dual betweenness $B_w^*$ and structurality $S_w^*$ for the map sample S4. The betweenness presents a lower cut-off with a large peak (corresponding to a null value before rescaling), and a tail for higher values compatible with an exponential. The structurality present on the contrary an exponential tail for low values, and a Gaussian (more visible on larger sample as Paris, Figure 10) for higher values. Right: the respective betweenness $B_w^*$ and structurality $S_w^*$ values for the same ways, when ordered by increasing order of $S_w^*$ (corresponding to the inverse of the cumulative probability). It shows no clear correlation. More precisely, there are low values of betweenness for his structurally, and vice-versa.</figcaption></figure>

To further compare all the results (the same measurements on different map samples and different measurements on the same map samples), we normalize all the measures $m^*$ by removing the mean value $m$ and dividing by the standard deviation $\sigma_m$, giving comparable values all centered on 0 with the same standard deviation of 1:

$$m^* = \frac{(\tilde{m} - \bar{m})}{\sigma_m} \qquad (5)$$

If we compare the two measurements on the ways, dual betweenness and structurality, the first result is that they present very different distributions (Figure 13 left). The probability of the structurality $S_w^*$ is a well-defined peaked and spread density with an exponential tail toward small values, and a rather Gaussian tail for high values. The probability of the betweenness $B_w^*$ has a sharp lower cut corresponding to numerous ways having a betweenness value of zero, and a tail compatible with an exponential for larger values. Even with different scaling, there does not seem to be a clear correlation when the values of the structurality are ordered. The values of the betweenness fluctuate without clear tendency: high betweenness corresponds to high as well as low structurality (Figure 13 left).

To get a better idea, one can directly plot the respective values for the same elements. Once again there is not a correlation, both for the ways and the arcs (Figure 14). To quantify this, a Pearson correlation is computed between the two measurements: $C_{B,S} = \overline{S_w^*}(k)B_w^*(k)_k$ (Figure 16 left).

To analyze the stability of a measurement $m$ within a map sample, one can plot the respective values obtained for the elements common in both samples (see Figure 15).
<figure><img src="image_16.png" /><figcaption>Fig. 14. Left: Dual betweenness plotted versus structurality for all the ways of S4. Right: the betweenness plotted versus the closeness for all the arcs of S4. The two clouds do not indicate much correlation, rather for both cases the independence of the two distributions, except for both high values (upper left corner).</figcaption></figure>

The map plots show different results, but with some common features. In particular, the measurements on the ways appear to be much more robust to border changes.

As for comparing different measurements, the robustness of a measurement *m* on the map samples *S*<sub>*i*</sub> and *S*<sub>*j*</sub> (*S*<sub>*i*</sub> being included in *S*<sub>*j*</sub>) can be quantified using the Pearson correlation between the two results, restricted to the common elements of the map samples: *C*<sub>*m*,*i*,*j*</sub> = *m*<sub>*i*</sub>*(*k*)*m*<sub>*j*</sub>*(*k*)*<sub>*k*</sub> (Figure 16 right). The fact that the values for each indicator make a monotonous curve, when drawn as a function of the sample size ratio, indicates that this dominates the sample size effects. The results show that the most stable measurement is the dual betweenness on the ways, followed by the structurality, the betweenness on the arcs, and finally closeness. The closeness shows some negative correlation when the sample size ratio is too large: it flips from indicating the sample center to the periphery belts for larger samples.

These results indicate first that the way is a useful object for analyzing cities. When one looks at the resulting maps (Figure 12), he can see that ways indicate internal radial structures, showing some positive correlations on the high values. On the contrary, these radial structures disappear in the centralities measured on the arcs. Even if the self-correlation curve of the betweenness on the arcs is still high, one can see in the direct plots (Figure 15 lower left) that the rare high betweenness points are diffuse. Betweenness also remains somehow correlated with the closeness. Those observations should lead to caution when using this indicator, and handling its results.

Ways and indicators based on it can also be considered given a calculus efficiency point of view. The computational time of betweenness and structurality indicators differ. The computational complexity of betweenness on the arcs is high: one has to compute the shortest path for each pair of elements, *O*(N<sup>2</sup>), where *N* is the number of arcs. Unfortunately, when the real length along the elements is considered, there is no quick algorithm to find it and one has to explore all the possible ways blindly, with a complexity of *O*(N<sup>2</sup>). This results in a total complexity of *O*(N<sup>4</sup>). On the other hand, when computed
on the ways, betweenness can use a faster algorithm to find the shortest path, topological,
leading to a complexity of only $O(n)$, where $n$ is now

<figure><img src="image_17.png" /><figcaption>Fig. 15. Plots of a measurement for the sample S2 as a function of the same measurement for the sample S4, restricted to the common elements. Up left: dual betweenness computed on the ways $B_w^*$ . Up right:structurality$S_w^*$. Lower left: betweenness computed on the arcs$B_a^*$. Lower right: closeness $C_a^*$. There are common trends for the betweenness, to have the strongest accumulation for an originally zero value, and to remain even after the renormalization closer to small values. On the contrary, the structuralities are more evenly spread, slightly toward to high values. One can also see that the computation on the ways are very stable, focused on the diagonal, while the measurement on the arcs are more diffused, with a cloud for high values for the betweenness, and a global spreading for the closeness.</figcaption></figure>

the number of ways, which is smaller than the number of arcs $N$ (roughly 1/3rd). This leads
to a total complexity of $O(n^3)$. So computed on the ways the betweenness is not only more
robust but much quicker to compute. Finally, the complexity of the structurality is lower.
Because it is just a mean distance measure, it can be computed for each element in $O(n)$,
resulting in a total complexity of $O(n^2)$ (the complexity of the closeness is $O(N^2)$). For
tractable and reasonably stable results, one should thus compute the structurality on the
ways.

6 Robustness in space and time of the ways
The robustness of the centrality indicators computed on the ways might be surprising, because they integrate the effects of all the elements in the chosen map. A first explanation is that the ways are multi-scale spatial elements, ranging from small

<figure><img src="image_18.png" /></figure>

Fig. 16. Left: Pearson correlation between the betweenness and the structurality, computed both on the ways and on the arcs, for the four map samples. They are ordered as a ratio of number of elements to the maximum number of elements (for S4, 2687 ways, and 7771 arcs). Except for the small sample S1, there is only a small correlation between the structurality and the betweenness computed on the ways. When computed on the arcs, there remains a medium correlation between the betweenness and the closeness. This could have been seen in Figure 12. Right: Pearson correlation for the four measurements, for the same indicators but on different size samples. The values are ordered along the ratio of size of the two samples compared, as indicated. The most stable measurement is the dual betweenness on the ways, followed by the structurality, then the betweenness on the arcs, with finally a very unstable closeness.

connections to large distances extending throughout the map. In this case, the centrality of a small way surrounded by large ones does not depend strongly on the rest of the map, beyond these large ways (when normalized). But this particular type of structure comes from the development of the road network in time, similar to crack patterns (Bohn et al., 2005b): the first elements are the longest, and the successive ones are connections between the previous ones. This leads to degree three intersections, which we found are common, even if the roads extend on average over two or three crossings (Figure 1).

In cities, the earliest ways correspond to the connections of small city centers with other surrounding urban centers. The number of city-connecting roads is a good way to deduce the respective age and importance of cities (Watteaux, 2009; Watteaux, 2012). These essential first ways are very stable. This robustness is not necessarily in their particular geographical inscriptions, as they can first wander around a globally fixed itinerary. It is in the preservation of their continuity and local straightness because they are the necessary ways that allow circulation (Watteaux, 2012). As soon as these roads are urbanized (surrounded by houses) their geographical inscription becomes more fixed. Heavy destruction and reconstruction of houses are then necessary to align the streets. This has been a constant process in cities' histories since the renaissance and the discovery of perspective. These city-connecting roads, which by construction cross a whole territory,
are thus very stable. Their dense interconnection, denser than for cracks and closer to a Delaunay triangulation, could explain the supernumerary of long ways (Figure 3).

Following the term of Scellato et al. (2006), we could say that those roads create the backbones around which the space will be divided, first by rural parcels and paths, then by local urban extensions. This corresponds to the creation of numerous little perpendicular roads (Watteaux, 2003). The difference between roads and cracks is that a new road can actually cross an older one, thus creating a degree four intersection. Even if this is the general image we have of a crossing, Figure 1 shows that limiting new roads to connecting close previous ones and not extending through the whole city is not the most common case. This explains why the typical way length (150 m, Figure 3) is just few times the arc length (60 m, Figure 1). These local connections maintain a successive hierarchical division of the space. It is this hierarchical process in time that explains the log-normal distribution of the length of the ways (Figure 3).

The fact that these successively created connections can still be identified by means of the construction of ways also comes from the spatial stability of these elements, in particular of their crossing geometry. This stability is not always present in other hierarchical successive reticulated pattern creation. For instance, in leaf venation patterns, the geometrical angle of the reconnections, even with only degree three connections, are modified by the ongoing surface expansion, and finally converges to an angular equilibrium closer to bubble foam (Bohn et al., 2002). In fact, detailed observations of cities show that the goal of town planners to control the city structure is precisely to modify the geometry of the crossings to impose particular ways continuity and forbid others, like roundabouts (Figure 8).

Reconstructed ways are an indication of a particular spatial history, by their successive hierarchical construction, and the preservation of their spatial geometry in time. They are thus a good indication of a particular developmental pattern in space and time.

This stability can be observed in the most structural elements, as in Paris (Figure 9) or Avignon (Figure 17). For Paris, we indeed see that the most structural part is on the right side of the Seine, where the middle age city first developed after the destruction of the Gallo-Roman city (on the hills of the left bank) (Huard, 2013; Rouleau, 1988). The radiating roads to the surrounding villages are indeed very structural, such as the “route de St Jacques” (path to the Spanish pilgrimage site built in the 15th century), and some oblique historic roads such as “route de Sevre,” “de Vaugirard,” and “de Belleville,” or the road to the West, “route du Faubourg St Honore,” before the 1800’s piercing of “rue de Rivoli” slightly closer to the Seine,’ “du Faubourg Poissoniere” (North, bringing fish from the Channel to Paris), “du Faubourg St Antoine” (East) etc. In Avignon, one can also see the radial structure connecting the city center at the South bottom of the rock, on which Papal palace is built to Lyon, going first East and then North along the left bank of the Rhone, with the road “de la Carreterie” and “route de Lyon,” or to Arles, going south to cross the Durance (on different crossing locations with time) and Aix-en-Provence, South-East along the right bank of the Durance. Beyond these historic access roads, one can also recover the successive belts of protecting walls, like the middle age ones inside the present walls of Avignon, or the several successive ones in Paris, or some of the more modern highway belts around Paris and South of Avignon.
<figure><img src="image_19.png" /><figcaption>Fig. 17. Structuralities of the ways of Large Avignon, ways reconstructed with method 0–60', and structuralities ranked in ten length classes. The upper part is limited by the major river Rhone, on the South by the joining river Durance. On the East, the map has been cut around the South French Highway (A7), just before another natural obstacle of South-North hills.</figcaption></figure>

(Color online)

7. The strucurality of the ways as a mean to read history

It is interesting to see that we can recover historical ways, even when their historical
importance was not transcribed in large boulevards or modern highways. This phenomenon
appears precisely because we use only the geometrical core of the roads, without
considering other characteristics (width and treatment). It is also interesting to see that
modern planning can also be observed, such as most of the highway belts, which usually
fulfill the aim of making the city easier to cross. One example is the case of “Hausmann”,
a type of new road piercing with limited extensions. In Paris, most of them do not appear
to be very structural. For instance, the “Boulevard St Michel” close and parallel to “rue St
Jacques,” is much less structural than this much older one. This is because these road
piercings, even if they have a strong local impact—in the road treatment (much wider), or
offering a nice view on essential buildings (the Opera)—are very limited in length and do
not cross the whole city. Another observation is that many of them, even if long like the
successive internal belts, are regularly cut at large places, creating roundabouts. There is
however a special case when the two structures are coherent, like when the “rue de
Turbigo” diagonally crosses the right bank square pattern, and connect straightaway to
“route de Belleville—an old exit of Paris from “Faubourg du Temple” to the then outside
village of Belleville. In this case, they both reinforce each other to create the most structural
element on the map. Such interactions between old and new structures should be studied
in more detail, as in (Barthelemy et al., 2013), using the stable indicators computed on the
ways.

In terms of structurality, the effect is simple to understand, because the addition of any
element, be it local or cutting through a larger territory, just makes the
<figure><img src="image_20.png" /><figcaption>Fig. 18. Left : Structurality maps of Villers-sur-mer. Right : Google™ map showing present representation. (Color online)</figcaption></figure>

structurality of connected or crossed ways comparatively better. For the betweenness the effect can vary. The new elements can create shortcuts decreasing the betweenness of the surrounding previous elements. Alternatively, it might slightly increase the betweenness of the local elements which shorten the path to get to them (Strano et al., 2012). The asymmetrical cloud in Figure 15 shows that it is the betweenness of elements that are degraded.

The structurality also has some advantages over dual betweenness, because of its more continuous diffuse nature. The dual betweenness will highlight the main important ways, but not the small ways connected to them (Figure 12 upper left). On the other hand, the structurality will highlight the same important ways, but also the ones closely connected to them (Figure 12 upper right). This is interesting from the perspective of the historical development of road patterns. The main ways are indeed the first ones but the small ways around them seem to be next to appear, before the rest of the territory is densified. It is thus interesting to highlight them too. A good example of this process is the small city of Villers-sur-mer on the Channel (Figure 18).

Independent of the present use of the streets (Figure 18 right), the structurality correlates with the history of the city (Figure 18 left). Villers-sur-mer started around a small community around a church, slightly inland and protected at the base of little hills. The main road was then diagonal to the sea reaching the harbor near the intersection of the cliffs and the sea. Between the two, around this diagonal street, houses with small perpendicular streets extended. They still constitute the main structural ways, even if the main road is now along the sea shore and climbing the cliff around the 19th century villas. The fact that the small perpendicular streets are still quite structural, due to their direct connection with the first historical way, reveals precisely their corresponding historical importance.

The diffuse structurality indicator can be checked in other cultural environments, such as in the city of Manaus (Brazil). The reconstruction of the ways and the analysis of their structurality is able to recover the city's historical center, which is globally very structural, the main connection roads, and the successive urbanization, when compared with a historical maps reconstructed by D. Rietz
<figure><img src="image_21.png" /><figcaption>Fig. 19. Manaus city (Brazil) left: structurality map. Right: expansion of the city from 1852 to 2012 (data from D. Rietz). (Color online)</figcaption></figure>

(personal communication, Figure 19). Of course, more detailed studies of the link between
historical development and structurality analysis of the ways are necessary, particularly in
the case of large scale reorganization.

8. Conclusion - discussion

We have shown that the way is a complex multi-scale object with interesting properties. First, it can be reconstructed using only the geometry of the road skeleton and the local information at crossings, allowing for simple and rapid analysis. Despite this simplicity, it reveals many features of the street pattern. We presented many observations, such as the preponderance in the distribution of road angles at crossings of 0° and 90°. This exhibits distinct power laws, the Gaussian distribution of angles inside ways (when normalized by random connections, Figure 2), the asymmetrical log-distribution of arc length, the log-normal distribution of way length with supernumerary long ones (Figure 3), the power law of their connectivity (Figure 7), and the Gaussian-exponential distribution of the structurality measure (Figure 10). All these information on real street networks derived from ways are quantitative benchmarks for any model of street pattern growth (Barthelemy, 2011).

After having specified the best method to reconstruct these ways, we defined a new
centrality indicator computed on the ways, the structurality. Compared with other
measures, such as the betweenness computed on the arcs, or the dual betweenness
computed on the ways, it appears to be a new independent indicator, that is quicker to
compute, easier to analyze, and more revealing.

In general the measures computed on the ways proved to be more significant, because
they revealed more underlying structure (like the radial roads), while the ones computed
on the arcs revealed the map centers or surrounding belts (Figure 12). They appear also to
be more stable with respect to the sample map studied. This is proof of the fundamental
usefulness of the ways.

The construction of the way, and their analysis is based only on the network skeleton. It
thus cannot be directly related to other analysis that emphasized the importance of the road
treatment on the flux they can carry (Banos & Thevenin, 2013; Genre-Grandpierre &
Banos, 2010). Studying the skeleton characteristics reveals what the use of the streets could be. It would be interesting however to compare the result of the indicators computed on the ways to the studies on the fluxes, to see if the treatment of the roads could also be correlated with the importance of the way. A rapid assessment seems to show a correlation, even if some exceptions exist, such as “rue St Honore” in Paris.’

The fact that the indicators based on the ways reveal some very particular and structured networks can be explained by the particular formation of a spatial pattern in time. It shows that the street pattern is essentially a successive hierarchical construction, with first the longest streets appearing and then smaller ones branching from them in successive, nearly local, divisions. The fact that this process is still visible in the present street pattern also shows that the network, and in particular its geometry, has been only slightly modified during its evolution, preserving its hierarchical nature.

This successive growth and this stability should be questioned in view of the users (and planners) of these networks. This particular growth must correspond to the nature of people, gathering successively close to already dense human aggregations. They need access to living space, and thus create new roads, that begin hierarchical growth. The fact that this first growth structure is preserved afterward, like in cracks but not like in leaf veins (Bohn et al., 2002), is in itself meaningful. The first reason could just be the high cost, both economical and social, of reorganizing the street pattern. The second reason could be that the need to do so does not arise. In other words, the structure thus created could be efficient enough and satisfying to the users (Hillier, 2006). Any other type of structure, for instance honey comb patterns as attempted in the 70’s, might not allow this simple and efficient representation, and thus finally are discarded by the users.

Although this deserves to be investigated in more detail in town planning and sociology, this last remark already corresponds to previous findings on the strategy of taxi-drivers (Pailhous, 1970). It was shown that the existence of few very structural ways allowed them to construct rapid and efficient strategies to find simple and short paths from any point to any other. The strategy is just to connect from a departure point to a close well-known structural way, then move with minimal turns, and only at the last moment go into lower structural ways up to approach the destination. This strategy is in fact optimal in terms of simplicity, maximizing the use of the driver’s previous knowledge, and minimizing the search for particular solutions. The simplest path gives an efficient method to compute a good approximation for the shortest path along the network, in a less demanding computational time (Courtat, 2012). Simplest path is simpler than constant reorientation evaluation (Lee & Holme, 2012), if global knowledge of the map is available.

Finally, we see that with only a local rule, computed at each vertex, one can construct an elaborated and multi-scale element to analyze the deep structure of a reticular network (Perna et al., 2011). This can be easily extended to other geometrical networks, such as delta and mangrove water networks, leaf nervation, ceramic cracks, etc. In the case of road networks, the use of the alignment as the criteria to construct the hypergraph is revealed to be very powerful, allowing us to recover both the structure of a city and its history.
Acknowledgements

The research presented here, supported by CNRS-PIRVE (Programme Interdisciplinaire de Recherches Ville-Environment) and by ANR-MN-2012 MoNuMoVi, results from the work of the multidisciplinary research team MORPHOCITY, jointly led by Ph. Bonnin (CNRS-AUS-LAVUE) and S. Douady (CNRS-MSC), composed of P. Bordin (ESTP-Geospective), E. Degouys (PhD student AUS-LAVUE), C.-N. Douady (AUS-LAVUE), J.-P. Frey (CRH-LAVUE), C. Lagesse (PhD student MSC) and P. Vincent (Z-Studio) ; with the participation of T. Courtat (PhD student), Wang X. (PhD student) and M. Watteaux (Post-Doctoral Researcher).

References

Albert, R., & Barabasi, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47–97.

Banos, A., & Thevenin, T. (Eds.) (2013). Geographical information and urban transport systems. Hoboken, NJ: John Wiley & Sons, Inc.

Barthelemy, M. (2011). Spatial networks. Physics Reports, 499, 1–101.

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

Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., & Hwang, D.-U. (2006). Complex networks: Structure and dynamics. Physics Reports-review Section of Physics Letters, 424, 175–308.

Bohn, S., Andreotti, B., Douady, S., Munzinger, J., & Couder, Y. (2002). Constitutive property of the local organization of leaf venation networks. Physical Review E, 65, 061914.

Bohn, S., Douady, S., & Couder, Y. (2005a). Four sided domains in hierarchical space dividing patterns. Physical Review Letters, 94, 054503.

Bohn, S., Pauchard, L., & Couder, Y. (2005b). Hierarchical crack pattern as formed by successive domain divisions. Physical Review E, 71, 046214.

Bordin, P. (2006). M'ethode d'observation multi-niveaux pour le suivi de ph'enom`enes g'eographiques avec un sig. Ph.D. thesis, Universite de Marne-la-Vallée.

Buhl, J., Gautrais, J., Reeves, N., Sole, R. V., Valverde, R. V., Kuntz, P., & Theraulaz, G.´ (2006). Topological patterns in street networks of self-organized urban settlements. European Physical Journal B, 49, 513–522.

Cardillo, A., Scellato, S., Latora, V., & Porta, S. (2006). Structural properties of planar graphs of urban street patterns. Physical Review E, 73, 066107.

Courtat, T. (2012). Walk on city maps. Physical and mathematical phenomenology of the city A geometrical approach. Ph.D. thesis.

Courtat, T., Gloaguen, C., & Douady, S. (2011). Mathematics and morphogenesis of cities : A geometrical approach. Physical Review E, 83, 036106.

Crucitti, P., Latora, V., & Porta, S. (2006). Centrality measures in spatial networks of urban streets. Physical Review E, 73, 036125.

Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40, 35–41.

Genre-Grandpierre, C. (2001). La structure topologique et fonctionnelle des reseaux routiers´urbains comme determinant de la g´eographie des flux de déplacements. Colloque Géopoint. L’explication en géographie, May 2000, Avignon, France. pp. 60–67.
Genre-Grandpierre, C., & Banos, A. (2010). New types of metrics for urban road networks explored with S3: an agent-based simulation platform. volume 325, Q. Bai, & N. Fukuta pp. 267–286. Berlin Heidelberg: Springer.

Genre-Grandpierre, C., & Foltete, J.-C. (2003). Morphologie urbaine et mobilité en marche à pied. Cybergeo: Revue européenne de géographie / European Journal of Geography, 248, 1–22.

Hamaina, R., Leduc, T., & Moreau, G. (2012). Caracterisation des tissus urbains à partir de l’analyse structurelle des reseaux viaires. Cybergeo: European Journal of Geography, 581. doi: 10.4000/cybergeo.25009.

Hillier, B. (2006). Studying Cities to learn about minds; How geometric intuitions shape urban space and make it work. In Holscher, Conroy Dalton, Turner (Eds.), Space syntax and spatial cognition (pp. 11–31).

Hillier, B., Penn, A., Hanson, J., Grajewski, T., & Xu, J. (1993). Natural movement or, configuration and attraction in urban pedestrian movement. Environment and Planning B Planning & Design, 20, 29–66.

Huard, M. (2013). Atlas Historique de Paris. Retrieved from http://paris-atlas-historique.fr.

Jiang, B., & Claramunt, C. (2004). Topological analysis of urban street networks. Environment and Planning B - Planning & Design, 31, 151–162.

Lee, S. H., & Holme, P. (2012). Exploring maps with greedy navigators. Physical Review Letters.

O'Sullivan, D. (2014). Spatial network analysis. In M. M. Fischer, & P. Nijkamp (Eds.), Handbook of regional science. Berlin Heidelberg: Springer.

Pailhous, J. (1970). Représentation de l'espace urbain et cheminements : l'exemple du chauffeur de taxi. Presses Universitaires de France.

Perna, A., Kuntz, P., & Douady, S. (2011). Characterization of spatial networklike patterns from junction geometry. Physical Review E, 83, 066106.

Porta, S., Crucitti, P., & Latora, V. (2006). The network analysis of urban streets: A dual approach. Physical A - Statistical Mechanics and its Applications, 369, 853–866.

Rouleau, B. (1988). Le tracé des rues de Paris : Formation, Typologie, Fonctions. Paris : Editions du centre national de la recherche scientifique. ISBN 2-87682-009-9.

Scellato, S., Cardillo, A., Latora, V., & Porta, S. (2006). The backbone of a city. European Physical Journal B, 50, 221–225.

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

Watteaux, M. (2003). Le plan radio-quadrille des terroirs non planifiés. Etudes Rurales, 3, 187–214.

Watteaux, M. (2009). La dynamique de la planimétrie et des réseaux routiers en Vendée méridionale. Etudes historiographiques et recherches archéogéographiques. Ph.D. thesis, Paris, Université de Paris I - Panthéon-Sorbonne

Watteaux, M. (2012). Archéogéographie des réseaux viaires sud-vendéens : une lecture multiscalaire et diachronique du paysage routier. D. Menjot.