Networks as Connectors and Disconnectors

2021-05-112021-05-11 | David Levinson

We often talk about networks providing connection. The World Wide Web is a network that connects people with websites across the world. But interesting word “web”, it is appropriated from a spider’s “web“, which has lots of strands that connect internally and to external supports, and enable the spider to move quickly over space. But the spider “web’s” primary purpose is to tangle up the wayward insect that crosses its path and prevent it from traveling further. That meaning of the word comes from a further word describing woven fabrics, weaving, and tapestry. Weaving of clothes is of course aimed at preventing cold air from reaching the body and provides insulation.

We could look at the word “net”, it is appropriated from a fisherman’s net. “Open textile fabric tied or woven with a mesh for catching fish, birds, or wild animals alive; network; spider web,” also figuratively, “moral or mental snare or trap.” So it too has the connotation of restricting movement rather than facilitating it.

Ther term “grid” comes from griddle, a device for keeping things from falling into the fire (while spreading heat along its elements).

Building frames are types of networks to transmit force between the structure and the earth to provide support. But these supports are rigid and generally prevent going through them, requiring people to go around. Normally this isn’t a big deal in a steel frame building, where the supports take a minimum of space, but in masonry or wood structures, the supports are pretty coterminous with walls, and individuals must find doors for passage. The walls and ceilings themselves, like woven clothing, protect the occupant from the vagaries of the environment.

Modern transport networks have much the same features as a spider’s web. Roadways are designed to facilitate movement for cars while trapping pedestrians who want to cross the street. Cars don’t literally eat pedestrians, but this environment certainly reduces the number of pedestrians, as people who would otherwise walk give up and join the motoring majority. We might say automobility eats walk mode share.

Wired power networks impose their own constraints. High voltage power lines are not to be touched, for instance. But they occupy little space. They do require the clearance of trees, disconnecting the dense bush in places, for the benefit of users of long-distance electricity. Power boxes often interrupt footpaths (needlessly).

Wired communications networks don’t have the same voltages, but still have physical constraints. Boxes for communications need to be accessed, leading to works in the transport network.

The disconnection wrought by communications may be more intangible. For every minute someone is engaged with distant people online (or even colleagues two desks away), they are not engaged with anyone who may be directly in front of them. In person contact has dropped as online has risen. For those not online, their available world is shrinking. I don’t know if this is a problem of the modern world, but it is a feature. Just as automobility enabled further suburbanisation and increasing distances between buildings, worsening the environment for those without a car, the always online world increases the effective physical distance between people, reducing the opportunities for those not on-board with the new technology.

We don’t weep too many tears for those stuck on AOL or Friendster or Orkut or Myspace or Google Plus or the Blogosphere, in a few years this will be Facebook (I hope) and Twitter, and eventually Insta et al., as the Cool Cycle continues its relentless march. The cool kids can’t be caught dead on the same network (wearing the same clothes) with the less cool kids (or their grandparents), and will migrate elsewhere. Being on different networks helps people differentiate their status, but that differentiation is a disconnection, slowing the flow of real ideas and information for the sake of social standing and relative positioning.

Once we have achieved communications saturation, for every increasing network online, producing network externalities for its members, it a world with a fixed time budget, some other physical or virtual social network is shrinking in either membership, attention, or both. Whether we have reached communications saturation is an empirical question, and perhaps brain to brain links will demonstrate how much further we have to go to create a truly social species, but it is feeling pretty saturated to me.

Gradial: Or the Unreasonable Network

2019-09-102020-01-02 | David Levinson

The reasonable network adapts itself to the world; the unreasonable one persists in trying to adapt the world to itself. Therefore all progress depends on the unreasonable network.¹

The physical location of network infrastructure is one of the most permanent decisions cities make. The Cardo Maximus in the old city of Jerusalem is still a main north-south shopping street, constructed when Emporer Hadrian rebuilt the city in the 130s CE.

A street right-of-way, once created is seldom destroyed. A segment of that infrastructure is designed to be optimal at a moment of time, with a particular land use (either the realized development of today or an imagined place of tomorrow), enmeshed within a particular network context of all the other nodes and links, compatible with a particular technology. That it functions at all when land use, networks, and technologies change radically, as they do over centuries, is testament to the general flexibility inherent in networks. But the implication is that if it is optimal for the world in which it was designed, it is unlikely to be optimal as that world changes.

Some adaptations do occur. Streets designed for horses were adapted for streetcars (trams) and bicycles and cars and buses and pedestrians.

Still, it may be the best that can be done. Embedded infrastructure, the dictionary example of sunk costs,² cannot adapt much to the world around them. Instead we expect the world to adapt to the infrastructure.

Following Shaw, we might say such infrastructures are `unreasonable’, in that they cannot be reasoned with.

Many, if not most, planned cities have been laid out with a network of streets “with the sombre sadness of right-angles,” as Jules Verne, quoting Victor Hugo, described the American grid in Salt Lake City, of streets at 90-degree angles to each other, in his classic road trip story: Around the World in 80 Days. Street grids don’t plan themselves, so while all street grids were planned, not all plans result in street grids.

Organically developed³ cities are often more naturalistic, radial cities, with streets feeding the city from the hinterlands, allowing more than 4-directions of entry. All roads lead to Rome, as the saying goes. The Romans themselves were a bit adverse to this organic radial system once they got their own growth machine going, laying out encampments and new settlements on the grid system. The radial system leading to and from the town would bend once it reached the town gates. But as cities themselves were generally not conceived of as whole, but rather themselves emerged, often as conurbations of smaller settlements, towns, and villages, there are often radial webs centered on town A overlapping radial webs centered on town B. Rome was famously built on seven hills, which can be read as meaning Rome is a conurbation of seven earlier villages. (See Elements of Access, Chapter 3.3)

Each of these networks typologies has its advantages and disadvantages.

DCMetro — Washington DC Metro. The center is a space, not a point. A `triangle’ is formed by L’Enfant Plaza (Yellow/Green with Orange/Blue/Silver), Metro Center (Red with Orange/Blue/Silver), and Gallery Place (Red with Yellow/Green)

We observe that radial networks are optimal to maximize access for many-to-one types of movements (suburbs to central city). So rail transit networks, which serve the high loads demanded by, and making possible, high density city centers tend toward being radial. But when they are large they are usually not so radial that all the branches meet at one junction. From a network design perspective, intersecting more than two lines at a station can lead to other types of conflicts, and many systems are designed with triangular center to avoid overloading a single transfer station. Washington DC’s largely radial Metrorail system, shown in the first figure, illustrates this design. Cities are spaces, not points.

In contrast, the 90-degree grid is reasonably well-suited to maximize access for scattered trips, what network analysts would call a many-to-many pattern. We see this especially in dispersed point-to-point (suburb to suburb, within city to within city) flows that are enabled by and reinforce the grid. This is the network for the automobile. The Los Angeles freeway grid, the famous Milton Keynes arterial grid, and numerous other late twentieth century cities have been designed in a grid-like way (though not so orthogonal that Victor Hugo would object). Even though the topology is not as efficient from a distance perspective as say a 60-degree mesh, by remaining out of the city core it can keep speeds higher.

But in response to the landscape that emerged with the automobile, transit planners like Jarrett Walker (2012) have called for more grid-like transit networks, so people can move, via public transport, from suburb to suburb without going through the city centre. This is relatively easy to reconfigure for buses, the very definition of mobile capital, while very difficult for the more capital intensive rail networks with their physically embedded infrastructure.

Still, core radial lines will always be the backbone of transit systems so long as at least one important center justifies a disproportionate amount of service.

So how can we grid the radial, or square the circle, so to speak?

A better network topology might be the 60-degree, hexagonal pattern. (Ben Joseph 2000) But remaking street grids for existing cities is tough-going, as property rights are well established, and requires efforts like those of Haussmann in 19th century Paris. (Willms 1997).

daganzo — Possible system layouts: (a) hub-and-spoke; (b) grid; (c) hybrid. Source: Figure 1 in Daganzo (2010)

Instead, we have overlapping network topologies, ideally which are grade-separated in some fashion, so trains are radial and don’t intersect streets or motorways, and bus services can be more grid-like, and rapid or express bus networks serve the market niche in-between.

Thus the original street level networks are still topologically grids, but the services running on that grid, while still largely parallel and perpendicular, are compressed near the center, so the bus lines, for instance, bend towards the center, as illustrated in the second figure. The regulatory layer of through streets for automobiles may be constructed to defer to the orientation of bus services.

There are no optimal network configurations independent of the enveloping land use pattern or the technological regime. Similarly there are no optimal land use allocations independent of the network pattern or technology. Finally, there is no optimal mode independent of the land use or network. All three of these systems are interlocking. Moving one requires adapting the others.

The unreasonable network forces the land use pattern to adapt to it, such that relocating network elements is more costly than keeping them in place. Similarly, in many ways the network, designed for a given technology, is very hard to adapt to a different technology. That doesn’t stop people and cities from trying, the misfit we see with the automobile in the urban core is the product of failing to acknowledge this unreasonableness. But as the number of European cities restricting cars in the city center are showing, the unreasonable network wins out over technology too.

The Grid/Radial Gradial network is also Gradual. These systems seldom change all-at-once, instead they gradually evolve over decades, centuries, and millenia.

Notes:

1. This is an adaptation of a famous George Bernard Shaw quote.

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable man.

2. The economist’s adage that “sunk costs are sunk” means that once something has been built, and that money spent, it no longer factors into benefit-cost analysis about how prospective decisions should be made, except to the extent it changes the costs of various options. Logically, you shouldn’t go to a concert just because you bought tickets if you don’t want to go, though if you are considering going to a concert or a bookstore after you bought the tickets, you don’t need to account for paying for the tickets again. You might also consider the `opportunity cost’ of going as the loss from not scalping the tickets. You shouldn’t throw good money after bad. But the sunk infrastructure cannot be unbuilt.

3. Organic development is often largely systematically unplanned, though obviously some degree of planning often goes into laying out a street, even if it is disjoint from any other decisions. When we think of `planning,’ we are generally referring to longer-term more strategic type spatial plans, that consider interactions between prospective decisions, rather than short-term tactical plans that optimize a single decision alone decontextualized from the rest of the city.

On Hypo- and Hyper-connectivity in Transport

2019-04-102019-04-05 | David Levinson

Connectivity is good. Is more connectivity better?

During the early stages of a useful technology like roads or transit, adding links generally adds more benefits than costs. However there are limits. A four way intersection is good does not mean a five way intersection (or six or seven) is necessarily better. The more complex intersection adds to the friction of travel and cost of construction over its simpler alternatives.

Muller's Hexagonal Network — Muller’s Hexagonal Network

A grid network, with streets at 90-degree angles to each other might not be as good as a network with streets at 60-degree angles, which reduces travel costs and increases directness (reduces circuity), but it is most assuredly better than a fine mesh with streets at 10-degrees or 1-degree, where almost all is pavement and little is actually buildable land. While 1-degree network would reduce surface travel distance, it does so at many other costs, including a reduction in accessibility because of fewer development opportunities.

Consider the circuity additions based on network angle. If all places are connected via a 90-degree square grid, the circuity at worst is SQRT(2), but on average 1.21. So travel distance increases by 21% over a straight-line path. With a 60-degree grid, the circuity is lower, at worst 1.22, on average nearer 1.11. (Bus transit networks, which tend not to follow the shortest path, have much worse circuity.)

The optimal level of connectivity depends on what you are trying to optimize.

Hypo and Hyper are antonyms. Wiktionary says:

Hypo: From Ancient Greek ὑπο- (hupo-), combining form of ὑπό (hupó, “under”).
Hyper: From Ancient Greek ὑπέρ (hupér, “over”).

I would maintain that most developed countries are pretty close to optimal in terms of road connectivity, that there are few missing links whose costs outweigh their benefits. If subsidies for modes were to be eliminated, some large cities might be under-developed in terms of transit connectivity because of a bias towards coverage (and circuity) aims rather than frequency.

Let’s think of this in the context of induced demand. More connectivity in one sense means a faster network, which users exploit by traveling longer distances in the same amount of time. They gain utility by being in a house they prefer. However they use up the capacity gains of the network. But more connectivity increases the friction of connections (junctions, interchanges, transfers) which slows down the network. Induced demand due to connectivity is thus self-limiting.

Braess Paradox is the most famous supply side example of hyper-connectivity. In this situation, removing a link improves travel for road users at large because the additional network link induces travelers to use a link with a lower average cost but higher social marginal cost.

A key point is that whether a network is over or under-connected depends on the technology of travel, as well as the amount. A network which is overconnected for cars may be underconnected for pedestrians who don’t congest so easily. A network which is overconnected for 2000 cars may be underconnected for 1000. This is the challenge in building cities. Networks last for seemingly forever, but technologies that use them change more frequently. How can you design a permanent infrastructure flexible enough to serve future technology?

Network Structure and the Journey to Work: An Intra-Metropolitan Analysis

2018-10-102018-10-06 | David Levinson

Recently published:

Parthasarathi, Pavithra, and David Levinson (2018) Network structure and the journey to work: An intra-metropolitan analysis. Transportation Research part A. Volume 118, December 2018, Pages 292-304 [doi] [free until Nov. 9, 2018]

Variation of estimated network measures by Minor Civil Division.

This research quantifies the variation of network structure within the Minneapolis – St. Paul metropolitan area and relates it to average travel time to work for each Minor Civil Division (MCD) in the metro area. The variation of these measures within the metropolitan area is analyzed spatially. The measures of network structure are then related to observed travel. Better connected networks have lower average travel times, all else equal. The results corroborate a relation between network structure and travel and point to the importance of understanding the underlying street network structure.

Elements of Access: Hierarchy

2016-11-282019-03-15 | Wes Marshall

In binary networks, the focus is on whether or not a connection between two nodes exists. However, not all links (or nodes) are created equal, particularly when it comes to transportation networks. When we know about the presence of a link as well as the strength of that link, it is called a valued network. For instance when traveling from A to B in a street network, there is usually discontinuity in street type. In other words, one might move from a local street to a collector road to an arterial road and then back to a collector before reaching their destination. While engineers know this sort of differentiation as functional classification, it is also referred to as hierarchy.

HIERARCHICAL STREET NETWORK FOR METROPOLIS

Hierarchy, which is embedded in many natural and societal systems such as biologic cells and the Internet, is a common transportation complexity that requires a more complicated topological analysis (Tomko, Winter, & Claramunt, 2008). Typical topological measures such as Degree or Betweenness can be useful in helping understand network hierarchy, particularly in tree-like networks; however, such measures would fail to properly distinguish between streets in a gridded street network. In the above version of Metropolis’ street network, the major streets are represented by thicker lines and easily discerned, even in a gridded network (Fleischer, 1941). Using the basic set of topological metrics, we would have no idea that 8^th Street is functionally different from 7^th Street or F Street from D Street. These metrics fail to consider attributes – such as urban design, number of lanes, active transportation infrastructure, adjacent land uses, and speed – beyond network structure and would not necessarily be able to distinguish such streets.

Elements of Access: Transport Planning for Engineers, Transport Engineering for Planners. By David M. Levinson, Wes Marshall, Kay Axhausen.

Working with hierarchical networks often involves dividing networks in multiple layers or tiers. Measurements of heterogeneity have also become common proxies for characterizing hierarchy. To identify heterogeneity among street segments, researchers have used entropy measures as well as discontinuity measures (Xie, 2005). Discontinuity, for example, does not necessarily denote a disconnected network; rather, the reference is to the discontinuity in moving from one street type to another. If we sum the number of times a traveler goes from one type of street to another while traveling along a shortest path route, we find the trip discontinuity. Dividing that number by the length of the trip gives us the relative discontinuity (Parthasarathi, 2011). Other simplistic hierarchy measures calculate the relative percentage of a particular type of road. For instance, we might divide the number or length of arterials by the total number or length of roads to find the relative percent arterials (Parthasarathi, 2011).

Interestingly, it is not uncommon for large-scale transportation models to delete streets on the lower end of the hierarchical spectrum (i.e. local streets) for the sake of computational efficiency. Yet, removing such streets creates a bias against more connected networks because less connected networks typically need to be supported by major streets with more capacity than would be needed in more connected networks (Bern & Marshall, 2012). Some topological researchers – where the focus should be on understanding the full network – unfortunately reach the same conclusion: “urban streets demonstrate a hierarchical structure in the sense that a majority is trivial, while a minority is vital” (Jiang, 2009). If we only care about vehicle traffic flow, such statements may be true. However, my previous street network research confirms that understanding the full network holds the key to pushing toward improved safety, increased active transportation, and better environmental and health outcomes (Bern & Marshall, 2013; Marshall & Garrick, 2009, 2010a, 2010b, 2012).

Elements of Access: Meshedness

2016-11-142018-01-08 | Wes Marshall

Urban planners and engineers have long been interested in measuring street connectivity and typically do so with relatively simple measures such as the link to node ratio (called the Beta Index in the Transport Geography field), which divides the total number of links (i.e. road segments between intersections) by the total number of nodes (i.e. intersections including dead ends). In the above image, the connected network has link to node ratio of 1.6 while the dendritic network’s link to node ratio is 1.0 (a link to node ration of 1.4 is typically considered a well-connected street network).

The connected node ratio divides the number of connected nodes (i.e. nodes that are not dead ends) by total number of nodes (Handy, Paterson, & Butler, 2003). The networks above have a connected node ratio of 1.0 and 0.6, respectively. The underlying intent is distinguish between well-connected or gridded street networks and dendritic, treelike networks – as highlighted in the figure above – in researching relevant issues such as travel behavior, road safety, VMT, and public health outcomes.

Topology takes a slightly different approach to understanding this issue. The Meshedness Coefficient, for instance, measures connectivity by looking at the number of cycles in the network with respect to the maximum number of cycles (a cycle is a closed path that begins and ends at the same node with no fewer than three links). A Meshedness Coefficient of 0 represents full tree structure (i.e. no cycles), and 1 represents complete connectivity (i.e. every node is directly connected to every other node, which is not feasible in a large surface transportation network) (Buhl et al., 2006). In non-planar networks, this measure is also known in Transport Geography as the Alpha Index. The Alpha for the connected network above is 0.4 and for the dendritic network, it is just 0.03. For large networks, Beta and Alpha are highly correlated.

Xie and Levinson (2007) developed another useful metric called Treeness. Instead of counting the number of cycles, Treeness is instead calculated by dividing the length of street segments not within a cycle by the total length of street segments. The Treeness measure also provides a value between 0 and 1, but in this case, the higher number represents a more treelike or dendritic network (Xie & Levinson, 2007).

DOWNED TREE TRAPS MORE THAN 50 HOUSEHOLDS Image from The Oregonian (Florip, 2010) — DOWNED TREE TRAPS MORE THAN 50 HOUSEHOLDS
Image from The Oregonian (Florip, 2010)

Networks with good overall connectivity are called integrated networks. Networks with low connectivity are called fractured networks (although fractured networks can still be comprised of connected components). Again, these measures relate to issues of resilience. When a single node failure can significantly erode network functionality, the system is fragile. The image below shows a fallen tree in Lake Oswego, OR that cut off more than 50 families from the outside world (or more specifically, the cars of more than 50 households were trapped) (Florip, 2010). If only that network had a little less Treeness.

Elements of Access: Clustering

2016-10-312018-01-08 | Wes Marshall

When we have nodes or links with high Betweenness values, it is often because our network is split into various sub-groups that can be called clusters. Clusters tend to have their own unique set of properties, so it is useful to be able to identify clusters quantitatively.

While there are a growing number of clustering algorithms, the basic idea behind them is to capture the degree to which nodes cluster. The Clustering coefficient, for instance, represents how likely is it that two connected nodes are part of a larger group of highly connected nodes. It can be calculated by dividing number of actual connections between the neighbors of a node (i.e. the nodes directly connected to the node in question) by the number of possible connections between these same neighboring nodes. For instance in the image above, the red node is the node of interest, and it has a Degree of 4. Those 4 neighboring nodes make 4 actual connections (i.e. the black lines in the figure on the right) but have 6 possible connections (i.e. the black lines plus the red dashed lines). Thus, the Clustering coefficient for the red node is 4 divided by 6 or 0.67.

The value represented by the Clustering coefficient ranges from 0 (i.e. no clustering) to 1 (i.e. complete clustering). If we are interested in the amount of clustering for an entire network, we average the Clustering coefficients for all of the nodes. Clustering tends to be higher in real-world networks than in random networks. So when a network becomes more centralized (i.e. a small percentage of nodes have high connectivity), the overall topology becomes more differentiated and clusters begin to emerge.

Other related terms include component and clique. When a given sub-group of nodes is also highly connected, that is called a component. When the nodes in a component have few connections to other nodes outside of the component, that is a clique. Understanding clusters, components, and cliques in networks can be useful because they can hold more influence over behavior than overall network structure (Neal, 2013). Imagine, for instance, a New Urbanist neighborhood with great street connectivity set into a city with poor overall street connectivity. Analyzing network structure for the overall city might lead us to one conclusion; yet, we could find very different outcomes in the New Urbanist neighborhood. While factors such as land use, street design, and demographics influence transportation-related outcomes as well, the concept of clustering holds value for those interested in truly understanding transportation networks.

Elements of Access: Betweenness

2016-10-202018-01-08 | Wes Marshall

Degree is often good for measuring local circumstance, but adequately characterizing centrality is a bit more complicated. When trying to figure out centrality in terms of how connected and influential a node or link is, it is useful to get a sense of relative network flow through a particular node or link.

RED NODE INDICATING HIGHEST BETWEENNESS VALUE FOR THIS NETWORK

Betweenness measures attempt to capture this relative flow by quantifying the number of times a node or link is on a shortest path between two other nodes. The first step would be to calculate the shortest path between every origin and every destination. Next, we count the number of times that a particular node or link shows up on a shortest path. The resulting number represents the relative role of a node or link as a connector between clusters of nodes or links. In the above street network, the intersection highlighted in red must be included in over half of the shortest paths. We call this count Betweenness, which is essentially an attempt to quantify how necessary a node or link is to get from one side of the network to the other. The Panama Canal, for instance, is a key maritime link connecting the Atlantic and Pacific Oceans. Without it, ships would have to route around Cape Horn at the southernmost tip of Chile or through the Straits of Magellan. For a ship traveling from New York to San Francisco, the Panama Canal – due to its high Betweenness value – cuts more than 7,500 miles from the journey. In terms of other transportation issues, Betweenness usually relates to metrics such as accessibility and traffic congestion.

In addition to revealing relative importance, Betweenness also indicates how irreplaceable a node or link may be to a network. In other words, what happens if we remove a certain node or link from the network? Very high betweenness values can indicate a critical connection between various groups of nodes or links. In some cases, this represents a vulnerability where we would want to add redundancies to the network.

In transportation networks, if we assume all travelers take the shortest path and treat each traveler as having a unique origin and destination, Betweenness is the same as the flow (number of travelers) on the link. We call this Flow-weighted Betweenness.

Elements of Access: Degree

2016-10-032018-01-08 | Wes Marshall

Centrality measures help gauge the overall importance of a node. In other words, how connected and how influential is a node within the overall network?

DEGREE VALUES FOR METROPOLIS STREET NETWORK

One of the simplest measures of centrality is Degree, which measures the number of connections between a node and all other nodes. For instance if we are considering a street network with intersections as nodes, a nodal Degree of 4 would indicate a typical 4-way intersection.

The image above depicts a rendition of the Metropolis street network with a Degree value shown at each intersection and a 4-way intersection highlighted in red (Fleischer, 1941). When we focus on what is happening at one particular node, it is called the ego network (in that we are looking at the network from the perspective of a single node while ignoring all nodes not directly connected, which can be deemed a bit narcissistic). The entire network can be called the complete, whole, or global network. So if we want an overall Degree measure, we can calculate Average Degree, which is the average number of connections for all the nodes within the overall network. When the Average Degree exceeds 1, every node has at least one connection, on average. When the Average Degree approaches log(n), where n equals the number of nodes in the network, every node starts to become accessible from every other node (Neal, 2013). For the Metropolis network, there are 78 nodes with an Average Degree of 3.4.

Degree Distribution Graph for Metropolis

Analyzing Degree measures for a complete network also entails generating a Degree Distribution, which literally equates to the plotting the frequency of each Degree for all the nodes as shown in the image below for the Metropolis street network. The idea is to try to capture the relative differences in connectivity between the nodes in order to gain a sense of network structure. For instance, every node in a homogenous network would have the exact same number of connections and not much of a distribution. A more centralized network might have one node with a high Degree value and all other nodes with low Degree values.