PaperlayerView exact revision on arXiv

Source-linked AI summary

Random planar graphs and the London street network

A. P. Masucci, D. Smith, A. Crooks, M. Batty

arXiv:0903.5440v1physics.data-anphysics.soc-ph

TL;DR

The paper asks how London’s street network can be understood through its physical layout and navigational information. It compares London with grid, static random planar, and growing random planar models, finding a self-organised compromise that balances spatial and informational effort.

  • Problem

    Planar urban networks and their interaction between geometrical structure and navigational information remain insufficiently explored, especially for growing systems.

  • Method

    The paper analyses London in primary and dual representations and compares it with grid, static random planar, and growing random planar graph models.

  • Results

    London’s network combines features of growing random and grid-like cities, while its primary and dual structures differ from random planar graphs.

  • Takeaways & Limitations

    The comparison supports viewing London as a self-organised system balancing the effort of spatial displacement against the information required for navigation.

Abstract

from arXiv · show

In this paper we analyse the street network of London both in its primary and dual representation. To understand its properties, we consider three idealised models based on a grid, a static random planar graph and a growing random planar graph. Comparing the models and the street network, we find that the streets of London form a self-organising system whose growth is characterised by a strict interaction between the metrical and informational space. In particular, a principle of least effort appears to create a balance between the physical and the mental effort required to navigate the city.

I. INTRODUCTION

The paper frames urban street networks as planar graphs whose primary and dual representations capture geometrical structure and navigational information. It introduces grid, static random, and growing random models to compare with London, emphasizing a balance between physical and mental effort.

  • Street networks model intersections and cul-de-sacs as vertices and connecting street fragments as edges in an embedded planar graph.
  • Existing research emphasized static planar graphs, so the paper introduces growing random planar graphs with more articulated properties.
  • The dual representation treats streets as vertices and intersections between streets as links, representing the network’s information content for navigation.
  • London is analysed in primary and dual representations alongside grid, static stochastic, and growing stochastic models.
  • 163878 intersections and 199931 street segments define the London network, whose average degree is approximately 2.44.
  • London street-segment lengths average 95.73mt and show scale-free properties over a long distance range with a finite-variance cutoff.

B. The Erd¨os-R´enyi Random Planar Graph

The Erdös-Rényi planar graph is a static random model built by connecting nearby random points only when proposed edges preserve planarity. A London-matched realization can remain highly disconnected.

  • The ERPG is presented as the conventional static random planar graph model in the existing literature.
  • It starts from Poisson-distributed points and repeatedly selects pairs within distance r for possible connection.
  • A candidate edge is added only if it does not intersect existing graph edges, until the target edge count or planar maximum is reached.
  • The London-matched realization contains 2072 disconnected components, with 146965 vertices in its largest component.

C. The Growing Random Planar Graph

The GRPG is a growing random planar graph designed to model urban growth through stochastic additions of non-intersecting segments and occasional local connections. Its parameters determine connectivity and, with London-matched inputs, produce long-range links, asymmetric structure, and connected networks.

  • C. The Growing Random Planar Graph: The GRPG extends static planar-graph models by introducing growth, producing properties that differ from those of the ERPG.The model is intended to represent cities as systems that assume their shape over centuries.
  • C. The Growing Random Planar Graph: At each step, the model selects an existing vertex and adds a segment of sampled length only if it intersects no existing segment.The initial process creates a tree planar graph.
  • C. The Growing Random Planar Graph: Every n time steps, the GRPG adds a non-intersecting edge between nearby existing vertices, raising its average degree to < k > = 2 + 2/n.The graph continues until the desired number of edges or vertices is reached, with properties determined by n and f(l).
  • C. The Growing Random Planar Graph: Using London-matched size, edge-length distribution, and n = 5, the GRPG permits long-range connections that create independent centres and an asymmetric overall form.Changing f(l) produces different city shapes.
  • C. The Growing Random Planar Graph: The GRPG has no unconnected components, unlike the ERPG.This is reported for the London-sized realisation of the model.

D. The Grid

The paper compares London’s street network with grid, static random planar, and growing random planar models across spatial, topological, and weighted measures. London differs from the random and grid benchmarks through radial density, degree, strength, and growth-related spatial patterns.

  • D. The Grid: The comparison covers topological, geometrical, cycle-space, and centrality measures for LN, ERPG, GRPG, and GM, while some ERPG and GM measures are omitted as trivial.The models provide ordered, static-random, and growing-random reference systems.
  • D. The Grid: London’s intersection density has a plateau to approximately 3.5Km, drops rapidly to around 7Km, then decays linearly toward the periphery.The GRPG instead has a smooth bell-shaped density profile that decays rapidly to around 15Km.
  • D. The Grid: The GRPG matches London’s average road-fragment length well for the first 15Km, while both networks have longer edges farther from the centre.Large GRPG fluctuations at large radius are attributed to finite-size effects.
  • D. The Grid: London’s degree distribution peaks more sharply than ERPG’s, with maximum degree 8 for LN versus 12 for ERPG; GRPG shows exponential behaviour with kmax = 24.The paper relates London’s non-exponential degree distribution to its particular organisation as a growing system.
  • D. The Grid: London’s strength distribution has scale-free exponent −3.87±0.06, whereas ERPG has a peaked distribution with an exponential tail and GRPG shows less-defined scale-free behaviour.Strength is defined from the lengths of street fragments incident at each vertex.
  • D. The Grid: Average degree declines linearly with radius in London and more rapidly in GRPG, while ERPG and GM remain constant; central vertices are therefore more densely connected.The radial decay is described as a signature of system growth.

B. Measures in the cycle space

Cycle-space measures describe polygonal structure through cycle lengths and face areas. London and the GRPG share radial growth patterns, but London has distinctive cycle frequencies, longer tails, and a face-area distribution also found in other stochastic networks.

  • B. Measures in the cycle space: Cycle length Cl is defined as the number of edges or vertices in a closed polygon, providing a measure of graph geometry.The cycle space consists of edges belonging to closed polygons.
  • B. Measures in the cycle space: Cycle-length distributions for LN, ERPG, and GRPG have power-law tails with a similar exponent of -3.The grid model’s cycle space is trivial.
  • B. Measures in the cycle space: London contains more cycles of length 4 and 5 than of length 3, and its cycle-length tail is much longer than those of the random networks.The paper associates this difference with geographical constraints, including large polygons around the Thames.
  • B. Measures in the cycle space: Average cycle length grows with distance from the centre in both LN and GRPG, with London’s increase steadier and well fitted by a linear function.The large-radius decline is attributed to finite-size effects.
  • B. Measures in the cycle space: London’s face-area distribution agrees with Dresden’s road network, but similar behaviour in stochastic networks suggests it is not by itself evidence of urban self-organisation.The paper cautions against treating this power law as a unique marker of complex urban organisation.
  • B. Measures in the cycle space: Average face area increases with radius in LN and GRPG, while it is constant in ERPG, supporting a strong monocentric component in city growth.Fluctuations also increase with distance from the centre.

C. Centrality measures

The paper uses inverse closeness centrality as an average metric distance from an intersection to all others, comparing travel friendliness across London and three models.

  • C. Centrality measures: 1/CC represents the average metric distance between an intersection and all other intersections, providing a measure of physical effort in navigation.The distance is measured in kilometres.
  • C. Centrality measures: The ERPG is the least travel-friendly network, with most vertices on a 30Km–46Km plateau.This distribution considers the connected portion of the network.
  • C. Centrality measures: The ERPG has lower centrality than the GM, whose plateau lies between 26Km and 37Km and has an exponentially falling tail beyond 10Km.
  • C. Centrality measures: The GRPG is described as the most travel-friendly pattern, with a peak around 13 km and a smooth decay to 32km.Its city is smaller in extent than the other models.

III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM

The dual representation converts roads into vertices connected at intersections, making street alignment central to how the network captures navigation information.

  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: A dual street network assigns common IDs to fragments belonging to the same road, then represents roads as vertices connected when they intersect.Figure 11 illustrates this conversion from a street graph to a dual graph.
  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: Long roads become hubs because they intersect many roads, whereas short roads and dead-ends have few connections.This produces hubs across scales and a characteristic degree-distribution shape.
  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: Street-name alignment is problematic because identical names can identify disconnected streets, while one physical street can have multiple names.
  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: ICNP extends ICN by applying the largest-convex-angle rule to nonadjacent segments and assigning the same ID to adjacent segments forming that angle.Other intersecting segments retain distinct IDs.
  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: The resulting unweighted, undirected information network measures navigation through road changes rather than individual street segments.Its diameter represents the maximum information required to cross the city.
  • III. THE DUAL REPRESENTATION AND THE ALIGNMENT PROBLEM: Any alignment algorithm introduces bias; London’s longest recognised road is about 17Km, while routes such as the M25 and A40 are not recognised as single roads.The authors note that these biases affect the degree distribution.

IV. DUAL ANALYSIS

The dual-analysis section examines London and model networks as purely topological binary networks, focusing on degree distribution, clustering, and related properties.

  • IV. DUAL ANALYSIS: The analysis compares the dual networks of London, the ERPG, the GRPG, and the Grid Model using topological measures.These networks are not embedded in Euclidean space per se.

A. Topological properties

The dual networks differ substantially in degree distributions, clustering, correlations, and global topology, with London showing distinctive organisation relative to random planar models.

  • A. Topological properties: The dual-network table reports vertices, edges, average degree, diameter, and average clustering coefficient for London and the three models.
  • A. Topological properties: London has more roads than the random networks but a much smaller diameter, indicating more efficient spatial organisation than random roads.The random-network diameters are of logarithmic order in their vertex counts, a small-world property.
  • A. Topological properties: London’s dual degree distribution shows power-law behaviour with a fat tail, while the stochastic models show exponential behaviour.The growing random planar graph retains a fat tail at kMax = 229.
  • A. Topological properties: The maximum degree is kmax = 20 for the DERPG, compared with kMax = 261 for the DLN and kMax = 229 for the DGRPG.The authors associate the larger degrees in the growing model with longer roads.
  • A. Topological properties: London’s average clustering coefficient follows a power law with exponent −0.89 ± 0.01 and has low average clustering, < c >≈0.04.The sparse triangles reflect predominantly orthogonal roads and more frequent cycles of length 4 or 5 than 3.
  • A. Topological properties: The DGRPG has average clustering < c >≈0.4 and the DERPG < c >≈ 0.31, both about an order of magnitude above London’s value.The random networks therefore contain more triangles than the urban network.
  • A. Topological properties: The nearest-neighbour degree is compared with a degree-preserving randomised London network to distinguish structural correlations from effects of the degree distribution.The London dual network exhibits disassortative correlations in this comparison.

B. Centrality measures

Shortest-path distributions quantify navigational information, while betweenness centrality characterizes road hierarchy across London and planar-graph models. London occupies an intermediate navigational position between grid-like and random models.

  • Shortest-path distributions: Shortest paths measure mental effort in navigation; London’s distribution lies between the grid model, easiest to navigate, and random models, most difficult.For London, P(d) is Gaussian with centre pc = 11.74 ± 0.05 and width σ = 7.14±0.09.
  • Shortest-path distributions: The grid model has a much lower average information requirement, with P(d) centred at pc = 3.940 ± 0.006 and width σ = 0.230 ± 0.001.Its distribution is well fitted by a lognormal distribution.
  • Shortest-path distributions: The growing random planar graph has a Gaussian P(d) centred at pc = 22.70 ±0.02 with width σ = 20.1±0.3.The distribution remains Gaussian, although its tail behaves slightly differently.
  • Shortest-path distributions: The Erdős–Rényi random planar graph requires substantially more mental effort, with its distribution centred at pc = 96.9 ± 0.3 and width σ = 99.0 ± 0.7.Its tail decays faster than the Gaussian curve.
  • Betweenness centrality: Betweenness centrality measures how often vertices participate in shortest paths and describes the hierarchy of centrality in the dual networks.The measure is zero for degree-one vertices, which represent dead-end roads, and is normalized relative to the central vertex of a star graph.
  • Betweenness centrality: The dual London, static random planar, and growing random planar networks show scaling betweenness-centrality distributions, whereas the figure compares their classifications with the grid model.The supplied figure passage identifies Gaussian and lognormal fits for path distributions and a semi-log scale for resolving tails.

V. CONCLUSIONS

The paper compares London’s primary and dual street-network representations with grid, static planar, and growing planar models. It concludes that London exhibits complex organization and that a growing random planar graph is the best null model for its correlations and properties.

  • V. CONCLUSIONS: The study develops primary and dual representations of large-city street networks and introduces grid, static planar, and growing planar graph models for comparison.The growing planar graph is presented as a new model for this kind of urban analysis.
  • V. CONCLUSIONS: The growing random planar graph is identified as the best null model for understanding correlations and properties of London’s street network.Many geometrical and topological features of London are described as emerging properties of a growing system.
  • V. CONCLUSIONS: London’s primary degree distribution differs from the exponential distribution of the growing random planar graph, indicating organization beyond planarity alone.The paper also reports richer topological and geometrical properties in planar graphs when examined in cycle space.
  • V. CONCLUSIONS: In the dual representation, London has a scale-free degree distribution, while random planar graphs have exponential distributions.The paper interprets London’s scale-free distribution as a signature of complex organization in information space.
  • V. CONCLUSIONS: The grid is easy to navigate informationally but costly metrically, whereas the growing random planar graph is easier metrically but difficult informationally.London appears to balance physical and mental navigation effort through interaction between its primary and dual representations.

APPENDIX A: THE LONDON STREET NETWORK

The London street network was constructed from two Ordnance Survey products selected to balance road coverage with geometric detail. The analysis begins from a planar graph whose edges have distinct identifiers.

  • APPENDIX A: THE LONDON STREET NETWORK: The London network was derived from the Ordnance Survey MeridianTM 2 and Integrated Transport Network datasets.MeridianTM 2 includes motorways, A roads, B roads, and minor roads; ITN includes these in greater detail.
  • APPENDIX A: THE LONDON STREET NETWORK: The ITN dataset contains detailed geometry, including traffic islands and roundabouts, resulting in more edges and vertices.The paper explains that many such details were unnecessary for the analysis.
  • APPENDIX A: THE LONDON STREET NETWORK: The network construction starts with a planar graph G = {V, E} in which every edge has a different label or ID.This provides the formal graph basis for the street-network representation.
Loading 0903.5440v1…