How do you measure the density of a network?

In a simple, unweighted network, I immediately think of the traditional density metric: ratio of realized edges over possible edges. We can also entertain more nuanced values, like number of nodes in cliques over the total number of nodes. Even median path length is a decent measure of density. When we have edge weights that represent "length" or some such, possibilities expand.

These graph-theoretic networks can exist happily without worrying about spatial embedding. (Unless you want to get into that in a very precise way.) The whole point of graph isomorphism is that we want to think of graphs as isomorphic regardless of how they are drawn.

I now spend some time each week at Civic Projects, a planning consulting firm. We're working on a project that is all about overlapping networks in urban space. How does the network of bike paths commingle with the network of car-centric streets? How do networks of wayfinding systems intertwine with networks of lighting infrastructure?

These networks are much different from ones I was used to in college. They are inherently spatially embedded and human-centric. Isomorphism doesn't matter: these are networks with anecdotal, instantiated importance.

Urban infrastructure networks also range widely in type. If we want to talk about the "network" of parking infrastructure, raw count of parking spots per unit area is a decently descriptive metric. Node-based metrics aren't very good at representing the density of, say, a bicycle path network, because these metrics can collapse travel distances. Instead, we want something that captures the travel times and interconnectedness. In lighting, if we treat each source of light as a node in the network, some measure of bulk distance between elements helps grasp and what needs to be measured for best human use.

I'm coming around to three major types of urban networks. (Nothing novel here, just useful for classification.)

  1. Area-based networks. These take form as static resources. Parking, special zones (e.g. school zones), shade, and so forth.
  2. Path-based networks. These networks have intersections, but their experiential value emphasizes transit along edges rather than action at nodes. Travel paths populate this category.
  3. Node-based networks. These represent points of interaction. Lighting, gas stations, and wayfinding, all fall into this category.

Each of these necessitates a different strategy for density.

  1. Areal Densities. How many of something per unit area? What proportion of a given area is given to a specific form?
  2. Path Network Densities. This is, to my knowledge, a bit of uncharted territory. Metro's Active Transportation Strategic Plan advocates for an average distance between parallel elements in a network. (In the case of roadways, this is comparable to the width of city blocks.) But in which direction should we measure? Do we integrate along the length of the block? Do we measure the largest possible diameter of each "block"? We could, also, resort to average network path length per unit area (e.g. "how many miles of bike path are there per square mile?").
  3. Nodal Densities. These are closer to typical graph-theoretic density measurements, but should tend towards accounting for edge lengths as well. How far apart are the nodes, on average? How far apart are they from their nearest neighbors, given some threshold of "nearest" or some kind of partitioning?

Context-dependent answers are necessary to make effective, well-reasoned, and responsible metrics for these types. And sometimes, a particular street feature doesn't fit neatly into one category. Trash cans, for instance—we want to consider both an areal density, but also think carefully about the causes for litter—maybe line-of-sight to a receptacle—which falls more into a path density representation. We might need to explore metrics of both forms to make an intelligent decision regarding a proposed system.

Why is any of this useful?

Lots of planners want rules-of-thumb when pitching concepts and making cost estimations. Infrastructure network statistics can also help codify best practices for urban design.

Lots more research required in this area.

(colophon: I am now at SIAM CSE 2017 to run a workshop on social systems modeling, through the Broader Engagement program. Brain getting back into math mode.)

Internet Topology: