## Using localised network complexity as a graph centrality measure

I’ve been running some experiments with graph centrality indices in an attempt to find an effective method to describe Jane Jacob’s thinking behind her argument for ’the need for small blocks’.

Centrality indices are a manner to identify the most important edges (links) or vertices (nodes) in a graph (network), and can tell you things like which people are the most influential in a social network, or which roads are the most likely to experience traffic and liveliness. In the case of street networks, we are ordinarily dealing with ‘planar’ (flat) graphs consisting of intersections and streets. The graph can be represented in its ‘primal’ form, where the intersections are nodes and the streets are links, or, as is the case with Space Syntax, the graph can be represented in its ‘dual’ form where the streets are represented as nodes. There are also different ways to describe what exactly constitutes a ‘street’, such as traditional implementations of Space Syntax that utilise unobstructed lines of sight, i.e. straightness.

For the the sake of intuition and experimentation, I am here using the primal representation where intersections are nodes connected by distance-weighted street links. Since I am trying to zero-in on Jacobs’ discussion and examples, I’ve created a little test scenario which consists of two clusters of manhattan grids, connected by two longer streets in order to sift out what works better at global or local scales. Some of the block clusters also have additional streets at the mid-points of the blocks in order to identify which centrality indices better align with Jacobs’ discussion about smaller street blocks in the context of her Rockefeller Plaza example.

Some better known examples of centrality indices include ‘closeness’ centrality, which effectively tells you how close a particular node is to all other nodes, and ‘betweenness’ centrality, which tells you how many times a particular node appears on the shortest path between all other nodes. At first glance, what Jacobs was describing sounds a little bit like betweenness, because she mentions how that many different paths need to come together to support pools of economic use.

Yet, betweenness doesn’t really tell the whole story. On a global level, betweenness paints an accurate picture of where the most commonly used streets are likely to be, including some isolated and longer streets that are centrally located between all other nodes, but that are in some cases unlikely to be successful with pedestrians.

A different picture emerges with localised betweenness, for which I’ve used a 600m (1/4 mile) walking radius. An algorithm cycles through all nodes in the graph, figures out which other nodes are within a distance of 600m, and then runs a localised betweenness on the resultant localised graphs.

In the above-picture, the right-hand cluster’s results resemble something like a ‘closeness’ centrality, whereas on the left it shows a similar but slightly higher average score due to the additional origins and destinations. However, the mid-block streets rank quite low because they aren’t technically on the most direct routes.

Looking for a way to better identify these mid-block streets, I then tried Alpha (Meshedness), Beta, and Gamma indices. Between themselves, they yield similar results and roughly describe which parts of the graph are more densely connected than other parts. But, while definitely closer to what I’m trying to measure, they demonstrate some idiosyncrasies such as more centralised nodes scoring lower than less centralised nodes.

Returning to Jacobs’ argument; what she was describing can be thought of as a form of network porosity and route-choice complexity. In other words, a street network that allows for multiple interweaving route-choice combinations that can support maximal access to local streets. This is a natural fit for an information entropy measure, so I experimented with a form of (Shannon’s) information entropy to measure the amount of route-choice information contained in the localised sub-graphs. Without describing the details, the index calculates an information entropy based on the number of ‘bits’ embedded in a graph’s route choices, therefore representing the route complexity of the localised graph. I subsequently found a similar implementation in the form of a degree complexity index formulated by Raychaudhury et. al. (1984)

The results are starting to get closer to the notions of porosity and complexity, but since this formula is applied to the localised sub-graph in a blanket-like fashion, it doesn’t necessarily encompass some of the routing subtleties of the network emanating outwards from each of the respective nodes. This isn’t immediately obvious in the manhattan-grid test case that I’ve been using, but is subtly present in more varied graphs. I therefore tried another approach, which is to calculate the outwards route choice probabilities (using a breadth-first outwards search) to effectively calculate the number of route choices and their consequent probabilities, and then using this information for computing the node’s information entropy index.

Out of these and several other approaches I tried, this one is my favourite because it results in a granular description of localised route complexity, which identifies the Rockefeller Plaza type of example used by Jacobs. More generally, information entropy is used as the basis of several diversity measures which are used to gauge diversity in systems ranging from from economics to eco-systems. It is perhaps fitting that such indices are useful for describing Jacobs’ conception of diversity as a key driver in cities as complex systems.

Raychaudhury, C., Ray, S.K., Ghosh, J.J., Roy, A.B. & Basak, S.C. 1984. Discrimination of isomeric structures using information theoretic topological indices. *Journal of Computational Chemistry*, 5(6), pp. 581-8.