# Structural Properties of Planar Graphs of Urban Street Patterns

Structural Properties of Planar Graphs of Urban Street Patterns

Alessio Cardillo1 , Salvatore Scellato2 , Vito Latora1 and Sergio Porta3

1

Dipartimento di Fisica e Astronomia, Universit` di Catania, and INFN Sezione di Catania, Italy a 2 Scuola Superiore di Catania, Italy and 3 Dipartimento di Progettazione dell’Architettura, Politecnico di Milano, Italy (Dated: February 2, 2008) Recent theoretical and empirical studies have focused on the structural properties of complex relational networks in social, biological and technological systems. Here we study the basic properties of twenty 1-square-mile samples of street patterns of di?erent world cities. Samples are represented by spatial (planar) graphs, i.e. valued graphs de?ned by metric rather than topologic distance and where street intersections are turned into nodes and streets into edges. We study the distribution of nodes in the 2-dimensional plane. We then evaluate the local properties of the graphs by measuring the meshedness coe?cient and counting short cycles ( of three, four and ?ve edges), and the global properties by measuring global e?ciency and cost. As normalization graphs, we consider both minimal spanning trees (MST) and greedy triangulations (GT) induced by the same spatial distribution of nodes. The results indicate that most of the cities have evolved into networks as e?cienct as GT, although their cost is closer to the one of a tree. An analysis based on relative e?ciency and cost is able to characterize di?erent classes of cities. I. INTRODUCTION

arXiv:physics/0510162v1 [physics.soc-ph] 17 Oct 2005

During the last decade, the growing availability of large databases, the increasing computing powers, as well as the development of reliable data analysis tools, have constituted a better machinery to explore the topological properties of several complex networks from the real world [1, 2, 3, 4]. This has allowed to study a large variety of systems as diverse as social, biological and technological. The main outcome of this activity has been to reveal that, despite the inherent di?erences, most of the real networks are characterized by the same topological properties, as for instance relatively small characteristic path lengths and high clustering coe?cients ( the so called small-world property) [5], scale-free degree distributions [6], degree correlations [7], and the presence of motifs [8] and community structures [9]. All such features make real networks radically di?erent from regular lattices and random graphs, the standard topologies usually used in modeling and computer simulations. This has led to a large attention towards the comprehension of the evolution mechanisms that have shaped the topology of a real network, and to the design of new models retaining the most signi?cant properties observed empirically. Spatial networks are a special class of complex networks whose nodes are embedded in a two or three-dimensional Euclidean space and whose edges do not de?ne relations in an abstract space (such as in networks of acquaintances or collaborations between individuals), but are real physical connections [4]. Typical examples include neural networks [10], information/communication networks [11, 12], electric power grids [13] and transportation systems ranging from river [14], to airport [15, 16] and street [17] networks. Most of the works in the literature, with a few relevant exceptions [11, 18, 19], have focused on the characterization of the topological properties of spatial networks, while the spatial aspect has

received less attention, when not neglected at all. However, it is not surprising that the topology of such systems is strongly constrained by their spatial embedding. For instance, there is a cost to pay for the existence of long-range connections in a spatial network, this having important consequences on the possibility to observe a small-world behavior. Moreover, the number of edges that can be connected to a single node is often limited by the scarce availability of physical space, this imposing some constraints on the degree distributions. In few words, spatial networks are di?erent from other complex networks and as such they need to be studied in a di?erent way. In this paper we focus on a particular class of spatial networks: networks of urban street patterns. We consider a database of 1-square mile samples of di?erent world cities and for each city we construct a spatial graph by associating nodes to street intersections and edges to streets. In this way, each of the nodes of the graph is given a location in a 2-dimensional square, and a real number, representing the length of the corresponding street, is associated to each edge. By construction, the resulting graphs are planar graphs, i.e. graphs forming nodes whenever two edges cross. After a previous work on the distribution of centrality measures [20], here we present a comparative study of the basic properties of spatial networks of di?erent city street patterns. In particular we evaluate the characteristics of the graphs both at a global and at a local scale. The main problem with spatial graphs is that, in most of the cases, the random graph or the complete graph are no more a good way to normalize the results. In fact, the common procedure in relational (non-spatial) complex networks is to compare the properties of the original graph derived from the real system with those of some randomized versions of the graph, i.e. of graphs with the same number of nodes and links as the original one, but where the links are distributed at random. This is, for instance, the standard

2 way proposed by Watts and Strogatz in Ref. [5] to assess whether a real system is a small world. One quanti?es the structural properties of the original graph by computing its characteristic path length L and clustering coe?cient C, where L measures the typical separation between two vertices in the graph (a global property), whereas C measures the cliquishness of a typical neighbourhood (a local property). Then, the graph is a small-world if L assume a value close to that obtained for the randomized version of the graph, Lrand, while the value of C is much larger than Crand . Similarly, in the e?ciency-based formalism proposed in Refs. [21, 22], a small-world network is de?ned as a system being extremely e?cient in exchanging information both at a global and at a local scale. Again, the values of global and local e?ciency are compared with those obtained for a randomized version of the graph. A similar method is used in the counting of short cycles or speci?c motifs in a graph representing a real system [8]. The research of the motifs and cycles is based on matching algorithms counting the total number of occurrences of each motif and each cycle in the original graph and in the randomized ones. Then, a motif or a cycle is statistically signi?cant if it appears in the original graph at a number much higher than in the randomized versions of the graph. In a planar graph, as those describing urban street patterns, the randomized version of the graph is not signi?cative because it is almost surely a non-planar graph due to the edge crossings induced by the random rewiring of the edges. Moreover, because of the presence of long-range links, a random graph corresponds to an extremely costly street pattern con?guration, where the cost is de?ned as the sum of street lengths [22]. The alternative is to compare urban street patterns with grid-like structures. Following Ref. [18], we shall consider both minimum spanning trees and greedy triangulations induced by the real distribution of nodes in the square. Spanning trees are the planar graphs with the minimum number of links in order to assure connectedness, while greedy triangulations are graphs with the maximum number of links compatible with the planarity. Spanning trees and greedy triangulations will serve as the two extreme cases to normalize the structural measures we are going to compute. for the city of Savannah: in the upper-left panel we report the original map, and in upper-right panel the obtained graph. N is the set of N nodes representing street intersections and characterized by their positions {xi , yi }i=1,...,N in the square. L is the set of K links representing streets. The links follow the footprints of real streets and are associated a set of real positive numbers representing the street lengths, {lk }k=1,...,K . The graph is then described by the adjacency N × N matrix A, whose entry aij is equal to 1 when there is an edge between i and j and 0 otherwise, and by a N × N matrix L, whose entry lij is equal to the length of the street connecting node i and node j. In this way both the topology and the geography (metric distances) of the system will be taken into account. A list of the considered cities is reported in table I, together with the basic properties of the derived graphs. The considered cases exhibit striking di?erences in terms of cultural, social, economic, religious and geographic context. In particular, they can be roughly divided into two large classes: 1) patterns grown throughout a largely self-organized, ?ne-grained historical process, out of the control of any central agency; 2) patterns realized over a short period of time as the result of a single plan, and usually exhibiting a regular grid-like, structure. Ahmedabad, Cairo and Venice are the most representative examples of self-organized patterns, while Los Angeles, Richmond, and San Francisco are typical examples of mostly-planned patterns. We have selected two di?erent parts of the city of Irvine, CA, (named Irvine 1 and Irvine 2) for two highly diverse kinds of urban fabrics: the ?rst is a sample of an industrial area showing enormous blocks with few intersections while the second is a typical residential early sixties “lollipop” low density suburb based on a tree-like layout with a lot of deadend streets. The di?erences between cities are already evident from the basic properties of the derived graphs. In fact, the number of nodes N , the number of links K, and the cost of the wiring, de?ned as the sum of street lenghts: Cost =

i,j

aij lij

(1)

II.

NETWORKS OF URBAN STREET PATTERNS

The database we have studied consists of twenty 1square mile samples of di?erent world cities, selected from the book by Allan Jacobs [23]. We have imported the twenty maps into a GIS (Geographic Information System) environment and constructed the correspondent spatial graphs of street networks by using a road-centerline-between-nodes format [24]. Namely, each urban street pattern is trasformed into a undirected, valued (weighted) graph G = (N , L), embedded in the 2dimensional unit square. In Fig. 1 we show the case

and measured in meters, assume widely di?erent values, notwithstanding the fact we have considered the same amount of land. Notice that Ahmedabad has 2870 street intersections and 4387 streets in a surface of 1-square mile, while Irvine has only 32 intersections and 37 streets. Ahmedabad and Cairo are the cities with the largest cost, while the cost is very small (less than 40000 meters) in Barcelona, Brasilia, Irvine, Los Angeles, New Delhi, New York, San Francisco, Washington and Walnut Creek. A large di?erence is also present in the average edge (street) length l , that assumes the smallest values in cities as Ahmedabad, Cairo and Venice, and the largest value in San Francisco, Brasilia, Walnut Creek and Los Angeles. In Ref. [20] we have studied the edges length distribution P (l) for the two di?erent classes of cities, showing that self-organized cities show single peak distributions, while

3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 CITY Ahmedabad Barcelona Bologna Brasilia Cairo Irvine 1 Irvine 2 Los Angeles London New Delhi New York Paris Richmond Savannah Seoul San Francisco Venice Vienna Washington Walnut Creek N 2870 210 541 179 1496 32 217 240 488 252 248 335 697 584 869 169 1840 467 192 169 K 4387 323 773 230 2255 36 227 340 730 334 419 494 1086 958 1307 271 2407 692 303 197 Cost 121037 36179 51219 30910 84395 11234 28473 38716 52800 32281 36172 44109 62608 62050 68121 38187 75219 49935 36342 25131 l 27.59 112.01 66.26 134.39 37.47 312.07 128.26 113.87 72.33 96.56 86.33 89.29 57.65 64.77 52.12 140.91 31.25 72.16 119.94 127.57 Dbox 1.92 1.99 1.95 1.83 1.82 – 1.81 1.90 1.94 1.85 1.72 1.88 1.78 1.85 1.87 1.90 1.81 1.88 1.93 1.80

TABLE I: Basic properties of the planar graphs obtained from the twenty city samples considered. N is the number of nodes, K is the number of edges, Cost and l are respectively the total length of edges and the average edge length (both expressed in meters), Dbox is the box-counting fractal dimension.

mostly planned cities exhibit a multimodal distribution, due to their grid pattern. We now have gone deeper into the characterization of the distributions of nodes (street intersections) in the unit square: we have calculated the fractal dimension of the distributions, by using the box counting method [25]. In all the samples, except Irvine 1 that is too small to draw any conclusion, we have found that the nodes are distributed on a fractal support with a fractal dimension ranging from 1.7 to 2.0. This result is similar to that obtained by Yook et al. for the spatial distribution of the nodes of the Internet, considered both at the level of routers and at the level of autonomous systems [11].

A.

Minimum Spanning Tree (MST) and Greedy Triangulation (GT)

Planar graphs are those graphs forming vertices whenever two edges cross, whereas non-planar graphs can have edge crossings that do not form vertices [26]. The graphs representing urban street patterns are, by construction, planar, and we will then compare their structural properties with those of minimally connected and maximally connected planar graphs. In particular, following Buhl et al. [18], we consider the Minimum Spanning Tree (MST) and the Greedy Triangulation (GT) induced by the distribution of nodes (representing street intersections) in the square. The Minimum Spanning Tree (MST) is the shortest tree which connects every nodes into a single connected component. By de?nition

the MST is an acyclic graph that contains Kmin = N ? 1 links. This is the minimum number of links in order to have all the nodes belonging to a single connected component [26]. At the other extreme, the maximum number of links, Kmax , that can be accomodated in a planar graph with N nodes (without breaking the planarity) is equal to Kmax = 3N ? 6 [27]. The natural reference graph should be then the Minimum Weight Triangulation (MWT), which is the planar graph with the highest number of edges Kmax , and that minimize the total length. Since no polynomial time algorithm is known to compute the MWT, we thus consider the Greedy Triangulation (GT), that is based on connecting couples of nodes in ascending order of their distance provided that no edge crossing is introduced [28]. The GT is easily computable and leads to a maximal connected planar graph, while minimizing as far as possible the total length of edges considered. To construct both the MST and the GT induced by the spatial distribution of points (nodes) {xi , yi }i=1,...,N in the unit square, we have ?rst sorted out all the couples of nodes, representing all the possible edges of a complete graph, by ascending order of their length. Notice that the length of the edge connecting node i and node j is here taken to be equal to the Euclidean distance dEucl = (xi ? xj )2 + (yi ? yj )2 . Then, to compute the ij MST we have used the Kruskal algorithm [29, 30]. The algorithm consists in browsing the ordered list, starting from the shortest edge and progressing toward the longer ones. Each edge of the list is added if and only if the graph obtained after the edge insertion is still a forest or it is a tree. A forest is a disconnected graph in which any two elements are connected by at most one path, i.e., a disconnected ensemble of trees. (In practice, one checks whether the two end-nodes of the edge are belonging or not to the same component). With this procedure, the graph obtained after all the links of the ordered list are considered is the MST. In fact, when the last link is included in the graph, the forest reduces to a single tree. Since in the Kruskal algorithm an edge producing a crossing would also produce a cycle, following this procedure prevents for creating edge crossings. To compute the GT we have constructed a brute force algorithm based on some particular characteristics of planar GT [28]. The algorithm consists in browsing the ordered list of edges in ascending order of length, and checking for each edge whether adding it produces any intersections with any other edge already added. For each of the twenty cities we have constructed the respective MST and GT. These two bounds make also sense as regards as the possible evolution of a city: the most primitive forms are close to trees, while more complex forms involve the presence of cycles. We can then compare the structural properties of the orginal graphs representing the city with those of the two limiting cases represented by MST and GT. As an example in Fig. 1 in the bottom-left and in the bottom-right panel we report respectively the MST and the GT obtained for the city

4 of Savannah.

<k> 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

P(k=5)

P(k=4)

P(k=3)

P(k=2)

P(k=1)

0.6 0.4 0.2 0 0.08 0.04 0 0.6 0.4 0.2 0 0.6 0.4 0.2 0 0.08 0.04 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

FIG. 2: Average degree k and probability of having nodes with degree respectively equal to 1, 2, 3, 4, and 5 for the twenty city considered. The cities are labeled from 1 to 20 as reported in Table I. The degree distribution P (k) is de?ned as P (k) = N (k)/N , where N (k) is the number of nodes having degree k. FIG. 1: The urban pattern of Savannah as it appears in the original map (top-left), and reduced into a spatial graph (topright). We also report the corresponding MST (bottom-left) and GT (bottom-right).

B.

Graph local properties

The degree of a node is the number of its direct connections to other nodes. In terms of the adjacency matrix, the degree ki of node i is de?ned as ki = j=1,N aij . In many real networks, the degree distribution P (k), de?ned as the probability that a node chosen uniformly at random has degree k or, equivalently, as the fraction of nodes in the graph having degree k, signi?cantly deviates from the Poisson distribution expected for a random graph and exhibits a power law (scale-free) tail with an exponent γ taking a value between 2 and 3 [1, 2, 4]. As already mentioned in the introduction, we do not expect to ?nd scale-free degree distributions in planar networks because the node degree is limited by the spatial embedding. In particular, in the networks of urban street patterns considered, it is very unprobable to ?nd an intersection with more than 5 or 6 streets. In Fig. 2 we report the average degree k , and the degree distribution P (k) for k going from 1 to 5. The cities are labeled with an index going from 1 to 20, the same index we have used in Table I. In all the samples considered, the largest number of nodes have a degree equal to 3 or 4. Self-organized cities as Ahmedabad, Bologna, Cairo and Venice have P (k = 3) > P (k = 4), while the inverse is true for most of the single-planned cities as New York, San Francisco and Washington, because of their squaregrid structure. It is not the aim of this article to discuss the meaning of such di?erences in terms of their possible

impacts on crucial factors for urban life, such as pedestrian movement, way?nding, land-uses or other cognitive or behavioural matters. However, it is worth noting that, for instance, 3-arms and 4-arms street junctions are expected to perform very di?erently in human orienteering within an urban complex system due to the di?erences in the angle widths involved in each turn [31, 32]. It is also interesting to notice the signi?cative frequency of nodes with degree 1 in cities as Irvine and Walnut Creek. Such nodes correspond to the dead-end cul-de-sac streets typical of the suburban early Sixties “lollipop” layouts, which in turn leads to highly debated topics in the current discussion about safety and liveability of modern street patterns as opposite to more traditional ones [33, 34]. Many complex networks show the presence of a large number of short cycles or speci?c motifs [1, 2, 4]. For instance, the so called local clustering, also known as transitivity, is a typical property of acquaintance networks, where two individuals with a common friend are likely to know each other [9]. The degree of clustering is usually quanti?ed by the calculation of the clustering coe?cient C, introduced in Ref. [5], that is a measure of the fraction of triangles present in the network. Such a quantity is not suited to characterize the local properties of a planar graph, since by a simple counting of the number of triangles present in the graph it is not possible to discriminate between di?erent topologies. For instance, there are cases as diverse as trees, square-meshes and honey-comb meshes, all having the same clustering coe?cient equal to zero. Buhl et al. have proposed a more general measure of the structure of cycles (not restricted to cycles of length 3) in planar graphs, the so called meshedness coe?cient M [18]. The meshedness coe?cient is de?ned as M = F/Fmax , where F is the number of faces (excluding the external ones) associated with a planar graph with N

5

CITY Ahmedabad Barcelona Bologna Brasilia Cairo Irvine 1 Irvine 2 Los Angeles London New Delhi New York Paris Richmond Savannah Seoul San Francisco Venice Vienna Washington Walnut Creek

GT GT GT M C3 /C3 C4 /C4 C5 /C5 0.262 0.023 0.042 0.020 0.275 0.019 0.101 0.019 0.214 0.015 0.048 0.013 0.147 0.029 0.027 0.012 0.253 0.020 0.043 0.019 0.085 0.035 0.022 0.005 0.014 0.007 0.004 0.001 0.211 0.002 0.075 0.011 0.249 0.011 0.060 0.020 0.154 0.011 0.020 0.011 0.348 0.024 0.136 0.028 0.241 0.028 0.063 0.016 0.279 0.034 0.068 0.022 0.322 0.002 0.111 0.026 0.253 0.021 0.051 0.021 0.309 0.003 0.148 0.003 0.152 0.016 0.030 0.010 0.242 0.007 0.063 0.018 0.293 0.026 0.132 0.022 0.084 0.000 0.011 0.003

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

TABLE II: Local properties of the graphs of urban street patterns. We report the meshedness coe?cient M [18], and the number Ck of cycles of length k = 3, 4, 5 normalized to the GT number of cycles in the GT, Ck .

centrality ?ows over the network, the former exhibiting power-laws distributions while the latter single-scale exponential distributions [20]. In most of the samples we GT have found a rather small value of C3 /C3 (as comGT pared, for instance, to C4 /C4 ), denoting that triangles are not common in urban city patterns. This is another proof that the clustering coe?cient C alone is not a good measure to characterize the local properties of such networks. Walnut Creek, Los Angeles and SaGT vannah are the city with the smallest value of C3 /C3 , while Irvine1, Richmond, Brasilia and Paris are the cities GT with the largest value of C3 /C3 . In 17 samples out of GT GT 20 we have found C4 /C4 > C3 /C3 : Brasilia, Irvine 1 and Irvine 2 are the only cities having a prevalence of triangles with respect to squares. San Francisco, New York, Washinghton, Savannah and Barcelona are the cities with GT the largest value of C4 /C4 (larger than 0.1). Finally, GT concerning C5 /C5 , we have found three classes of cities. Samples such as Ahmedabad, Cairo, Seul and Venice havGT GT ing C3 /C3 ? C5 /C5 . Samples such as Brasilia, Irvine GT GT and Paris with C3 /C3 > C5 /C5 , and samples as Los GT GT Angeles, Savannah and Vienna with C3 /C3 < C5 /C5 .

C. Graph global properties

nodes and K edges, and expressed by the Euler formula in terms of number of nodes and edges as: F = K ?N +1. Fmax is the maximum possible number of faces that is obtained in the maximally connected planar graph i.e. in a graph with N nodes and Kmax = 3N ? 6 edges. Thus Fmax = 2N ? 5 and the meshedness coe?cient can vary from zero (tree structure) to one (maximally connected planar graph, as in the GT [35]). Here, we have evaluated the meshedness coe?cient M for each of the twenty cities. In addition, we have counted the cycles of length three, four and ?ve by using the properties of powers of the adjacency matrix A. E.g., the number of cycles of length three is simply equal to 1/6Tr(A3 ) [36]. We have denoted by Ck the number GT of cycles of length k in a given city, and by Ck the same number in the corresponding GT. The results are reported in Table II. Three are the cities with a value of meshedness larger than 0.3: New York, Savannah and San Francisco. These represents the most complex forms of cities. On the other hand, Irvine and Walnut Creek with a value of M lower than 0.1, have a tree-like structure. Notice that both the ?rst and the second group of cities are examples of planned urban fabrics. On the other hand, organic patterns such as Ahmedabad, Cairo and Seoul also exhibit high values of mashedness, which means a considerable potential of local clustering. Thus, beside the suburban “lollipop” layout, both grid planned and organic self-organized patterns do show good local performances in terms of the local structural properties of the network: this is even more interesting if coupled with our previous ?nding that such two classes of patterns perform radically di?erent in terms of how

One of the possible mechanisms ruling the growth of an urban systems is the achievement of e?cient pedestrian and vehicular movements on a global scale. This has important consequences on a number of relevant factors a?ecting the economic, environmental and social performances of cities, ranging from accessibility to microcriminality and land-uses [37]. The global e?ciency of an urban pattern in exchanging goods, people and ideas should be considered a reference when the capacity of that city to support its internal relational potential is questioned. It is especially important to develop a measure that allows the comparison between cases of di?erent form and size, which poses a problem of normalization [38]. The global structural properties of a graph can be evaluated by the analysis of the shortest paths between all pairs of nodes. In a relational (unweighted) network the shortest path length between two nodes i and j is the minimum number of edges to traverse to go from i to j. In a spatial (weigthed) graph, instead we de?ne the shortest path length dij as the smallest sum of the edge lengths throughout all the possible paths in the graph from i to j [21, 22]. In this way, both the topology and the geography of the system is taken into account. As a measure of the e?ciency in the communication between the nodes of a spatial graph, we use the so called global e?ciency E, a measure de?ned in Ref. [21] as: E= 1 N (N ? 1) dEucl ij dij (2)

i,j,i=j

Here, dEucl is the distance between nodes i and j along a ij straight line, de?ned in Section II A, and we have adopted

6

CITY Ahmedabad Barcelona Bologna Brasilia Cairo Irvine 1 Irvine 2 Los Angeles London New Delhi New York Paris Richmond Savannah Seoul San Francisco Venice Vienna Washington Walnut Creek E 0.818 0.814 0.799 0.695 0.809 0.755 0.374 0.782 0.803 0.766 0.835 0.838 0.800 0.793 0.814 0.792 0.673 0.811 0.837 0.688 E M ST 0.351 0.452 0.473 0.503 0.385 0.604 0.533 0.460 0.475 0.490 0.433 0.473 0.502 0.341 0.444 0.448 0.386 0.423 0.452 0.481 E GT 0.944 0.930 0.936 0.931 0.943 0.943 0.932 0.930 0.936 0.930 0.931 0.938 0.939 0.922 0.941 0.893 0.943 0.937 0.930 0.938

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

thus de?ne a normalized cost measure, Costrel , as: Cost ? CostMST CostGT ? CostMST

Costrel =

(4)

By de?nition the MST has a relative cost Costrel = 0, while GT has Costrel = 1. In Fig. 3 we plot for each city Erel as a function of Costrel . The cities can be a-priori

0.9 0.8 0.7 0.6

Erel

0.5 0.4 0.3 0.2 0.1 0 0.1 0.15 0.2

TABLE III: The e?ciency E of each city is compared to the minimum and maximum values of the e?ciency obtained respectively for the MST and the GT. The cities are labeled from 1 to 20 as in Table I

Medieval (arabics and european) Grid-iron Modernist Baroque Mixed Lollipop

0.25 0.3 0.35 0.4

Costrel

FIG. 3: Relation beetween relative cost, Crel , and relative e?ciency, Erel . Each point in the plot represent a city. The point of coordinates (0,0) would correspond to the cost/e?ciency of the MST while the point (1,1) would correspond to the GT network. Irvine 2, having coordinates (0.175,-0.398), i.e. a negative value of relative e?ciency, has been plotted instead as having coordinates (0.175,0).

a normalization recently proposed for geographic networks [39]. Such a normalization captures to which extent the connecting route between i and j deviates from the virtual straight line. In Table III we report the values of e?ciency obtained for each city and for the respective MST and the GT. The values of E MST and E GT serve to normalize the results, being respectively the minimum and the maximum value of e?ciency that can be obtained in a planar graph having the same number of nodes as in the original graph of the city. Notice that Irvine 2 is the only case in which E < E MST . This is simply due to the fact that Irvine 2 is the only city whose corresponding graph is not connected. Consequently, the MST has a smaller number of edges but a higher value of e?ciency because it is, by de?nition, a connected graph. The main result is that the cities considered, despite their inherent di?erences, achieve a relatively high value of e?ciency, which is in most of the cases about 80% of the maximum value of the e?ciency in a planar graph, E GT . Following Ref. [18] we de?ne the relative e?ciency Erel as: Erel = E ? E MST E GT ? E MST (3)

Of course, the counterpart of an increase in e?ciency is an increase in the cost of construction, i.e. an increase in the number and length of the edges. The cost of construction can be quanti?ed by using the measure Cost de?ned in formula (1). Given a set of N nodes, the shortest (minimal cost) planar graph that connects all nodes correspons to the MST, while a good approximation for the maximum cost planar graph is given by the GT. We

divided into di?erent classes: 1) medieval fabrics, including both arabic (Ahmedabad and Cairo) and european (Bologna, London, Venice, and Vienna); 2) grid-iron fabrics (Barcelona, Los Angeles, New York, Richmond, Savannah and San Francisco); 3) modernist fabrics (Brasilia and Irvine 1); 4) baroque fabrics (New Delhi and Washington); 5) mixed fabrics (Paris and Seoul); 6) “lollipop” layouts (Irvine 2 and Walnut Creek). We shall see that the plot Erel vs. Crel has a certain capacity to characterize the di?erent classes of cities listed above. The plot indicates an overall increasing behavior of Erel as function of Costrel , with a saturation at Erel ? 0.8 for values of Costrel > 0.3. Grid-iron patterns exhibit a high value of relative e?ciency, about 70 ? 80% of the e?ciency of the GT, with a relative cost which goes from 0.24 to 0.4. The three grid-iron cities (New York, Savannah and San Francisco) with the largest value of e?ciency, Erel ? 0.8, have respectively a cost equal to 0.342, 0.354 and 0.383. Medieval patterns have in general a lower cost and e?ciency than grid-iron patterns althouh, in some cases as Ahmedabad and Cairo (the two medieval cities with the largest e?ciency), they can also reach a value of Erel ? 0.8 with a smaller cost equal to 0.29. Modernist and “lollipop” layouts are those with the smallest value of Cost but also with the smallest value of e?ciency.

7

III. CONCLUSIONS

We have proposed a method to characterize both the local and the global properties of spatial graphs representing urban street patterns. Our results show that a comparative analysis on the structure of di?erent world cities is possible by the introduction of two limiting auxiliary graphs, the MST and the GT, A certain level of

structural similarities across cities as well as some di?erence are well captured by counting cycles and by measuring normalized e?ciency and cost of the graphs. The method can be applied to other planar graphs of di?erent nature, as highway or railway networks. Acknowledgment. We thank J. Buhl, P. Crucitti, R.V. Sol? and S. Valverde, for many helpful discussions e and suggestions.

[1] R. Albert and A.-L. Barab?si, Rev. Mod. Phys. 74, 47 a (2002). [2] M.E.J. Newman, SIAM Review 45, 167 (2003). [3] R. Pastor-Satorras, A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, (Cambridge University Press, 2004). [4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.U. Hwang, Phys. Rep. in press. [5] D.J. Watts and S.H. Strogatz, Nature 393, 440 (1998). [6] A.-L. Barab?si and R. Albert, Science 286, 509 (1999). a [7] R. Pastor-Satorras, A. V?zquez, and A. Vespignani, a Phys. Rev. Lett. 87, 258701 (2001). [8] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashan, D. Chklovskii, and U. Alon, Science 298, 824 (2002). [9] S. Wasserman and K. Faust, Social Networks Analysis, (Cambridge University Press, Cambridge, 1994). [10] O. Sporns, Complexity 8, 56 (2003). [11] S.-H. Yook, H. Jeong, and A.-L. Barab?si, Proc. Natl. a Acad. Sci. U.S.A. 99, 13382 (2002). [12] V. Latora and M. Marchiori, Phys. Rev. E71, 015103(R) (2005). [13] R. Kinney, P. Crucitti, R. Albert and V. Latora, Eur. Phys. J. B46, 101 (2005). [14] F. Pitts, The Professional Geographer 17, 15 (1965). [15] R. Guimer` , S. Mossa, A. Turtschi, and L.A.N. Amaral, a Proc. Natl. Acad. Sci. USA 102 7794 (2005). [16] A. Barrat, M. Barth?lemy, R. Pastor-Satorras and A. e Vespignani. Proc. Natl. Acad. Sci. USA 101, 3747 (2004). [17] S. Porta, P. Crucitti and V. Latora, Preprint physics/0506009. In Press in Environment and Planning B [18] J. Buhl, J. Gautrais, R.V. Sol?, P. Kuntz, S. Valverde, e J.L. Deneubourg, and G. Theraulaz, Eur. Phys. J. B42, 123 (2004). [19] M. T. Gastner and M. E. J. Newman, cond-mat/0407680. [20] P. Crucitti, V. Latora and S. Porta, Preprint physics/0504163. [21] V. Latora and M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001). [22] V. Latora and M. Marchiori, Eur. Phys. J. B32, 249 (2003). [23] A. Jacobs, Great streets (MIT Press, Boston, MA, 1993). [24] N. Dalton, J. Peponis and R. Dalton, To tame a tiger one has to know its nature: extending weighted angular inte-

[25]

[26] [27] [28] [29]

[30] [31] [32] [33]

[34] [35]

[36] [37] [38] [39]

gration analysis to the description of GIS road-centerline data for large scale urban analysis, Proceedings of the 4th International Space Syntax Symposium, London, UK 2003. S. H. Strogatz, Nonlinear dynamics and chaos with applications to phsyics, biology, chemistry and engineering (Perseus, 1994). D.B. West, Introduction to Graph Theory, (Prentice Hall, 1995). B. Bollob?s, Modern Graph Theory (Graduate Texts in a Mathematics, Springer-Verlag, New York, 1998). M.T. Dikerson, R.L.S. Drysdale, S.A. McElfresh, E.Welzl, Computational Geometry 8, 67 (1997) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms (MIT University Press, Cambrdige, 2001). J. B. Kruskal, Proc. Amer. Math. Soc. 2, 48 (1956). R. Dalton, Environment and Behavior 35 107 (2003). B. Hillier and I. Shinichi, paper presented at COSIT 2005, Conference On Spatial Information Theory, Sept. 14-18, Ellicottville, New York. M. Southworth and E. Ben-Joseph, Streets and the shaping of town and cities, (Island Press, Washington D.C., 2003). S. Marshall 2004, Streets and Patterns, (Routledge, London, UK, 2004). In the computed GT, the graphs we have obtained have less than 3N ?6 edges. This is due to the fact that we have considered all the edges as being straight-lines connecting the two end-nodes. For such a reason some of edges connecting the external nodes (the nodes on the border of the unit square) cannot be placed without causing edge crossings. However, the number of these edges is of the √ order of N , so that in large GT graphs the meshedness is close to 1. N. Alon, R. Yuster and U. Zwick, Algorithmica 17, 209 (1997). A. Penn, Environment and Behavior, 35, 30 (2003). J.A. Teklemburg, H.J. Timmermans and A.F. Van Wagemberg, Environment and Planning B20 347 (1993). I. Vragovic, E. Louis, A. Diaz-Guilera, Phys. Rev. E71, 036122 (2005).