Dr César Ducruet
email: cdu@parisgeo.cnrs.fr

Graph Theory

Originally a branch of mathematics designed to formalize the topological properties of networks, graph theory has evolved dramatically in the last two decades through interdisciplinary research encompassing both social and natural scientists. Geographers, who have been actively pushing for the integration of graph theoretical methods into geography in the 1960s have somewhat neglected recent advances in network theory and analysis originating from graph theory.

The origins of graph theory are often attributed to the works of Leonhard Euler. In a classic study of the city of Koenigsberg (1735), he designed a problem where a set of nodes (or vertices) connected by links (or edges), had to be traveled without passing two times by the same road or bridge. Such an exercise proved to be mathematically impossible, and motivated further efforts to define the topological properties of graphs during the subsequent decades and centuries. Still nowadays, the application of graph theory to geography remains largely focused on technical networks, using traditional mathematical tools [START_REF] Arlinghaus | Graph theory and geography: an interactive view[END_REF]. This entry describes graph theory in general as well as its use by geographers, notwithstanding parallel evolutions of the field in other social and natural sciences, and their mutual influences.

A wide and specific vocabulary describes various sorts of graphs having distinct internal structures, as well as subgraphs (subset of connected nodes) and individual nodes by the architecture of their mutual links. Graphs may be visualized either through matrices or by the node/link view, and many graph visualization softwares exist nowadays, capable of applying numerous types of visualizations and measures even on very large networks composed of thousands of links and nodes. Visualizing large graphs is often an exercise with limited outputs, due to poor readability, so that many different operations of network simplification should be applied prior to visualization, such as filtering links or nodes according to certain quantitative thresholds or qualities. Furthermore, visualizing a network on a map, such as in geography (but this has become so popular nowadays that any spatially embedded dataset made of nodes and links can be instantaneously projected on the screen regardless of its size etc.), brings in additional issues of readability. The matrix itself (or adjacency matrix) is represented by a table where nodes are rows and columns, and links are, in their simplest understanding, represented in a binary fashion by the number 0 or 1 where lines and columns intersect. There are specific mathematical calculations based on matrices that we do not detail in this review. Visualizing graphs as sets of nodes connected by links proved to be more useful to illustrate the existence of various network morphologies, or fundamental components of networks, such as cycles, cliques, chains, motifs, but also various situations characterizing individual nodes, such as isthmus, bridge, ego network, star, etc. Graph theory is based on a specific vocabulary to describe networks. Nodes and links are labelled vertices (vertex) and edges, respectively. Vertices may be junctions or end points in the graph, with edges between them. Connexity refers to the property of a graph to have all its vertices interconnected, which otherwise contains isolates (i.e. vertices without edges) or at least two connected components. A complete graph is defined by the maximum number of edges among vertices. The graph is directed (digraph) when two edges exist between two same vertices, referring to two directions (AB vs. BA). When both directions exist the graph is said symmetrical, otherwise asymmetrical. Other dimensions are also important, such as when vertices and edges have certain values, in a weighted graph (e.g. passenger flow, number of vehicles); when vertices are connected by only one type edges (simple graph) or at least two types (multigraph, multiplex graph), such as, in a social network, friendship and professional ties. Finally, a bipartite graph exists when two or more types of vertices are connected, such as conferences and speakers, journals and scholars, etc. at the condition that vertices of the same nature are not connected with each other.

Numerous internal structures have also been identified within graphs at different levels of their organization. For instance, chains and cycles are both continuous alignment of edges, while the cycle starts and ends at the same vertex. A path between two nodes is a sequence of edges travelled in the same direction. Several paths may exist between two same nodes, thus motivating the search for the shortest path and of the minimum cost path, the latter being only possible in the case of a weighted graph where edges are valued by a distance, time, or other metric (e.g. days, hours, kilometers, monetary value). For the shortest path, topological distance refers to the number of edges to be crossed in order to reach the final destination of the path.

Topological distance is often referred to as path (or edge) length but also depth. The clique is one fundamental structure of graph theory, defined as a maximal complete subgraph, i.e. a subset of nodes being fully connected with each other, the smallest example being the triangle of "3clique". In social network analysis (SNA), the clique is an essential component of social organization, and is often opposed to the "star" configuration where several vertices are connected to only one vertex. The ego network comprises the connected neighbors of a given vertex as well as the edges among these neighbors. More complex internal structures have been the focus of several researches on graphs, such as the so-called "clusters" or "communities", which definition may vary according to several criteria. Overall, a cluster or community is defined either by a higher density of connections or by the similarity of their connections. In other words, tightly connected vertices may form a community with a high probability to be relatively close to each other in the graph. Vertices having similar connectivity to others, conversely, may be close or far away to each other. Vertices and edges lying in between two or more communities are often labelled isthmuses or bridges, due to their high importance. In social network analysis, it is also called weak tie or structural hole in the case of edges in-between different groups. Finally, a graph is said assortative when the number of edges of a given vertex is positively and significantly correlated with the average number of edges of its direct neighbors in the graph, otherwise it is said disassortative.

Based on the aforementioned characteristics, graphs may be labelled differently in terms of their overall structural properties. The regular graph (or k-regular) possesses exactly the same number of edges per vertex. The random graph exhibits a normal or Gaussian statistical distribution of the number of edges per vertex. Scale-free and small-world graphs are defined below when it comes to the more recent field of complex networks. The tree graph refers to a situation where no clique, cluster, or cycle can be found, as in the case of river networks for instance, which function as dendrograms. More conventional measures help revealing the overall structure of the graph and define its main character. For instance, the diameter is the length of the longest of the shortest paths among all pairs of vertices in the graph, measured by the number of edges needed to be travelled. The average shortest path length is similar but refers to the average number of edges composing the shortest paths across the graph, while high values often imply more difficulty to circulate in the network. Planar graphs often have high values for both diameter and average shortest path length. The average clustering coefficient (or transitivity) measures on average the proportion of closed triangles in the maximum possible number of triangles in the graph. In that sense it is close to another classic measure of graph theory, the alpha index, which looks at the proportion of existing cycles in the maximum possible number of cycles, with the difference that a cycle can have a length of three edges (triangle, 3-clique) but also of four, five, etc. High values of the average clustering coefficient mean that the graph is tightly connected, while tree graphs will always have zero.

One of the first imports from mathematics into geography was made by [START_REF] Kansky | The structure of transportation networks: Relationships between network geography and regional characteristics[END_REF], incorporating previous studies on telecommunication flows and highway networks among US cities. Such works notably reviewed the various measures and indices applicable to mostly planar graphs, i.e. graphs where two edges cannot cross without creating a vertex, as it is often the case for road, rail, and river networks; the main goal being to describe the morphology, connectivity, and density of various graphs [START_REF] Haggett | Network analysis in geography[END_REF]. Without reviewing them entirely, most common indices include the diameter (number of links between the two most distant nodes), the alpha (share of observed cycles in the total possible number of cycles -the cycle being a closed path of various length in terms of its number of links), beta (number of links per node, or density), and gamma (share of observed links in the total possible number of links, or completeness) indices. Three limitations of such general indices should be addressed, however.

First, one major drawback is that two networks of identical size (number of nodes and links) but with drastically different topology (e.g. star-shaped network where one node connects all others vs. chain-like network formed by an alignment of links) will be characterized by same results.

Second and related with the first, general indices are not robust to network size, so that their level will vary according to the size of the network. Third, graph theory and its application to geography long remained binary (presence or absence of a link between two nodes), thereby completely ignoring the possible weight of links (e.g. traffic intensity or capacity, kilometric length) and their quality (e.g. links and nodes of different types).

Other measures include those at the local level, such as calculating, for each node, its farness to all other nodes by the number of links needed to connect the most distant node (Koenig number) or the total length of shortest paths connecting all other nodes (Shimbel accessibility index) (Figure 1). Such studies focusing on small, planar networks thus largely neglected the analysis of non-planar networks (i.e. allowing edge crossings without creating nodes). Due to limited interactions with Social Network Analysis (SNA) that developed from the 1920s onwards, no imports have been realized from sociology although the latter had developed many tools for analyzing non-planar networks. For instance, betweenness centrality (number of times a node lies on a shortest path in the graph) as well as transitivity (or clustering coefficient) came from SNA, and later on were integrated in studies of complex networks. They consider that for each node, there is a share of observed triangles -or cliques -in the maximum possible number of triangles among its neighbors. Transitivity had no use for studying planar networks since rectangles rather than triangles are often found in road or railway networks. It is only in the early 1990s that geographers started to analyze networks of different nature, or non-planar networks, such as those formed by multinational corporations, airlines, and shipping lines, thereby stepping out of classic graph theory [START_REF] Ducruet | Spatial science and network science: review and outcomes of a complex relationship[END_REF] and from a more urban perspective. Other important refinements of graph theory have been to consider the weight and spatial dimension of networks. The cited measures have been adapted to incorporate the weight of links and nodes so as to better reflect inequality in, for instance, traffic distribution, compared with the sole topological (binary) aspects. Thus, all measures can be weighted according to various metrics at global (whole network) and local (individual nodes) levels. When it comes to the spatial dimension of networks, physicists were keen to demonstrate the influence of spatial constraints on network growth and topology, whereas such aspects were often taken for granted by geographers, since all their studies focused on spatially embedded networks in contrast with studies of non-spatial networks such as social networks, collaborative and citations networks, the world wide web, etc. Geographers focused more on detailed analyses of binary graphs in abstract spaces and of real networks using Geographical Information Systems but often without reference to graph theory. Physicists studying spatial networks notably underlined that preferential attachment occurs over shorter distances, since there is a cost of creating new links to overcome the friction of space, thus resulting in higher average clustering coefficients than in non-spatial networks [START_REF] Barthelemy | Spatial networks[END_REF]. Efforts made by geographers to improve their use of graph-theoretical methods occurred in relative isolation, though, from the rapid evolution which graph theory went through in the late 1990s and early 2000s. Natural scientists, such as physicists, have been eager to rejuvenate graph theory and notably the aforementioned limitations as well as its approach of graph dynamics. They notably proposed to define a so-called "complex network" by non-trivial topological attributes, which are neither random nor regular, but are found in most real-world networks. Another dimension of complex networks is their large number of nodes and links, and their analysis clearly benefited from the growing availability of large datasets and computation power. New measures were proposed, although they were in fact a rediscovery of existing ones, such as transitivity (clustering coefficient) originating from SNA and the gamma index (density) proposed by [START_REF] Kansky | The structure of transportation networks: Relationships between network geography and regional characteristics[END_REF]. Still, the merit of natural scientists has been to provide clearer definitions of network models and their evolutionary mechanisms, with new applications on realworld networks that were traditionally analyzed by social sciences in more limited ways. One of their major achievement has been to complement the random graph model, which were dominant until then (a random graph is characterized by a normal or Gaussian distribution of the nodes' degree), by two new models: scale-free and small-world. The small-world network is defined by a higher average clustering coefficient and smaller diameter than the random graph of equal size [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. It means that small-world networks are more likely to contain cliques (subgroups of at least three connected neighbors forming a closed path) and to provide more efficient ways to circulate in the network, in terms of the length needed to connect its distant parts. Scale-free networks are similar to small-world networks but their distribution of degrees follows a power-law (the slope exponent ranging between 2 and 3), which means that very few nodes have plentiful connections, and a vast majority of nodes have very few connections. Another dimension of scale-free networks is the process of preferential attachment by which newly added nodes primarily connect larger nodes, thereby reinforcing the hierarchical structure of the network (Barabasi and Albert, 1999). Despite the spread of such models across almost all scientific disciplines, geography has remained somewhat reluctant in adopting and testing these innovations. In fact, geographers doing network analysis have continuously relied on the same indices and measures over the last five decades. Just like the innovative character of complex network research is questioned, the benefits of applying such methods to test geographic questions also remain unclear. Should this be indebted to the models or to the way they were applied? One part of the answer lies in the fact that geography as a whole went through a "behavioral" turn after the so-called quantitative revolution of the 1960s, graph theory and network analysis -and spatial analysis as a whole -remaining "somewhat of a backwater" since then [START_REF] Waters | Network and nodal indices. Measures of complexity and redundancy: A review[END_REF]. Networks continued to be analyzed by regional scientists but not necessarily using graph theory, so in even more abstract spaces while focusing on costs, and engineers focusing on performance and optimization. Yet, a small number of geographers have promoted the rediscovery of graph theory through the adoption of certain methods and models rejuvenated by complex networks research.

One first and key issue raised by geographers has been the relationship between network measures at node level and the more socio-economic characteristics of the connected places, such as by looking at significant statistical correlations between different centrality measures (i.e. degree, betweenness, and closenessthe latter being the inverse of the Shimbel distance) and local urban/regional data (e.g. population or Gross Domestic Product) Internet, airline, telecommunications, and scientific collaboration networks on a national or world level, as well as between street network centrality and retail and service concentration at the intra-city level (see [START_REF] Ducruet | Spatial science and network science: review and outcomes of a complex relationship[END_REF] for a synthesis). The second dimension explored by geographers is the influence of distance on network topology as mentioned above, although this influence is often taken for granted by geographers One original approach has been to apply space syntax to urban streets so as to consider the network from a more cognitive point of view.

Space syntax notably proposed to consider crossroads as links between streets, the latter being defined by their name or number instead of as alignments of different segments [START_REF] Hillier | The social logic of space[END_REF]. Such an approach made it possible to have a completely different approach to centralities and topologies in a planar network, and to extract meaningful information on the small-world and scale-free dimension of many cities (i.e. dual graph). In the same vein, and as a third aspect of renewed graph theory applied in geography, several geographers have proposed a combination of methods rather than a strict, direct application of complex networks. It is interesting to mention that, for instance, Spatial Interaction Models (SIM) such as the gravity model (see [START_REF] Schintler | Using raster-based GIS and graph theory to analyze complex networks[END_REF], Geographic Information Systems (GIS), multiplicative growth models, and Social Network Analysis (SNA) tools, such as structural equivalence and blockmodelling, were applied, sometimes even jointly, to various networks, such as Internet backbone networks, commuting flows, road and railway networks, airline and shipping networks. This is mostly the case for regional science that was already using such methods for decades. It allowed, for instance, a better appreciation of the cost factor in network organization.

A fourth dimension is the existence of subgroups of densely connected nodes in the network, often referred to as clusters or communities of nodes. Geographers were keen to detect and define such subgroups with reference to the concept of region, sometimes also mentioning the multilevel organization of networks, whereby the different subgroups are linked to each other in various ways. Methods of partitioning (or clustering) were thus applied to a number of networks, such as the worldwide airline network of intercity passenger flows, container shipping networks and mobile phone communication networks to verify the influence of geographic proximity in the emergence of clusters, and commuter flows between localities in order to either redefine functional urban regions or to identify secondary poles inside metropolitan areas. Such approaches were already far more advanced than the traditional single (or multiple) linkage analysis proposed in the 1960s by Nystuen and Dacey (1961) and further applied in numerous contexts afterwards. Other approaches also looked at the emergence of clusters within large cities based on the cartography of vehicle trajectories. In particular, the local and global impacts of random or targeted attacks that are well investigated by physicists (e.g. cascading failures) did not yet receive much attention from geographers so far. This is rather surprising given the fact that such approaches would well apply to the analysis of cities and urban systems, which are connected by a variety of networks (e.g. power grid, water, telecommunications, transport, etc.).

Finally and as a sixth aspect of recent research based on graph theory, geographers have paid particular attention to network dynamics. Very few works have approached directly the dynamical evolution of real-world networks. Existing studies are more approaching dynamics through an analysis of successive static states of the network or phases, mostly due to a lack of continuity in available time series datasets of any kind. Other approaches to network dynamics are also those applying simulation methods to systems of cities, starting from an initial stage and testing the role of different parameters on the evolution of urban size in a relational perspective (Bretagnolle and Pumain, 2010), but often without actual information on inter-city linkages.

Graph theory has had an important influence on the way geographers studied spatial phenomena, but this influence has been stronger in the early phase of its adoption, and remained mostly true in the specific field of transportation networks. Natural scientists have been faster in adopting (and even fostering) innovations that appeared in the late 1990s through what is known as complex network research. While geographers became skeptical about the benefits of graphtheoretical methods applied to spatial issues, physicists and computer scientists had no doubt that their models, concepts and methods would improve our understanding of the uneven distribution of flows and networks, especially across space. Nevertheless, one major limitation of complex network research done by natural scientists is the absence of discussion about the link between their results and the wider social, economic, institutional and political context in which networks evolve. Stronger interactions between natural and social sciences, among which geography, is thus needed in order to better bridge abstract space and concrete space. In the past decades, geographers have proved to be able to explain in detail the strategies of specific actors involved in building and expanding networks of all kinds, but without a firm engagement into renewed methods of network analysis. On the contrary, natural scientists keep on refining their models and tools to analyze graphs, but without questioning the possible link with existing geographical research. Issues of scales, borders, territories, urbanization, innovation, diffusion, globalization, regional planning, environmental and socio-economic impacts are still to be explored in relation with what graph theory may provide to the concerned actors and institutions. Yet, an area well covered by geographers in the last decade, in collaboration with computer scientists, has been the search for better methods to visualize spatial networks and flows [START_REF] Rozenblat | Methods for multilevel analysis and visualization of geographical networks[END_REF]. This constitutes, perhaps, the main contribution of geography so far to graph theory and network analysis as a whole.

SEE ALSO: Network Analysis; Transport Networks; Visualization

Figure 1 :

 1 Figure 1: Selected graph-theoretical measures

  Fifth, geographers have attempted to go beyond the analysis of single (or simple) networks by proposing an analysis of coupled or interdependent networks of different nature, labeled multigraphs (or multiplex graphs) in the classic graph theory literature. Due to the absence of a formal mathematical definition of multigraphs, and therefore, of a precise methodology to analyze them, scholars had to create innovative ways to extract meaningful information dedicated to such graphs. Sometimes the network is simply a combination of various networks (or network of networks) in which the nature of the links is ignored, but the analysis compares the effect of adding (or removing) one or more networks at the level of nodes or the entire network. This was applied to the analysis of world regions and global cities based on various types of links (e.g. trade, diplomatic, airlines, and shipping lines). Other examples include the combination of airline and Internet networks, airline and corporate (multinational) networks, etc. Yet, geographers have poorly investigated to what extent are certain places more specialized than others in terms of combined centrality, how certain networks and nodes are more vulnerable than others according to their physical embedding and distribution across space.


Dr César Ducruet
email: cdu@parisgeo.cnrs.fr

Transport networks

A transport network is basically defined as a set of connected nodes and links allowing the circulation of goods and/or individuals. Traditionally studied for itself and in rather abstract ways through graph-theoretical and economic lenses, the transport network has increasingly been defined as one component only, albeit crucial, of wider logistical, territorial, and societal realities.

) have particularly demonstrated that biological networks such as those built by slime molds are "with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks-in this case, the Tokyo rail system". While the nature of nodes may vary from one network to the other, those are often crossings, stations, terminals, cities or countries etc., while links can be of totally different nature, from physically grounded tracks to more ephemeral flows. In all cases, transport

networks belong to the category of "spatial networks" that comprises many other networks such as so-called technical networks (e.g. power grids) and any network being physically (and often geographically) grounded into space (see Barthelemy, 2010). Like any other network and according to the language used by graph theory, a branch of mathematics describing the topological properties of networks, a transport network may be planar or non-planar (i.e. without or with crossings between links or "edges"), directed or undirected, weighted or not (i.e. where links carry a certain quantity e.g. of traffic, distance, or time). A multimodal transport network may be understood as a "multigraph" where two given nodes are connected via at least two links of different nature. However, the concept of transport network does not entirely belong to graph theory; it includes other approaches, such as transport history, spatial analysis, economics, or engineering, where nodes, links and flows are considered by means of other methods, such as discourses, policies, actors, governance, planning, and dedicated Geographical Information Systems for Transport (GIS-T).

Traditionally in geography, transport networks have been the focus of scholars willing to apply quantitative methods to geographical research. Transport networks and flows received foremost attention in the 1960s by US geographers. They particularly developed the idea of ideal-typical sequences of transport network development and applied several graph-theoretical methods to road and railway networks [START_REF] Taaffe | Geography of transportation[END_REF]. The most renowned model describes six successive phases inspired from the evolution of transport networks in West Africa (see [START_REF] Rodrigue | Conceptual corridor development[END_REF] for a useful online illustration). In a first phase (Scattered ports), a set of ports along a coastline is characterized by homogeneity in traffic volumes and connection levels based on local resources. The second phase (Penetration lines and port concentration) witnesses an expansion of the hinterland benefitting to only a minority of such ports through new transport lines such as rail or canal. The subsequent phases reinforce a path-dependent process by which initially favored ports continue to grow proportionally to the importance of their inland accessibility as the corridor emerges gradually through economies of scale. Although this model has been updated to take into account overseas linkages among ports and more recent trends of de-concentration, many critiques have been addressed given the linear dimension of the successive phases which ultimately always lead to concentration in the core and decline in the periphery. Similar criticism emerged from (trans)port specialists about early urban models, such as the central place theory, due to its inability incorporating deviations caused by specific transport configurations (sea-land, intermodal), as in the works of British geographer James Bird.

In the early days however, limited computational power largely explained the reliance upon small, planar networks easily extracted from city and country maps, while detailed -and often more voluminous -data about transport flows remained hardly accessible.

Two central and recurrent themes until nowadays are the topology of transport networks and the accessibility and centrality of their nodes. The topology may refer to the differences between the actual layout of a given transport network and its simplified representation as a graph, i.e. straight lines (or edges) between nodes (or vertices). The graph itself is often understood as a matrix, sometimes called origin-destination (O-D) matrix, where links exist or not between nodes ordered in lines and columns (Figure 1). Several measures express a variety of topological features based on such a graph or matrix [START_REF] Kansky | The structure of transportation networks: Relationships between network geography and regional characteristics[END_REF], such as the size of the network (number of nodes and links), its density (number of links per node), completeness (proportion of existing links in the maximum possible number of links), cliquishness (number of cycles, transitivity as measured by the average proportion of connected adjacent neighbors in the maximum possible number of connected neighbors), etc. Using the graph or matrix to calculate network indices makes it possible to apply any graph-theoretical measure such as those found in Social Network Analysis (SNA) and complex systems, despite fundamental differences in the nature of the studied networks. Some measures may not be interpreted the same depending on if people, firms, terminals, or neurons are concerned. Nevertheless, transport networks are common objects of an emerging "science of networks" notably since physics and computer science started to analyze such networks with renewed tools and concepts since the late 1990s [START_REF] Newman | Networks: an introduction[END_REF].

Other aspects of transport networks have thus been explored, such as their scale-free and/or small-world dimensions, the probability for nodes to connect other nodes of comparable size (assortativity), the average shortest path length, the "rich-club" coefficient, etc. While the degree distribution follows a power-law function in scale-free networks, small-world networks are characterized by the existence of dense communities (or subgroups of nodes). The rich-club dimension refers to networks in which nodes with many links connect primarily with each other.

Great care must be inferred, however, in comparing different networks via such methods because network indices are often biased by network size. Such measures better apply to the evolution of a single network over time, or to the comparison between actual and optimal configurations. For instance, a given (planar) transport network, if weighted by cost or other metric, is best understood when confronted to its two possible extreme situations, i.e. when all possible links are built (cf. greedy triangulation) or when only the optimal links are retained (cf. minimum cost spanning tree). Novel evidence could have been proposed based on such methods when comparing cities of the world through the configuration of their streets, in terms of planning models, urban architecture, and overall circulation efficiency (see [START_REF] Barthélemy | Co-evolution of density and topology in a simple model of city formation[END_REF]. At the node level, measures are similar and may look at the immediate environment of nodes by the number of adjacent neighbors (degree centrality), which correspond to the number of connected airports for instance. In a road or railway network, cities or stations can be compared according to their farness (or eccentricity) to other nodes, their occurrence on shortest paths, etc. In a weighted network, it is also interesting to look at the proportion of traffic depending on the biggest link; in the case of maritime transport, it revealed the extent to which certain ports heavily depended on a close competitor despite their high traffic volume (e.g. Shenzhen vs. Hong Kong). Are larger nodes more central in the transport network? What are the respective roles of local and global centralities? Certain findings could have pointed at interesting functions of some nodes, as in an air transport network, some nodes despite having a few links can still be highly accessible, due to their bridge role between large regions, while larger and more connected nodes often connect across farther topological and kilometric distances. In turn, the existence of such "regions" in a transport network is revealed by means of various techniques of clustering nodes based on certain attributes of connectivity. Are best connected airports or seaports geographically close? How can commuting flows help delineating functional urban areas and/or urban regions? Clustering algorithms applied to transport networks, such as modularity, have, among other results, verified the underlying regional patterns of global airline and maritime flows. Single linkage analysis, for instance, was applied to telecommunication flows as early as in the 1960s by US geographers in order to delineate socalled "nodal regions" in a given urban system.

Complementary methods of network coupling based on the concept of multigraph have explored how different transport networks share similarities but also vulnerabilities. This is where the network analysis of transport meets more practical problems of disruptions, rerouting and congestion, but also optimization. Where should a new node or link be placed in order to make the transport network(s) more robust to all kinds of failures and targeted attacks? How should two or more transport networks connected so as to limit such shocks? Such questions are particularly relevant in the case of networks being largely dependent upon a few large, critical nodes (e.g. Suez and Panama canals for sea transport). Other aspects to be explored via coupled networks include the study of potential intermodal shifts, the co-evolution of transport networks, the multimodal accessibility of cities, among others. Geographers have been particularly keen in analyzing transport network dynamics under various contexts, such as the impact of deregulation on airline networks, of railway development on urban accessibility, etc. Notably, [START_REF] Bogart | Inter-modal network externalities and transport development: Evidence from roads, canals, and ports during the English Industrial Revolution[END_REF] is a good example of a study combining a dynamical and a multimodal approach when looking at the evolution of canals, roads, and ports during the English Industrial Revolution. This work notably demonstrated the positive effect of road development on canal development, but a less significant role of ports probably due to their earlier existence. It also suggested that investing in a canal would be less profitable when nearby road improvements were initiated due to higher uncertainties about potential profits from canal tolls.

Overall, graph-theoretical approaches to transport networks attracted a lot criticism from more applied research due to its inability including more complex aspects of transport, such as cost, time, strategies, and scenarios, but also graphical aspects. Indeed, a recurrent problem of transport networks is their visualization and cartography. Recent advances in graph visualization algorithms have provided certain solutions to represent, for instance, airline networks as planar networks using so-called edge-bundling tools, in order to limit the fuzziness of mappings caused by the intermingling of numerous, space-constrained links and nodes in a large transport network [START_REF] Lambert | Graph visualization for geography[END_REF]. In turn, exploring the multifaceted dimension of transport networks, such as their territorial embedding, had mobilized other methodologies than sole graph theory. One good example is the raster-based analysis of global urban accessibility taking into account no less than ten different layers in a GIS understood as "friction surface components" [START_REF] Nelson | Estimated travel time to the nearest city of 50,000 or more people in year 2000[END_REF]. Despite its fundamental graph-theoretical essence, a work on the road accessibility of European seaports integrated several qualitative aspects such as national regulations in terms of speed limits and resting times for truckers, the presence and cost of highway tolls, the types and capacities of main road arteries, and the loading/unloading potential delays at intermodal junctions (Chapelon, 2006). In the case of urban streets, more qualitative aspects were introduced by "space syntax", which proposed to define links based on the continuity of avenues and boulevards from a cognitive point of view instead of being alignments of arbitrarily separated segments [START_REF] Hillier | The social logic of space[END_REF]. Such an approach could, by transforming lines into nodes and nodes into lines, reveal hidden dimensions of the network, the hierarchy of streets, which was not visible via the more traditional, planar perspective. Many measures did not provide extraordinary new results, since in general, the traffic volume of transport nodes, which is known from classic sources, is highly equivalent to any centrality measure: large seaports or seaports have many links and vice-versa. Rare studies, however, have truly investigated the spatial determinants of the centrality of transport nodes. These include statistical evidence about the role of urban and regional socio-economic characteristics mostly in the realm of airline networks, where cities are nodes and aircraft trips are links. Main results point at noticeable interdependencies between centrality and the well-being of localities. At least could have been made evident certain linkages between urban indicators and network indicators for cities such as in Europe based on airline data, often concluding to a circular causation between urban and transport development. The spatial dimension was also included, perhaps more by physicists than by geographers, so as to demonstrate rather trivial, albeit fundamental, properties of transport networks whereby larger nodes connect more distant nodes on average. Such works shared some affinities with the regional science perspective on transport hubs where cost and time are central parameters.

Given such limitations and despite the improvements brought by GIS-T and natural sciences, geography and other social sciences have increasingly defined transport networks as elements of wider structures. The shift from quantitative/structural to more behavioral approaches is one main explanation [START_REF] Waters | Network and nodal indices. Measures of complexity and redundancy: A review[END_REF], but also the fact that network analysis mostly considers transport networks as simplified and self-sufficient entities developed in abstract spaces. New concepts that emerged in the late 1990s, such as global production networks, value and commodity chains, have in common a disregard of pure physical flows, more concerned by the "flesh" than the "bones" when dealing with actors, mobility, governance, and territorial issues at various scales. A transport network can thus be approached via more complex and parent configurations, planned or not planned, such as corridors and gateways, although the two latter concepts are often subcomponents of the transport network itself.

Another way to place transport networks into a wider analytical perspective has been proposed by urban geographers, in implicit or explicit ways. Early urban models, such as the central place theory and up to the New Economic Geography (NEG), approached transport networks in a rather abstract fashion while conferring them vital importance in the emergence of cities and hubs within and between regions. Nevertheless, most NEG studies keep considering cities and regions as equally spaced, thus somewhat excluding the friction exerted by transport networks on mobility. Studies of urban systems and systems of cities were more keen on analyzing urban development through the more concrete configuration of transport networks, such as railway networks. In such a perspective, the transport network is used as a proxy forand a material illustration of -wider inter-urban interactions and dynamics in terms of spatial expansion, functional diversification, hierarchical transformations, and innovation cycles.

Simulation methods are used to extract meaningful properties about both transport and urban dynamics and to confront estimates with real population data across many decades or centuries.

Yet, there are very rare attempts to integrate urban or regional attributes into transport network analysis and/or modeling, such as the one of [START_REF] Schintler | Using raster-based GIS and graph theory to analyze complex networks[END_REF] analyzing the vulnerability of road and railway networks in Florida through a mixture of various methods and approaches.

More efforts are thus need to push further this integration in order to better meet current challenges in transport and society.

Figure 1 :

 1 Figure 1: Representations of a transport network

  SEE ALSO: GIS-T; Graph Theory; Maritime Transport; Network Analysis; New Economic Geography; Rail Transport (Freight); Rail Transport (Passengers); Road Transport; Routing and Navigation; Transport Geography; Transport and Transportation Systems; Visualization


Dr César Ducruet
email: cdu@parisgeo.cnrs.fr

Spatial networks

In geography, the spatial dimension of networks has long been taken for granted. This is not the case of natural sciences, of which physics, distinguishing amongst spatial and non-spatial relationships. The core element at stake is thus distance, resulting in time and cost to travel the network and/or to create new links and nodes. Yet in many disciplines, spatial networks remain analyzed in a binary fashion, without taking into account the length of links and the local characteristics of nodes. This article reviews how the spatial dimension of networks is addressed in the geographic literature and in other sciences, concluding to a need for further research in this field.

From graph theory to complex networks

From the 1960s onwards, geographers kept on studying networks from a pure topological perspective, looking at the way nodes (vertices) are connected by links (edges). Graph theory was introduced in geography to measure and describe the topology of many transport and communication networks. Quantitative geographers doing so never explicitly coined their study object 'spatial network' because the spatial dimension was seen as inherent to the network, for instance when studying a set of connected cities within a certain region or country. All the different network measures and indices made available at the time were based on the number of nodes and links, without qualifying them by spatial metrics. Perhaps, only the detour indexthe difference between straight linear distance and real distanceexplicitly addressed the influence of space on network setting. One main reason had been the dominant focus of geographers on technical networks, or networks made of physical infrastructure (e.g. road, rail), which exist in a two-dimensional space and can be characterized as planar networks, i.e. having nodes at every link intersection. The belief that all networks are spatial did not motivate further efforts to look at the influence of space compared with a non-spatial context. It is only in the 2000s that physicists, pushed by a growing interest for real-world networks, investigated the difference between spatial and non-spatial networks, revisiting existing network models and providing numerous empirical evidences. This shift from graph theory to complex networks was soon embraced by various geographers, but without necessarily following the same steps, as space continued to be taken for granted or to be a consequence rather than a cause of network structure.

A spatial network as a set of nodes and links embedded in a certain geometry. Such a geometry confers to the network a certain interaction range for nodes to connect and thus to establish links. Nodes, as places, are characterized by locational factors, from simple coordinates on a plane to more advanced attributes such as their size and function.

Recognizing the important legacy of quantitative geography in network studies, [START_REF] Barthelemy | Spatial networks[END_REF] demonstrated that existing network models were insufficient in catching those effects, while "for many critical infrastructures, communication or biological networks, space is relevant: most of the people have their friends and relatives in their neighbourhood, power grids and transportation networks depend obviously on distance, many communication network devices have short radio range, the length of axons in a brain has a cost, and the spread of contagious diseases is not uniform across territories".

Quantitative geographers mainly devoted their attention to transport, planar networks of small size, with a main emphasis on the shape of infrastructural links. This is explained by the lack of computational power at the time and by the scarcity of data on flows compared with tracks. In their goal to understand and compare the structure and evolution of such networks, geographers did not pay much attention to modelling. In turn, the famous model by [START_REF] Taaffe | Transport expansion in underdeveloped countries: A comparative analysis[END_REF] on the phased corridor concentration in West Africa did not refer to graph theory. The latter, a branch of mathematics, long remained dominated by the random graph model proposed by Erdos and Renyi (1959), where the distribution of nodes' degree (i.e. their number of topologically adjacent neighbors) follows a normal or Gaussian distribution. Graph theory kept on analyzing random graphs until physicists, in the late 1990s, formulated new models, closer to real-world phenomena. [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] proposed the small-world network model, characterized by a shorter average path lenth and a higher average clustering coefficient than a random graph of equal size. The average path length refers to the average number of stops between two nodes and the average clustering coefficient is the proportion of connected triangles in the maximum possible number of triangles in the graph. [START_REF] Barabási | Emergence of scaling in random networks[END_REF] proposed the scale-free network model, defined by a power-law distribution of nodes' degree, i.e. containing few large degree nodes and many low degree nodes. Such networks have in common to be more easily navigable due to the presence of hubs, bridges, and cliques.

The topological structure of spatial networks

As natural scientists increasingly criticized the overlooking of space in existing studies, a specific category of 'spatial network' gradually emerged in the physics literature [START_REF] Gastner | The spatial structure of networks[END_REF]) in opposition to those existing "only in an abstract "network space" where the precise positions of the network nodes have no particular meaning". [START_REF] Gastner | The spatial structure of networks[END_REF] demonstrated that most edges are short in terms of kilometric length, since "long edges are presumably more expensive to create and maintain than short ones", should it be the Internet, the highway network or the airline network (in the United States). It was also remarked by [START_REF] Barthelemy | Crossover from scale-free to spatial networks[END_REF] that long-distance edges have a high probability to connect large nodes or 'hubs', while short ones connect mainly smaller nodes with each other and with the hub. The author relates this to the preferential attachment process in complex networks discussed previously by [START_REF] Barabási | Emergence of scaling in random networks[END_REF], as when a new node is added to the network, it will not only connect a larger existing node but a geographically closer one. Subsequent works and experiments provided additional clues about the difference made by space (and distance) in the organization and structure of networks. Those concluded to a higher average clustering coefficient in spatial networks due to the importance of proximity in node connectivity, a higher disassortativity as the network grows (negative correlation between node degrees across node pairs), a higher correlation between degree and betweenness, an increased influence of the barycentre on betweenness values, and an increased cliquishness [START_REF] Ducruet | Network science and spatial science: Review and outcomes of a complex relationship[END_REF]. Other studies using clustering techniques demonstrated that numerous networks are in fact regionalized, such as the global airline network [START_REF] Guimera | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF], the global maritime network [START_REF] Kaluza | The complex network of global cargo ship movements[END_REF], and the Belgian mobile phone network [START_REF] Expert | Uncovering space-independent communities in spatial networks[END_REF], influenced either by physical geography constraints or by administrative borders. At the local level, the "relative cost" methodology was used by [START_REF] Cardillo | Structural properties of planar graphs of urban street patterns[END_REF] to compare the spatial structure of many streets networks worldwide (Figure 1). From the original network where edges are weighted by a given metric (e.g. distance, travel time or cost), the Kruskal algorithm extracts the optimal cost route (B), defined by one single line connecting all nodes or Minimum Spanning Tree (MST). The Greedy Triangulation (GT) consists in adding all possible links between nodes (C) to make it complete without breaking its planarity. This allowed the authors to find direct correspondence between network cost and urban planning type. In sociology, the "space syntax" school, also focused on urban streets, proposed to look at the urban network structure from a more "cognitive space" perspective [START_REF] Hillier | The Social Logic of Space[END_REF]. While engineers and most other scientists often considered street segments as edges and their intersections as nodes, it was envisaged to redefine streets based on the visual and name continuity of avenues and boulevards (Figure 2). Once redefined, these linear objects made of multiple segments are considered as nodes and their mutual intersections as links (axial map), thereby transforming the initially planar graph into a non-planar one (dual graph), providing newand in some way more realisticways to study accessibility and centrality within cities.

Figure 2: The space syntax methodology to analyse urban streets networks Source: adapted from Rodrigue and Ducruet (2020) Geographers and regional scientists increasingly adopted complex network methods to analyse graphs in a spatial context, from the 2000s onwards. They particularly insisted on the importance for social networks to be considered across space, and in their criticism of graphtheoretical methods, proposed various empirical studies mixing complex network analysis and spatial analysis, from spatial interaction models to Geographic Information Systems (GIS). Yet, the adoption of complex network methods by spatial scientists often left aside space itself, by considering the sole topology of nodes and links (see a review by [START_REF] Ducruet | Network science and spatial science: Review and outcomes of a complex relationship[END_REF]. One important difference with natural sciences had been, however, to put a stronger emphasis on nodes' socio-economic characteristics and their influence on centrality and connectivity. In the global maritime network for instance, as in the work of [START_REF] Gastner | The spatial structure of networks[END_REF], vessel traffic enormously concentrates over the shortest inter-port links, which are also the most numerous. This is mainly explained by the importance of coastlines on the design of shipping routes, in particular container shipping that follows scheduled portto-port services along maritime ranges. In turn, ports with higher strength (or total vessel traffic) tend to connect over longer distances, as they are fit with better infrastructure and cargo handling equipment than smaller ports [START_REF] Ducruet | Maritime networks as systems of cities: The longterm interdependencies between global shipping flows and urban development (1890-2010)[END_REF], just like large airports in the airline network [START_REF] Guimera | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF]. These large ports also act as pivots through huband-spokes systems along major interregional trade lanes, with high frequency traffic towards secondary nodes for intraregional redistribution. Not only are shorter links weightier; they are also the most diversified in terms of the distribution of traffic types across the network. Thus, the probability for a link (edge) to carry more traffic and more commodities diminishes with distance. Larger ports are also the most diversified, and they impressively centralize the network at the expense of more specialized ones, such as Rotterdam and Singapore. Last but not least, another important feature of spatial networks is the existence of gravitational rules, whereby traffic volume (or link strength) decreases with distance but increases with (node) size, in accordance with the Newton's law of gravity and echoing numerous works about spatial interaction in geography and regional science. This was demonstrated in various contexts such as maritime networks [START_REF] Kaluza | The complex network of global cargo ship movements[END_REF], highway networks in Korea [START_REF] Jung | Gravity model in the Korean highway[END_REF], and mobile phone networks in Belgium [START_REF] Krings | Urban gravity: a model for intercity telecommunication flows[END_REF]. The latter study demonstrated the importance of taking into account the local characteristics of nodes like population, as "communication intensities scale linearly with city size".

Spatiality as local socio-economic embedding

The inclusion of node attributes had been particularly fruitful for the study of spatial properties in this particular case. At the level of subnational regions connected by maritime flows, it was found that regions with higher degree and betweenness centrality are also those with a higher interaction range, a higher share of container traffic, and in the meantime concentrate population, Gross Domestic Product (GDP), and tertiary activities. In opposition, regions specialized in the primary sector and solid bulks traffic (e.g. grain, coal) have a low connectivity and interaction range. More advanced localities are thus better connected, as shown in the case of telecommunication flows in the UK for instance [START_REF] Eagle | Network diversity and economic development[END_REF] but also in other contexts such as the Chinese airline network. At the level of urban areas, larger cities by population kept on concentrating vessel traffic since the late nineteenth century. Such cities are also the most central in the network whatever the metric used (degree centrality, betweenness centrality, clustering coefficient), are the most diversified in terms of vessel types, and connect at farther distances than smaller cities. Local market size is thus a strong determinant of traffic distribution and network configuration, due to the role of cities as production and consumption centres. The application of single linkage analysis as in the pioneering work of [START_REF] Nystuen | A graph theory interpretation of nodal regions[END_REF] on telecommunication flows among Oregon cities served the identification of the network's backbone and main hubs as well as barrier effects (see Figure 3). This could highlight the isolation effect provoked by political barriers to trade at different dates, as in the case of Barcelona, Gdansk, and Shanghai in 1950, Havana (Cuba) in 1970and 1980, Tel-Aviv in 1980, but also by war effects (Beirut in 1970) and distance effects, with the recurrent isolation of Melbourne and Sydney. Such isolated subcomponents made of a small number of cities stood apart the main, larger components polarized by the world's largest cities such as New York, London, and Tokyo. Yet, these "global cities" were gradually replaced overtime by smaller ones at the centre of the network, such as the aforementioned Rotterdam and Singapore, due to the fading port-city relationship and the concentration of major port and shipping services in a few main hubs handling the biggest ships and acting as transhipment nodes between and within regions.

Many other works have compared node centrality with node characteristics such as population, density, and economic features. Numerous algorithms were used to cluster spatial networks and discover barrier effects, understood as the effect of territories on network structure, thereby revealing hidden information often neglected by natural scientists in their primary interest for general laws. Efforts have been made to better visualize spatial networks, especially in the case of non-planar graphs that are often poorly readable when plotted on a map [START_REF] Rozenblat | Methods for Multilevel Analysis and Visualisation of Geographical Networks[END_REF]). Yet, the inclusion of distance parameters in the analysis of spatial networks remains limited to a few works. Another avenue of research has been to analyse simultaneously several complementary networks, or "networks of networks", to understand their robustness and the way nodes embed in multiple layers. Overall, spatial network analysis remains highly static in scope, as we do not have many examples of how such networks grow overtime. The future of spatial network research shall thus lean towards the study of an all-encompassing system taking into account distance, node characteristics, and dynamics.

Figure 1 :

 1 Figure 1: Methodology for calculating the cost of a spatial network Source: adapted from Rodrigue and Ducruet (2020)

Figure 3 :

 3 Figure 3: Nodal regions and urban hierarchies in the global maritime network, 1950 Source: Ducruet et al. (2018)


Dr César Ducruet
email: cdu@parisgeo.cnrs.fr

Urban network

The concept of urban network implies a certain degree of interdependency among cities that are connected by various linkages at different spatial scales. Geographers but also many other scientists have theorized the urban network, leading to a wide diversity of definitions and empirical studies. We review existing approaches through three successive steps: schools of thought across scientific disciplines; operational urban networks in relation to spatial planning; and empirical analyses of intercity transport and other systems. The scarcity of studies offering a multilayered approach to urban networks and/or integrating local socioeconomic determinants motivates further research in this field.

From a historical perspective, urban networks can be seen as a particular form of organization transcending political boundaries due to their cultural and economic nature. Among the most cited examples are the Italian city-states (9 th to 15 th centuries), the Hanseatic League (14 th to 17 th centuries) in North Europe, and the Asian port cities connected by the Chinese diaspora among other vectors of exchanges [START_REF] Gipouloux | The Asian Mediterranean: Port Cities and Trading Networks in China, Japan and[END_REF]. Such urban networks emerged both in opposition and complement to centralized political governments in order to ensure trade and shipping activities led by merchants seeking a degree of freedom.

Numerous references to these textbook examples are found in contemporary spatial planning initiatives, such as the Randstad Holland in the Netherlands. Here and elsewhere in Europe, numerous inter-city partnerships emerged, generally aiming to value a common set of interests from local governments, partly derived from their common regional identity. Bottom-up examples include the Nordregio project (Baltic sea region), the Bothnian Arc, the Conference of Peripheral Port Cities, the cultural network of Eurocities, or alliances among provinces rather than cities, such as the Atlantic Arc, the Mediterranean Arc, and the Channel Arc, which are other types of cross-border cooperation. The aforementioned urban networks are closely linked with European planning policies promoting a better regional balance, such as the Nordregio project being in fact part of the Interreg IIc programme. All projects have in common to be a lever for socio-economic development, based on the idea that single citiesespecially the small and medium-sized onesare difficult to compete in a world dominated by so-called "global cities" and should think beyond their individualistic management.

A more top-down example is the case of France, where under the national planning policy, a total of 24 urban networks were created between 1989 and 2000, including no less than 107 local governments, principally as a counterforce to the centralization exerted by the Greater Paris region over the entire territory. Another example but more endogenous is the South Coast Metropole Partnership in UK, promoting a functional region in the 'shadow' of Greater London. This central southern region animated by its main urban centers was seen by its proponents as a more relevant planning unit than the traditional Southeast and Southwest administrative regions, which lacked decisional power. As such, urban networks constitute new institutions, conduct a common policy, in order to achieve synergy, reach a critical mass, complement their functions, and strengthen a coherent regional system, based on more or less geographic proximity [START_REF] Brunet | L'Europe des réseaux[END_REF]. An assessment of the success of such initiatives is difficult, given the diversity of cases, and the fact that many of them have been discontinued, often due to the changing political agenda of the concerned municipalities. Yet, some urban networking strategies proved to be efficient when focusing on a specific project rather than simply creating an "image" for potential investors, like the creation of a common university, airport, and missing motorway link, to name but a few examples.

Throughout the academic literature, the surge of studies on urban networks since the 1960s motivated scholars to summarize the field. They conclude to a dispersal of approaches and definitions, to such an extent that urban network research "does not represent a standardised and consolidated field of scholarship" as this approach varies "immensely in their research questions, scales of analysis, disciplinary perspective, and intended audiences" [START_REF] Derudder | Uncovering links between urban studies and network science[END_REF]. The urban network concept itself may be coined differently across the academic spectrum, from city network, city system, system of cities, urban system, but also various spatial forms such as conurbations and megalopolises. As stated by [START_REF] Derudder | Uncovering links between urban studies and network science[END_REF], the variation among existing studies comes from three main elements: the scale of analysis adopted, the urban processes captured, and the ontological status ascribed to the network under study. The crossing between network science and urban studies made it possible to consider urban networks as graphs (cf. graph theory) where cities are nodes or vertices and their mutual connections are links or edges [START_REF] Derudder | Network analysis of 'urban systems': potential, challenges, and pitfalls[END_REF]. We present below the different schools of thought and their evolution.

Interestingly, the pioneering studies of urban networks were closely related to spatial planning issues. Two main poles actively researched the properties of urban networks during the 1960s and 1970s, namely an Anglophone group and a Swedish group, both adapting quantitative methods of regional science to regional planning issues. The main innovation of this "first science of cities" was to shift from intra-urban to interurban dynamics, greatly inspired by the central place theory developed by Christaller and Lösch. Brian [START_REF] Berry | Cities as systems within systems of cities[END_REF]'s expression of "cities as systems within systems of cities" is emblematic of such a shift, following Edward Ullman (1954)'s horizontal definition of the urban network, which rested on three main elements: complementarity, economic opportunity, and distance. Alan [START_REF] Pred | City Systems in Advanced Economies: Past Growth, Present Processes, and Future Development Options[END_REF] provided a clear definition of the urban network that is still valid nowadays: a national or regional group of interdependent cities where changes in one city (e.g. economic activities, professional structure, wages or population) will affect the other cities. Based on such a relatively unified conceptual framework, geographers and regional scientists proposed numerous analysis of urban networks using various flow matrices, but mainly using urban population as the key variable to test the rank-size rule (or Zipf law) governing urban networks in both developing and developed countries, for instance to demonstrate their degree of centralization (primacy) or integration. Other studies looked at the diffusion of innovations across urban networks, with reference to the pioneering works of Hägerstrand (1953), mostly concluding to hierarchical tendencies whereby larger cities are first adopters before redistribution to smaller cities. The Swedish school was particularly keen in establishing direct links between national planning problems and urban network theories, based on the observation that population and economic activities were too much concentrated in Sweden's main urban centers. Authors such as Godlund, Öberg, Olsson, and Törnqvist, among others, produced several reports for the central governments aiming at understanding the spatial dynamics of information flows across the urban network, contrary to Anglo-Saxon scholars focusing mainly on physical flows and infrastructures (Peris, 2016). Another originality of Swedish geography was to interview businessmen to produce simulation models capable of predicting future urban network patterns, with reference to the organization theory, integrating additional data on commuting flows for instance. In the following decades, research on urban networks went through a fragmentation with the emergence of separated schools of thought having their own definition and theory on the matter [START_REF] Peris | The evolution of the systems of cities literature since 1995: schools of thought and their interaction[END_REF], sometimes in opposition to the aforementioned classic models. Each research domain often claimed to offer a 'new paradigm'. Yet, certain similarities can be found, especially given the growing interdisciplinary character of such researches in their use of quantitative methods such as network analysis. A French school around the geographer Denise Pumain emerged in the 1970s and 1980s, taking distance from classic models by referring to self-organization, synergetic, and coevolution, thereby formulating an "evolutionary theory of cities". Experiments using agent-based models and multivariate analysis were proposed, mainly looking at the distribution of urban population and transport networks across nations and continents over long time spans. Similarities can be found with what was coined the "new science of cities" promoted by Michael Batty in the United Kingdom, such as the reference to and use of biology and physics methods to describe urban networks, like scaling laws. Such laws are the statistical relationships between urban attributes and urban population across cities of a given country, which can be interpreted as expressions of the urban network's degree of centralization, especially for the most advanced activities (e.g. employment in research and development activities).

Another school emerged in the 1990s with reference to Jean Gottmann's (1961) work on the U.S. megalopolis. Improvements in transport and communication technologies, the fading role of distance, and the rise of the service economy as well as globalization motivated scholars to identify polycentric forms of urban development in various parts of the world, such as Northern Italy, the Randstad, and Kansai in Japan. The "city network paradigm" [START_REF] Capello | The city network paradigm: measuring urban network externalities[END_REF] is thus a criticism of the dominantly hierarchical conception of urban networks of the two previous schools. For such authors, cities are specialized in certain firms' activities and connect through horizontal linkages as a matter of complementarity, thereby generating positive externalities, vertical integration, cooperation, innovation, and synergy effects [START_REF] Camagni | Network urban structures in northern Italy: elements for a theoretical framework[END_REF]. The main geographical focus of this school is at the subnational level, searching for relevant examples of urban networks or "districts" having such properties, in close relation to spatial planning issues as said above.

Economics in general, and the New Economic Geography in particular, devoted its attention to the concentration and location of various urban activities, defining the urban network as "a collection of economic agents (consumers and firms) without or with limited spatial interactions, with static, comparative, and equilibrium methods as the basic core of the analysis" [START_REF] Ducruet | Cities and transport networks in shipping and logistics research[END_REF]. Based on the principle that distance does not affect the mobility of economic agents among cities, authors included the Dixit-Stiglitz assumptions of monopolistic competition and the null trading cost in their models, providing important economic mechanisms for understanding specialized and diversified cities. The second principle is iceberg costs, i.e. the increasing fraction of product price due to mobility. Yet in this school cities are considered as nodes in a linear or circle structure, in a so-called racetrack economy where distance remains neutral as "regions are equally spaced" (Abdel-Rahman and Anas, 2004). Related methodologies and applications often used spatial interaction and gravity models, and due to issues in explaining social behavior by natural science models, adaptations were made using more realistic tools such as spatial autocorrelation and heterogeneity. One important difference with other schools is the absence of reference to the physical flow itself linking cities, as this approach to urban networks is highly theoretical.

Lastly, an important change in the way urban networks are analyzed had been to shift the focus to "world city networks", having in common with the "city network paradigm" to focus on services location and firms' networks but at the global level. Such a school takes its roots in the works of Manuel Castells on the information society describing how spaces of flows are functioning, but also from previous works of John Friedmann and Saskia Sassen on the "world city" or "global city", concluding to the existence of a transnational urban system. These foundations provided strong support to the geographer Peter Taylor and his Globalization and World Cities (GaWC) Study Group and Network to provide numerous empirical analyses of such systems based on company data. Based on the interlocking network model applied to advanced producer services location across cities of the world, cities are ranked and classified to unravel the global urban hierarchy of alpha, beta, and gamma centers. The link with the emerging literature on global commodity chains and global production networks motivated scholars to study other types of linkages such as airlines but also specialized services like those related to maritime transport [START_REF] Jacobs | Integrating world cities into production networks: The case of port cities[END_REF]. Peter [START_REF] Taylor | External urban relational process: introducing central flow theory to complement central place theory[END_REF] even proposed a "central flow theory" in opposition to the central place theory which remained bound to the local or national scale and ignored the relational aspects of urban networks.

As argued by [START_REF] Ducruet | Network science and spatial science: review and outcomes of a complex relationship[END_REF] and [START_REF] Derudder | Network analysis of 'urban systems': potential, challenges, and pitfalls[END_REF], the network analysis of interconnected cities went through unprecedented change in the last two decades, following the growing integration of complex networks methods from physics into geography and other social sciences, but also the growing interest of physicists for cities and real-world networks. Far from being a school of thought per se, this methodological breakthrough, combined with increased computational power, the development of dedicated graph analysis software, and newly available data on interurban relationships permitted scholars to concretely measure and visualize the structure and dynamics of urban networks, thereby creating a dialogue or common ground among the different schools of thought. Such an approach first permitted to identify the global properties of urban networks, i.e. their resemblance to theoretical models such as the scale-free and small-world networks. It also allowed to compare cities based on their various centralities in the network [START_REF] Guimera | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF], and to extract, from a large network, different and strongly interconnected subsystems, to test, for instance, the existence of barrier effects such as distance or borders. Few analyses, however, tackled the difficulty to study multiple linkages at a time, or analyzed the urban network by considering the socio-economic characteristics of the connected cities. In the world maritime network of cities, since the late 19 th century, the most populated nodes remained dominant until new hubs emerged thanks to progresses in shipping and port technology as well as operational modifications, as shown per using single linkage analysis and assortativity measures [START_REF] Ducruet | Maritime networks as systems of cities: the longterm interdependencies between global shipping flows and urban development (1890-2010)[END_REF]. Other studies could show the connivance between urban Gross Domestic Product, population, and centrality in airline urban networks. When it comes to multiple linkages, studies often looked at the degree of overlap of at least two transport modes on nodes and on links, but without taking into account the characteristics of cities (see [START_REF] Ducruet | Cities in worldwide air and sea flows: A multiple networks analysis[END_REF][START_REF] Derudder | The connectivity of South Asian cities in infrastructure networks[END_REF]. Should it be in natural or social sciences, the complex networks approach remains usually rather static and does not consider node attributes. Thus, the future or urban network research should lean towards the analysis of a fully-fledged network where nodes and links have multiple characteristics and evolve overtime. Only then the full understanding of urban networks be possible, allowing to unravel how network diversity and dynamics affect urban growth and vice-versa.

SEE ALSO:

Graph Theory; Network Analysis; Spatial Networks; Transport Networks

Figure 1 :

 1 Figure 1: Evolution of schools of thought about urban networks Source: adapted from Peris (2016)