Network centrality

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 — number of connecting links; trivial to compute, 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: 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.

Related

• Accessibility indicators
• Shortest path and the Dijkstra algorithm
• Spatial Interaction Models