Network centrality

Accessibility indicators ask how well a location reaches destinations. Centrality measures ask how important a location is within the network itself, independently of what is located there. The two are related but not interchangeable: a motorway junction in an empty landscape is central but not accessible to much.

Centrality by random walker distributions (Markov modelling)

When an outgoing link of node $i$ to node $j$ has a probability $P_{ij}$ of being chosen by a random walker at node $i$, with $\sum\limits_{j} P_{ij} = 1$ for each $i$, a random walker starting at node $i$ with probability state vector $\pi_0$, where $\pi_{i0}$ is the probability of the walker being in node $i$ at stage 0, will at stage $t$ (after $t$ steps) be in node $j$ with probability $(P^{t} \cdot \pi_0)_j$.

For a fully connected network this converges to a stationary Markov distribution that is independent of the starting state. That stationary distribution can be considered a measure of centrality for a connected set of nodes. It is the same construction that underlies PageRank.

Computation

If a network has $n$ nodes with an average of $k$ outgoing links and distribution $\pi_{it}$, then

$$\pi_{j,t+1} := \sum\limits_{i} P_{ij} \cdot \pi_{it}$$

can be computed with a simple array lookup (index), a multiplication and a partitioned summation, in $O(nk)$ time per iteration.

attribute<float64> link_probability   (link) := 1.0 / float64(pcount(link_F1)); // P_ij
attribute<float64> node_probability_0 (node) := 1.0 / pcount(node);
attribute<float64> node_probability_1 (node) := sum(node_probability_0[link_F1] * link_probability, link_F2);

Applying the last line iteratively gives $\pi_{it}$ for successive $t$, which can be generated with for_each:

unit<uint32> t: nrofrows = 100
{
   attribute<string> name := 't' + string(id(t));
}
container iteration := for_each_nedv(t/name,
     sum(' + MakeDefined(t/name[ID(iter)-1], 'node_probability_0') + '[link_F1] * link_probability, link_F2)'
     , node
     , float64);

Other centrality measures

For reference, the random walk measure sits alongside the classical graph theoretic ones.

• Degree centrality, the number of connecting links. Trivial to compute, but weak as an indicator on road networks where degree is nearly constant.
• Betweenness centrality, the share of shortest paths passing through a node. Directly meaningful for traffic load, but expensive, since it requires all pairs shortest paths.
• Closeness centrality, the inverse of the mean shortest path impedance to all other nodes. This is the measure closest to a location based accessibility indicator with a uniform attraction.

Flow based centrality

A third route to centrality is to assign modelled flows to the network and read off how much passes through each link. The interaction section of the impedance options produces exactly this as Link_flow, the sum of all origin destination flows whose route uses that link, and trace_back gives the same quantity for a given set of routes.

This is betweenness centrality with the pairs weighted by a spatial interaction model instead of counted equally, which for a road network is usually the more meaningful of the two. The theory is in Spatial Interaction Models.

Related

• Accessibility indicators
• Shortest path and the Dijkstra algorithm
• Spatial Interaction Models
• connected_parts and strongly_connected_components, for the connectivity assumptions the Markov measure depends on