Nov 9, 2005 - (Dated: February 2, 2008). We study centrality in urban street patterns of different world cities represented as networks in geographical space. The results indicate that a spatial analysis based on a set of four centrality indices allo
Jun 17, 2017 - them, making agents who serve as intermediaries on the most paths connecting other agents most central. Or, the ... In particular, we first note that standard centrality measures can be written as functions of what we call .... social
Sep 23, 2008 - newleftblogs.blogspot.com, D michellemalkin.com, R presidentboxer.blogspot.com, R. 10Â° atrios.blogspot.com, D truthlaidbear.com, R corrente.blogspot.com, D. TABLE III: Top Ten of the network of political blogs according to PR, Î±EV, a
Nov 23, 2011 - network transport typically happens on all length-scales, from transport to nearest neighbors to the farthest reaches of the network. ... these networks are the result of evolutionary processes, it is important to understand ..... and
Nov 23, 2011 - social network inferred from cell-phone trace logs (â¼ 5.5 Ã 106 nodes and â¼ 2.7 Ã 107 edges). Fi- nally, we apply these .... ness type quantities to quantify congestion in Internet- like graphs include Refs [44, 45]. ...... pairs
May 25, 2006 - In this paper, we empirically investigate correlations among four centrality measures, originated from the social science, ... works from which many mathematical results for general structural characteristics have ... in the understand
Jan 26, 2016 - PDPM Indian Institute of Information Technology,. Design & Manufacturing Jabalpur, ... information to the whole network more easily than the rest of the nodes with low centrality measures, they are .... authors compared three global ce
Sep 21, 2016 - into a supra-centrality matrix of size NT Ã NT whose dominant eigenvector gives the centrality of each node i at each ... Victor Preciado, Feng Shi, Gilbert Strang, Blair Sullivan, and Simi Wang for helpful discussions ... a solution
Jan 26, 2016 - authors compared three global centrality measures: degree, betweenness and random walk ... order to compare with the proposed strategies. 1. Degree .... Input Graph/Network G(V,E), Community Structure of the network with community list
Jan 24, 2018 - show the power and exibility of the proposed framework. CCS CONCEPTS. â¢Mathematics of ... interests in utilities, waste management, industrial manufacturing, chemicals, bio-engineering, weapons, ..... identity matrix, which has nonne
Jul 28, 2017 - and thus have become a prevalent tool for the representation of systems across various scientific domains. However, as ... include the celebrated page-rank algorithm , employed in the search of relevant sites on the web; the detect
Oct 11, 2018 - Many measures based on the network topology have emerged over the .... Experiments have been performed using SIR simulations on Facebook friendship ..... the infected nodes turn into recovered nodes with the recover ...
Jan 21, 2012 - Using data from 92 indices of stock exchanges worldwide, I analize the cluster formation and evolution from 2007 to 2010, which includes the Subprime .... Chile joins the American cluster, and Luxembourg, Hungary, Estonia, Lithuania, R
Apr 16, 2018 - To be more precise, consider a graph G with adjacency matrix A. We say G is walk-regular if for each â â¥ 0, ... The entry in the ith row and jth column of A is denoted Aij. ..... Let graph G have walk matrix W and adjacency matrix
May 14, 2013 - also have the same degree, eigenvector, closeness, and betweenness centralities. We provide a counterexample for the latter two centrality ...
Jan 23, 2015 - in this paper is the one of direct exposures between financial institutions, which include credit ... networks or equivalently by a network where several different types of links can coexist between two ... 2 Data description. Our anal
cific types of relations (e.g., financial exchange, trade, friends, and Web links). A link between any two nodes exists, if a relationship between those nodes ..... Borgatti, S., Centrality and AIDS. Connections, 1995. 18(1): p. 112-114. 7. Bonacich,
Jul 5, 2017 - centrality measure to this effect, which quantifies the fraction of the total information flow of the network ..... negative edge weights and let Î³ be a loop on G. Then. 0 â¤ c(Î³) â¤ 1. Proof. ..... âForestry and loggingâ, âFi
analysis tool, commonly used in many application environments to retrieve ... model, one can generate networks with diminished size, but with the same ...
Apr 19, 2013 - in the distribution network or even a small short-circuit) that propagates its effects to its direct ... (whose removal causes most damage to the grid) and find out how much capacity is required at each node so .... the traditional bet
advantages over graph-theoretic measures like degree, betweeness, and closeness; they can be used in signed and valued graphs . Extension of local measure to also include these types of graphs is in progress. However, the calculation of these meas
Jan 3, 2015 - if the people you know are themselves influential. Eigen- ... over all nodes. Here Aij is an element of the adjacency matrix A of the network having value one if there is an edge between nodes i and j and zero otherwise. Defin- ing a ve
Apr 19, 2013 - node vulnerability in the context of power grids, by considering not only ..... and agreed upon the use of distributed renewable energy sources ...
Jul 27, 2010 - a social network (SocNet) inferred from mobile phone trace-logs  ..... as RG, roadways, etc., Î²l â¼ ld, where d is the embedding dimension ...
CENTRALITY MEASURES IN URBAN NETWORKS a
PAOLO CRUCITTI , VITO LATORA , SERGIO PORTA a Scuola Superiore di Catania, Italy b Dipartimento di Fisica e Astronomia, Università di Catania, and INFN Sezione di Catania, Italy c Dipartimento di Progettazione dell’Architettura, Politecnico di Milano, Italy
Centrality has revealed crucial for understanding the structural order of complex relational networks. Centrality is also relevant for various spatial factors affecting human life and behaviors in cities. We present a comprehensive study of centrality distributions over geographic networks of urban streets. Four different measures of centrality, namely closeness, betweenness, straightness and information, are compared over eighteen 1-square-mile samples of different world cities. Samples are represented by primal geographic graphs, i.e. valued graphs defined by metric rather than topologic distance where intersections are turned into nodes and streets into edges. The spatial behavior of centrality indexes over the networks is investigated graphically by means of colour-coded maps. The results indicate that a spatial analysis, that we term Multiple Centrality Assessment, grounded not on a single but on a set of different centrality indices, allows an extended comprehension of the city structure, nicely capturing the “skeleton” of most central routes and sub-areas that so much impacts on spatial cognition and collective behaviours. Statistically, closeness, straightness and betweenness turn out to follow the same functional distribution in all cases, despite the extreme diversity of the considered cities. Conversely, information is found to be exponential in planned cities and to follow a power law scaling in self-organized cities. A hierarchical clustering analysis based on the Gini coefficients of the different centrality distributions reveals a certain capacity to characterize classes of cities.
The science of networks has been witnessing a rapid development in recent years: the metaphor of the network, with all the power of its mathematical devices, has been applied to complex, self-organized systems as diverse as social, biological, technological and economic, leading to the achievement of several unexpected results [1,2,3]. In particular, the issue of centrality in networks has remained pivotal, since its introduction in a part of the studies of humanities named structural sociology . The idea of centrality was first applied to human communication by Bavelas  who was interested in the characterization of the communication in small groups of people and assumed a relation between structural centrality and influence/power in group processes. Since then, various measures of structural centrality have been proposed over the years to quantify the importance of an individual in a social network . Currently, centrality is a fundamental concept in network analysis though with a different purpose: while in the past the role and identity of central nodes were investigated, now the emphasis is more shifted to the distribution of centrality values through all nodes. Centrality, as such, is treated like a shared resource of the network community – like wealth in nations – with the focus being on the homogeneity/heterogeneity of distributions . In urban planning and design, as well as in economic geography, centrality – though under different terms like accessibility, integration, transport cost or effort – has entered the scene stressing the idea that some places are more important than others because they are more central : all these approaches have been following a primal representation of spatial systems, where punctual geographic entities (street intersections, settlements) are turned into nodes and their linear connections (streets, infrastructures) into edges. A pioneering discussion of centrality as inherent to urban design in the analysis of spatial systems has been successfully operated after Hillier and Hanson seminal work on cities  since the mid Eighties.
Space Syntax, the related methodology of urban analysis, has been raising growing evidence of the correlation between the so-called “integration” of urban spaces, a closeness centrality in all respects, and phenomena as diverse as crime rates, pedestrian and vehicular flows, retail commerce vitality and human way-finding capacity . The Space Syntax approach follows a dual representation of street networks where streets are turned into nodes and intersections into edges. An outcome of the dual nature of Space Syntax is that the node degree is not limited by physical constraints, since one street has a conceptually unlimited number of intersections: this property makes it possible to witness the emerging of power laws in degree distributions  that have been found to be a distinct feature of other non geographic systems [1,2,3,12]. On the other hand, the dual character leads Space Syntax to the abandonment of metric distance (a street is one node no matter its real length) – which, conversely, was the core of most if not all territorial studies  and is a key ingredient of spatial networks . Here, we propose a primal network analysis of urban street systems within a properly geographic framework based on metric distances. We show that, by using a set of different centrality measures, it is possible to characterize and discuss urban networks within the same framework of all other complex systems of a non geographic nature. In our approach, urban street patterns are turned into nondirected, valued, primal graphs, where intersections are nodes and streets are edges. A valued graph G, of N nodes and K edges, is 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 the value associated to the edge, in our case the metric length of the street connecting i and j. Edges follow the footprints of real streets. The Multiple Centrality Assessment (MCA) consists in the evaluation of the importance of a node based on four different centrality
measures, namely closeness CC, betweenness CB, straightness CS and information CI. Centrality Measures Degree centrality, CD, is the simplest definition of node centrality. It is based on the idea that important nodes have the largest number of ties to other nodes in the graph. The degree centrality of i is defined as [4,15]:
Ci D =
ki N −1
where ki is the degree of node i, i.e. the number of nodes adjacent to i. Degree centrality is not particularly relevant in primal urban networks where node degrees are limited by geographic constraints. Closeness centrality, CC, measures to which extent a node i is near to all the other nodes along the shortest paths, and is defined as [4,15]:
Ci C =
N −1 ∑ dij j∈G i≠ j
where dij is the shortest path length between i and j, defined, in a valued graph, as the smallest sum of the edges lengths throughout all the possible paths in the graph between i and j. Betweenness centrality, CB, is based on the idea that a node is central if it lies between many other nodes, in the sense that it is traversed by many of the shortest paths connecting couples of nodes. The betweenness centrality of node i is :
Ci B =
n (i ) 1 ⋅ ∑ jk ( N − 1) ( N − 2 ) j ,k∈G n jk j ≠ k ≠i
where njk is the number of shortest paths between j and k, and njk (i) is the number of shortest paths between j and k that contain node i. Straightness centrality, CS, originates from the idea that the efficiency in the communication between two nodes i and j is equal to the inverse of the shortest path lenght dij . The straightness centrality of node i is defined as:
∑ S i
j∈G j ≠i
d ijEucl d ij
where d ij Eucl is the Euclidean distance between nodes i and j along a straight line, and we have adopted a normalization recently proposed for geographic networks . This measure captures to which extent the connecting route between nodes i and j deviates from the virtual straight route. Information centrality, CI, is a measure introduced in , and relating a node importance to the ability of the network to respond to the deactivation of the node. The network performance, before and after a certain node is deactivated, is measured by the efficiency of the graph G [16,19]. The information centrality of node i is defined as the relative drop in the network efficiency caused by the removal from G of the edges incident in i:
Ci I =
∆E E (G ) − E (G′) , = E E (G )
E (G ) =
d ij Eucl ∑ i , j∈G d ij i≠ j
N ( N − 1)
where G′ is the network with N nodes and K-ki edges obtained by removing from G the edges incident in node i. Notice that E(G) is finite even for a non-connected graph. Application to 1-square mile maps We have selected eighteen 1-square mile samples of different world cities from Ref. , imported them in a GIS (Geographic Information System) environment and constructed primal graphs of street networks using a roadcenterline-between-nodes format . The considered cities (see the list in table 1) exhibit striking differences 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, fine-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. Case Ahmedabad Barcelona Bologna Brasilia Cairo Los Angeles London New Delhi New York
N K Case N K 2870 4387 Paris 335 494 210 323 Richmond 697 1086 541 773 Savannah 584 958 179 230 Seoul 869 1307 1496 2255 San Francisco 169 271 240 340 Venice 1840 2407 488 730 Vienna 467 692 252 334 Washington 192 303 248 419 Walnut Creek 169 197
Table 1. Basic properties of the primal graphs obtained from the eighteen 1-square mile samples of the different world cities considered. N is the number of nodes, K is the number of edges.
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. The basic characteristics of the
derived graphs are reported in table 1: N and K assume widely different values, notwithstanding the fact we have considered the same amount of land. In fig. 1 we report the edges length distribution P(l) for the two different classes of cities. In particular we take into consideration Ahmedabad and Cairo as self-organized cities, and Los Angeles and Richmond as mostly planned cities. Cities of the first class show single peak distributions, while cities of the second one show a multimodal distribution, due to their grid pattern. Finally, for each of the eighteen cities we have evaluated the four node centrality indices: CC, CB, CS and CI.
trality, exhibits a spatial distribution that is in many cases similar to that of CB. This is especially evident in Cairo (fig.2d above), as well as in Ahmedabad and Venice. Notwithstanding the similarities in the color maps, the two measures exhibit radically different statistical distributions.
Fig. 1 Length distributions for (a) two self-organized cities (Ahmedabad and Cairo), and (b) two planned cities (Los Angeles and Richmond). Length distributions P(l) are defined by N(l)/N, where N(l) is the number of edges whose length is in the range [l - 5 meters; l + 5 meters].
The spatial distribution of centralities. The spatial distributions of node centralities have been graphically illustrated by means of GIS supported colourcoded maps. As representative examples of self-organized and planned patterns we consider respectively Cairo and Richmond (fig.2). Analogous figures for the remaining cities can be downloaded from our website . In both grid and organic patterns, CC exhibits a strong trend to group higher scores at the center of the image (fig.2a). This is both due to the nature of such index and to the artificial boundaries imposed by the 1-square mile maps representation. Edge effects are also present, although less relevant, in the other centrality measures (see for instance the contour nodes in fig.2b and 2d below). The spatial distribution of CB nicely captures the continuity of prominent urban routes across a number of intersections, changes in direction and focal urban spots. This is visible both in Cairo (fig. 2b above) and in Richmond (fig.2b below). In particular, in Richmond CB clearly identifies the primary structure of movement channels as different to that of secondary, local routes. The same happens in Ahmedabad and Seoul. Among the other cities not shown, CB is particularly effective in Venice, where most popular walking paths and squares (“campi”), and the Rialto bridge over the Canal Grande, emerge along the red nodes routes. The spatial distribution of CS depicts both linear routes and focal areas in the urban system (fig. 2c): CS takes high values along the main axes, even higher at their intersections. Finally CI, although based on a different concept of cen-
Fig. 2 The spatial distributions of centrality in Cairo (above) and Richmond (below): the former is an example of a largely self-organized city while the latter of a mostly planned city. The four indexes of node centrality, (a) Closeness CC; (b) Betweenness CB; (c) Straightness CS and (d) Information CI, are visually compared over the primal graphs. Different colours represent classes of nodes with different values of the centrality index. The classes are defined in terms of multiples of standard deviations from the average, as reported in the colour legend.
The statistical distribution of centralities. In fig.3 we report an example of the cumulative distributions of centrality indexes obtained for the two categories of cities. Closeness, straightness (not shown in figure) and betweenness distributions are quite similar in both self-organized and planned cities, despite the diversity of the two cases in socio-cultural and economic terms could not be deeper. In particular, CB exhibits a single scale distribution  both self-organized and planned cities, the former having an exponential distribution, the latter having a Gaussian distribution, as respectively shown in fig.3a and fig.3b for Ahmedabad and Cairo, and for Los Angeles and Richmond. Conversely, the distribution of CI is broad-scale for self-organized cities, and single-scale for planned cities. In fact, as shown in fig.3d, the information centrality distributions for Los Angeles and Richmond are well fitted by exponential curves, while, as shown in fig.3c for the cases of Ahmedabad and Cairo, distribution are perfectly fitted by power-laws P(C) ~C-γ with exponents γAhm=2.74, γCai=2.63. Among the selforganized cities considered, Venice is the one with the smallest value of the exponent, namely γVen=1.49. Similar results have been obtained by modelling planned cities as regular triangular, square or rectangular lattices, and self-organized cities as growing networks [24,25,26].
have low centrality scores and coexist with a few nodes with high CI [1,12]. Inequalities in the distribution of the four centrality indexes among the nodes of the network can be quantified consistently by evaluating the Gini coefficients of the distributions. The Gini coefficient g is an index commonly adopted to measure inequalities of a given resource among the individuals of a population. It can be calculated by comparing the Lorenz curve of a ranked empirical distribution, i.e. a curve that shows, for the bottom x% of individuals, the percentage y% of the total resource which they have, with the line of perfect equality . The coefficient g ranges from a minimum value of zero, when all individuals are equal, to a maximum value of 1, in a population in which every individual except one has a size of zero. E.g., in the case of CI, the Gini coefficient is 0.12 for New York, 0.19 for Richmond, and 0.23 for Cairo, thus indicating that Cairo shows a distribution more heterogeneous than those of Richmond and New York. In fig.4 we show the results of a clustering analysis based on the Gini coefficients of the five centrality distributions. Here, the iterative pairing of cities seems to capture some basic classes of urban patterns: it is the case of the early association of Barcelona and Washington or New York and Savannah, all grid-iron planned cities as well as that of Bologna, Wien and Paris, all mostly medieval organic patterns. Brasilia, Walnut Creek and New Delhi, to this respect, share a planned, large scale modernist formation. Venice is the last association, which tells of the unique mix of fine grained pattern and natural constrains that have shaped the historical structure of the city.
Fig. 3 Cumulative distributions of betweenness CB (a, b) and information CI (c, d) centrality for two self-organized cities (Ahmedabad and Cairo), and two planned cities (Los Angeles and Richmond). Cumulative centrality ∞ , where N(C) is distributions P(C) are defined by P (C ) = ∫ N (C ' ) / N dC ' C
the number of nodes having centrality equal to C. The betweenness distributions are single scale in all the cases: the dashed lines in panels (a) and (b) are respectively exponential, P(C) ~exp(-C/s) (sAhm = 0.016, sCai=0.022), and gaussian, P(C) ~exp(-1/2 x2/σ2) (σLA= 0.078, σRich=0.049), fits to the empirical distributions. Conversely, the information centrality distributions notably differentiate self-organized cities from planned ones: the dashed lines in the log-log plot of panel (c) indicate that the information centrality follows a power law P(C) ~C-γ for the two self-organized cities (γAhm=2.74, γCai=2.63), whereas the dashed lines in panel (d) indicate an exponential distribution P(C) ~exp(-C/s) for the two planned cities (sLA = 0.007, sRich=0.002).
The identified power-laws indicate a highly uneven distribution of CI over self-organized networks: most nodes have low centrality scores and coexist with a few
Fig. 4 Hierarchical tree (dendrogram) baesd on the Gini coefficients of all centrality distributions. The complete linkage method, based on the largest distance between objects in different clusters, has been applied. Choosing a maximum distance equal to 0.15 for two cities to belong to the same cluster, we find: a first cluster (in red) from Barcelona to Los Angeles including medieval organic patterns and most grid-iron planned cities; a second cluster (in cyan) from Ahmedabad to Seoul including self-organized cities; a third cluster (in blue) made up by New York and Savannah, both grid-iron, but different from cities of the first cluster for peculiarities in the geometric patterns; a forth cluster (in green) from Brasilia to New Delhi, including cities with a sizeable number of cul-desacs and a large scale modernist formation; a fifth cluster (in grey) constituted only by Venice, atypical for its strong natural constraints.
Conclusions Analysis performed on non directed, valued, primal graphs has shown that CC, CB, CS, and CI consistently capture different natures of centrality. Despite the striking differences in terms of historical, cultural, economic, climatic and geographic characters of selected cases, CC, CB, and CS show always the same kind of distribution. CI, instead, is differently distributed in planned and selforganized cities: exponential for planned cities and power law for self-organized ones. The inequality of centrality indexes distribution over the “population” of nodes has been investigated: a certain level of structural similarities across cities are well captured through the cluster analysis operated on the Gini coefficient. The Multiple Centrality Assessment method, hereby presented opens up to the in depth investigation of the correlation between the structural properties of the system, and the relevant dynamics on the system , like pedestrian/vehicular flows, retail commerce vitality, land-use separation or urban crime, all information traditionally associated to primal graphs. We expect that some of these factors are more strictly correlated to some centrality indices than to others, thus giving informed indications on the actions that can be performed in order to increase the desired factors, as economic development, and to hinder the undesired ones, as crime rate.
19 Latora V, Marchiori M, 2005, “Vulnerability and Protection of Critical Infrastructures”, Phys. Rev. E71, 015103 20 Jacobs, A. (1993) Great streets (MIT Press, Boston, MA). 21 Dalton., N., Peponis, J., Dalton, R. (2003), Proc. 4th Int. Space Syntax Symp. London UK. 22 http://www.ct.infn.it/~latora/1sqml.html. 23 Amaral, L. A. N., Scala, A., Barthelemy, M., Stanley, H. E. (2000) Proc. Natl. Acad. Sci. U.S.A. 97, 1114911142. 24 Crucitti, P., Latora, V., Porta, S. in preparation. 25 Batty, M., Longley, P. (1996) Fractal Cities (Academic Press, London, UK). 26 Makse, H. A., Havlin, S., Stanley, H. E. (1995) Nature 377, 608-612. 27 Dagum, C. (1980) Écon. Appl. 33, 327-367. 28 Kuipers, B., Teucci, D., Stankiewicz, B. (2003) Environ. Behav. 35, 81-106.
References 1 Albert, R., Barabási, A. L. (2002) Rev. Mod. Phys. 74 4797.
2 Strogatz, S. H. (2001) Nature 410, 268-276. 3 Pastor-Satorras, R., Vespignani, A. (2004) Evolution and structure of the Internet (Cambridge University Press, Cambridge, UK). 4 Wasserman, S., Faust, K. (1994) Social Networks analysis (Cambridge University Press, Cambridge, UK). 5 Bavelas, A. (1948) Hum. Organ. 7, 16-30. 6 Wilson., G. A. (2000) Complex Spatial Systems: The Modelling Foundations of Urban and Regional Analysis (Prentice Hall, Upper Saddle River, NJ). 7 Hillier, B., Hanson, J. (1984) The social logic of space (Cambridge University Press, Cambridge, UK). 8 Hillier, B. (1996) Space is the machine: a configurational theory of architecture (Cambridge University Press, Cambridge, UK). 9 Jiang, B., Claramunt, C. (2004) Environ. Plan. B 31, 151162. 10 Rosvall, M., Trusina, A., Minnhagen, P., Sneppen, K. (2004) preprint cond-mat/0407054. 11 Porta, S., Crucitti, P., Latora, V. (2004) pre-print condmat/0411241. 12 Albert, R., Barabási, A. L. (1999) Science 286, 509-512. 13 Salheen, M., Forsyth, L. (2001) Urb. Des. Int. 6 93-106. 14 Gastner, M. T., Newman, M. E. J. (2004) preprint condmat/0407680. 15 Freeman, L. C. (1979) Soc. Net. 1, 215-239. 16 Latora, V., Marchiori, M. (2001) Phys. Rev. Lett. 87, 198701. 17 Vragovìc, I., Louis, E., Dìaz-Guilera, A. (2004) preprint cond-mat/0410174. 18 Latora, V., Marchiori, M. (2004) preprint condmat/0402050