Two betweenness centrality measures based on Randomized Shortest Paths

Abstract

This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.

Figure 1

A 5-regular graph with three communities, and the heat plots of its betweenness values with the shortest path likelihood betweenness (a), the simple RSP betweenness (b), and the degree centrality (c).

Figure 2

The mean average rank of the nodes of community B which lies in between two other communities, A and C, based on the nodes’ RSP betweenness (a) and RSP net betweenness values (b) over 200 networks of 360 nodes generated using the LFR algorithm, as described in the body text (with low rank meaning a high betweenness score). The results are plotted for varying values of β and for three values of the mixing parameter μ with error bars indicating the standard error of the mean over the 200 runs. In both plots, the values at the left end of the curves (as β → ∞) show the results with the shortest path likelihood betweenness and at the right end (as β → 0⁺) the results with the degree centrality in (a), and the current flow betweenness in (b).

Figure 3. The interpolation between the shortest path and random walk betweenness measures with the simple RSP and the RSP net betwenness measures on the Midtown and Lower Manhattan street network.

The network has been extracted from http://www.openstreetmap.org (for the data and code, see Materials).

Figure 4. The interpolation between the shortest path likelihood betweenness the stationary distribution with the simple RSP betwenness on the subnetwork of Wikipedia.

The color of a node in the plots indicates its rank w.r.t. the betwenness measure; red and blue indicate high and low rank (i.e. high and low betweenness values), respectively. The dense cluster of nodes in the lower left corner consists mostly of nodes related to social networks. Below the plots, the 10 highest-ranked nodes are listed.