Information measures and cognitive limits in multilayer navigation

Riccardo Gallotti points me to this interesting working paper in arXiv:

Information measures and cognitive limits in multilayer navigation

Cities and their transportation systems become increasingly complex and multimodal as they grow, and it is natural to wonder if it is possible to quantitatively characterize our difficulty to navigate in them and whether such navigation exceeds our cognitive limits. A transition between different searching strategies for navigating in metropolitan maps has been observed for large, complex metropolitan networks. This evidence suggests the existence of another limit associated to the cognitive overload and caused by large amounts of information to process. In this light, we analyzed the world’s 15 largest metropolitan networks and estimated the information limit for determining a trip in a transportation system to be on the order of 8 bits. Similar to the “Dunbar number,” which represents a limit to the size of an individual’s friendship circle, our cognitive limit suggests that maps should not consist of more than about 250 connections points to be easily readable. We also show that including connections with other transportation modes dramatically increases the information needed to navigate in multilayer transportation networks: in large cities such as New York, Paris, and Tokyo, more than 80% of trips are above the 8-bit limit. Multimodal transportation systems in large cities have thus already exceeded human cognitive limits and consequently the traditional view of navigation in cities has to be revised substantially.

My take is this greatly supports things like Grid networks and network simplification (see the work of Jarrett Walker). This looked at rail. Think about buses. In a few years, people will just let their apps navigate them, and human cognition limits may fall off the chart.

Accessibility Analysis of Risk Severity

Recent working paper

Risk severity in transportation network analysis is defined as the effects of a  link or network failure on the whole system. Change accessibility (reduction in the number of jobs which can be reached) is used as an integrated indicator to reflect the severity of a link outage.  The changes of accessibility before-and-after the removing of a freeway segment from the network represent its risk severity. The  analysis in the Minneapolis – St. Paul (Twin Cities) region  show that links near  downtown Minneapolis have relative higher risk severity than those in  rural area. The geographical distribution of links with the highest risk severity displays the property that these links tend to be near or at the intersection of freeways. Risk severity of these links based on the accessibility to jobs and to workers at different time thresholds and during different dayparts are also analyzed in the paper. The research finds that network structure measures: betweenness, straightness and closeness, help explain the severity of loss due to network outage.

Keywords: GPS data, congestion, network structure, accessibility

Accessibility and the Ring of Unreliability

Recent working paper

Abstract: This study measures the variability of job accessibility via automobile for the Minneapolis-St. Paul region. The accessibility analysis uses cumulative opportunity measures. The travel times on the network are tested at various level (10th percentile speed, 50th percentile speed, 90th percentile speed) using the TomTom speed data for 2010. It is shown that accessibility varies widely day-to-day as travel speeds on the network vary. Some parts of the region (a ring around the core) have more volatility in accessibility (and are thus less reliable) than others.

Keywords: GPS data, congestion, network structure, accessibility, reliability

Grids are for squares: Three reasons to consider alternatives to rectilinear street networks

Just as we have cut the earth into a grid of latitude and longitude (and knowing that each “block” of 1 degree latitude by 1 degree longitude gets smaller and smaller as we approach the poles), we similarly cut our cities and rural areas into a finer mesh from that same grid. Much of this arises from the various large scale ordinance surveys that took places in the Americas, Australia, and India. There are of course grids dating much earlier, to Miletus and Mohenjo Daro among many others. Not all grids are aligned with longitude and latitude, sometimes they align with local landscape features, but most of the modern ones are. (Where grids of different alignments come together, interesting spaces are created). Not all grids are squares, most are more like rectangles.

So why should we have 90-degree rectilinear grids?

The arguments in favor are that it:

1. simplifies construction and makes it easier to maximize the use of space in buildings,
2. simplifies real estate by making the life of the surveyor easier,
3. simplifies intersection management by reducing conflicts compared to a 6-way intersection,
4. is embedded in existing property rights and so impossible to change.

We in the modern world need not be bound to the primitive tools of the early surveyor, the primitive signal timings of the 1920s traffic engineer, or the primitive construction techniques of early carpenters. And while for existing development we might be locked into existing property rights, for new developments that doesn’t follow.

The arguments against the rectilinear include that it:

1. is among the least efficient way to connect places from a transportation perspective,
2. reduces opportunities for interesting architecture,
3. wastes developable space by overbuilding roads.

There are many designs for non-rectilinear street networks. Ben-Joseph and Gordon (2000) (Hexagonal Planning in Theory and Practice (Journal of Urban Design 5(3) pp.237-265)) summarize a number of the 19th and 20th century designs. Most are simple aesthetic choices, as in Canberra, the planned capital city of Australia, and don’t seem to relate to deeper urban organizational issues.

Rudolf Müller proposed The City of the Future: Hexagonal Building Concept for a New Division. Müller’s plan offsets the 60-degree streets so that they come together in 4-way rather than 6-way intersections (though they are still at 60-degrees and not bent to make 90-degree intersections). This ensures that the cells in the plan are not bisected by roads, and that they are instead hexagonal blocks. This plan loses a lot of areas to ornamental parks in the middle of streets.
The circuity increase associated with a 90-degree rather than 60-degree network is obvious. Circuity (the ratio of Euclidean to Network distance) would be minimized if roads were at 0-degree angles. The downside is that this Euclidean network where everyone traveled in a straight-line would literally “pave the earth“. Leaving aside the downsides for the environment of being so-paved, the more critical trade-off from a transportation perspective is construction costs. More roads are more expensive. So a network design trades-off travel costs accruing over time with the up-front construction and long-term maintenance costs. The optimal network design depends on the land use pattern it aims to serve. (And the land use pattern depends on the network design.) The City of Alonso or Von Thünen, with all jobs downtown merely requires a simple radial network to connect it. A polycentric or fully dispersed (homogeneous) city with everything spread uniformly across space begs for more cross-connections.

Charles Lamb’s City Plan has the streets hexsect the hexagonal cells. In this case, the blocks are really triangles.

There is a large literature on the network design problem. One useful paper: Pierre Melut and Patrick O’Sullivan (1974) A Comparison of Simple Lattice Transport Networks for a Uniform Plain, Geographical Analysis 6(2) pp. 163–173, says:

The objective is to compare construction and transport costs for triangular [60-degree], orthogonal [90-degree], and hexagonal [120-degree] regular lattices as transport networks serving a uniform, unbounded plain. The lattices are standardized so that the average distance from the elementary area to the edge is the same for each. This standardization results in equal construction costs for the three networks; thus, the comparison can be made in terms of route factors [circuity], which favors the triangular lattice over the other two.

Because the circuitous network is less efficient, more network pavement and track and vehicle mileage must be provided to enable the same amount of transportation.

This wastes spaces that could be better allocated to non-transportation purposes.
The lattice itself comprises a single level in a hierarchical system. Selected links in a lattice can be reinforced to make them faster, attracting traffic. This process of reinforcement is natural with investment rules that favor more heavily trafficked routes and explains the hierarchy of roads. If it is based on simple reinforcement of existing links rather than creation of new links, that hierarchy will not affect the topology of the network.

Ask MetaFilter has an interesting thread on Comparing perimeters of arrays of hexagons vs. squares – geometry tiling resolved . A key point is that arranging hexagons into a square-like shape has a higher perimeter than arranging squares into a square-like shape.

__    __    __    __    __
/  \__/  \__/  \__/  \__/  \
\__/  \__/  \__/  \__/  \__/
/  \__/  \__/  \__/  \__/  \
\__/  \__/  \__/  \__/  \__/
/  \__/  \__/  \__/  \__/  \
\__/  \__/  \__/  \__/  \__/
/  \__/  \__/  \__/  \__/  \
\__/  \__/  \__/  \__/  \__/
/  \__/  \__/  \__/  \__/  \
\__/  \__/  \__/  \__/  \__/
Diagram 1. Sample hex map

Jellicle wrote:

I think your problem is this – to minimize the perimeter of n hexagons, when you add each new hexagon to the previously-existing group, you have to add it in such a way that touches the most neighbors possible. You would never add a hexagon that touches only on one face if you could add it somewhere else where it touches two faces or three faces, right? If you look at diagram 1 here (which is hexes in a grid shape), you see several hexes at the four corners which touch only on two faces, while there are areas on the outer surface at the top and bottom where those hexes could be placed where they would touch on three faces instead of two. So simply moving those four corner hexes would reduce the perimeter without changing the surface area.

Yet we know the hexagon is efficient, it replicates the closest packing of circles. (Take a penny, surround it with pennies so that they are all tangent. The central penny touches six others.) Thus following the closest-packing argument, the hexagon as geometrical shape is not sufficient for efficiency, we must also arrange those shapes into an efficient pattern, in this case, something more like the Glinski Chess Board:

Much of the inspiration for thinking about hex-maps comes from the gaming community, where such maps have been used since the 1961, when a Hex map was used for the Avalon Hill game Gettysburg. It has since become a standard that is widely used to represent directions of movement in games.

So, although we talk about “grids” as being necessary for connectivity, we can get even more connectivity if we think about a variety of different geometries. It would be a shame if we got locked into grid geometries for new developments when there are so many alternatives to be had.

Network Structure and City Size

Network structure varies across cities. This variation may yield important knowledge about how the internal structure of the city affects its performance. This paper systematically compares a set of surface transportation network structure variables (connectivity, hierarchy, circuity, treeness, entropy, accessibility) across the 50 largest metropolitan areas in the United States. It finds most of these measures vary with city size. A set of scaling parameters are discovered to show how network size and structure vary with city size. These results suggest that larger cities are physically more inter-connected.
Keywords: Connectivity, Network Structure, Transportation Geography, Network Science, City Size, Scaling Rules

Network Structure and Travel

Congratulations to soon to be Dr. Pavithra Parthasarathi, who recently was awarded the 2011 John S Adams Award for Excellence in Transportation Research and Education, and who successfully defended her Ph.D. Thesis “Network Structure and Travel” (a draft of which is linked) on May 5, 2011. She accepted a job with the Hampton Roads Transportation Planning Organization (HRTPO) in Norfolk, VA, starting May 16th.

Abstract:

Changing the design aspects of urban form is a positive approach to improving transportation. Land use and urban design strategies have been proposed to not only to bring about changes in travel behavior but as a way of providing a better quality of life to the residents. While the research on the relationship between urban form and travel behavior has been pretty extensive, there is a clear gap in the explicit consideration of the underlying transportation network, even though researchers acknowledge its importance. This dissertation aims to continue on the research interest in understanding travel behavior while explicitly accounting for the underlying transportation network structure.

Transportation networks have an underlying structure, defined by the layout, arrangement and the connectivity of the individual network elements, namely the road segments and their intersections. The differences in network structure exist among and between networks. This dissertation argues that travelers perceive and respond to these differences in underlying network structure and complexity, resulting in differences in observed travel patterns. This hypothesized relationship between network structure and travel is analyzed in this dissertation using individual and aggregate level travel and network data from metropolitan regions across the U.S. Various measures of network structure, compiled from existing sources, are used to quantify the structure of street networks. The relation between these quantitative measures and travel is then identified using econometric models.

The underlying principle of this research is that while the transportation network is not the only indicator of urban form and travel, an understanding of the transportation network structure will provide a good framework for understanding and designing cities. The importance of such an understanding is critical due to the long term and irreversible nature of transportation network decisions. The comprehensive analyses presented in this dissertation provide a clear understanding of the role of network design in influencing travel.

A Numeric Topology of the United States Eisenhower Interstate Highway System

Hedberg Maps makes “A Numeric Topology of the United States Eisenhower Interstate Highway System “ which looks quite cool, though is not quite free. A full discussion is here

The interstate system has another quality besides the creation of corridors, boundaries and districts: it orders and grids the country. In creating the basic numbering plan for the highways, its creators followed a tradition that includes not only previous highway systems (including the 1920’s U.S. Highway System), but street layouts dating back to William Penn’s Philadelphia, the initial “nine squares” of New Haven, and the very definition of United States territory, the 1785 Land Ordnance with its grid of 6 x 6 mile townships. It has become so common for American cities to lay out streets in a square grid with numerical names that it can be surprising to go to countries where this practice is unknown. Learning to navigate even older American cities like Boston, where what grids there are are haphazard and streets change names seemingly at whim, can be daunting to those raised in orderly Omaha or Chicago.

….

Some ground-rules quickly emerged:

• I would try to keep the “5-roads” as my guideposts and conform everything else to them (but what do you do when 1-80 and 1-90 become one road in Ohio and Indiana?)
• One roadway = one line.
• Two-digit routes would be drawn with a heavier line weight than three-digit routes. Where they share a pathway, the heavier line takes priority.
• State boundaries would be topologically correct: every road intersection and state boundary road crossing would be shown in the correct order.
• Odd-prefix three-digit routes (i.e spurs like I-394) would be shown as straight lines, and even ones (i.e. loop roads like I-494/694) would be made of circular arcs.
• As much as graphically feasible, routes would be encouraged to lie along their numbered place in the grid for as much of their length as was graphically feasible.
• A minimum of 1⁄4 inch would fall between each major intersection. Mostly.
• I would use only straight line segments and arcs. No other curvy bits.

Debunking Theories of a Terrorist Power Grab

Network Reliability on the Electric Grid (from Miller-McCune Debunking Theories of a Terrorist Power Grab

Hines and Blumsack’s study … shows that the most vulnerable points are the ones that have the most energy flowing through them — like huge power stations or highly connected transformers.

Article Do topological models provide good information about electricity
infrastructure vulnerability?

I think there is something to learn about generalizing network reliability and vulnerability across fields (electricity, transportation, etc.). Network structure, and the underlying technology, matter.

A Positive Theory of Network Connectivity

Recent working paper:

This paper develops a positive theory of network connectivity, seeking to explain the micro-foundations of alternative network topologies as the result of self-interested actors. By building roads, landowners hope to increase their parcels’ accessibility and economic value. A simulation model is performed on a grid-like land use layer with a downtown in the center, whose structure resembles the early form of many Midwestern and Western (US) cities. The topological attributes for the networks are evaluated. This research posits that road networks experience an evolutionary process where a tree-like structure first emerges around the centered parcel before the network pushes outward to the periphery. In addition, road network topology undergoes clear phase changes as the economic values of parcels vary. The results demonstrate that even without a centralized authority, road networks have the property of self-organization and evolution, and, that in the absence of intervention, the tree-like or web-like nature of networks is a result of the underlying economics.