Tore Opsahl

In a network, certain nodes occupy advantageous positions, whereas others must rely on these nodes to, for example, exchange knowledge. The extent to which a node is part of the transactions among other nodes can be studied using Freeman’s (1978) betweenness measure. This measure has been applied to a variety of settings, such as the Russian-Ukraine gas dispute.

Formally Freeman (1978) defined the betweenness of a focal node to be:

where and are all the other nodes in the network, is the number of shortest paths between node and node , and is the number of those paths that go through the focal node.

In the sample network on the right, if the ties did not have a weight assigned to them, the grey lines represent the 9 shortest paths in the network that pass through intermediate nodes. The highlighted node is an intermediate on 8 of these paths. This will give this node a betweenness score of 8.

Brandes (2001) proposed a new algorithm for calculating betweenness faster. In addition to reducing the time, this algorithm also relaxed the assumption that ties had to be either present or absent (i.e. a binary network), and allowed betweenness to be calculated on weighted networks. This generalisation takes into account, that in weighted networks, the transaction between two nodes might be quicker along paths with more intermediate nodes that are strongly connected than paths with fewer weakly-connected intermediate nodes. This is due to the fact that the strongly connected intermediate nodes have, for example, more frequent contact than the weakly connected ones. For example, the tie between the top-left node and the focal node in the sample network above has four times the strength of the tie between the bottom-left node and the focal node. This could mean that top-left node has more frequent contact with the focal node than the bottom-left node has. In turn, this could imply that top-left node might give the focal node a piece of information (or a disease) four times quicker than the bottom-left node. If we are studying the nodes that are most likely to be funnelling information or diseases in a network, then the speed at which it travels, and routes that it takes, are clearly affected by the weights.

This post highlights the generalisation of Freeman’s (1978) betweenness measure to weighted networks by Brandes (2001). This generalisation is separate from the flow measure proposed by Freeman et al. (1991), which might be more appropriate in certain settings. The generalisation highlighted in this post follows the generalisation of closeness to weighted networks by Newman (2001) who built on work by Dijkstra (1959). Newman’s (2001) generalisation was introduced in detail in my previous post: a method for calculating the average shortest distance in weighted networks. Nevertheless, I will quickly reiterate Dijkstra’s (1959) and Newman’s (2001) work here:

1. Dijkstra (1959) proposed an algorithm to find the shortest paths in a network where the weights could be considered costs. The least costly path connecting two nodes was the shortest path between them (e.g. a network of roads where each leg of road has a time-cost assign to it).
2. Newman (2001) transformed the positive weights in a collaboration network into costs by inverting them (dividing 1 by the weight).
3. Based on the inverted weights, Newman (2001) applied Dijkstra’s algorithm and found the least-costly paths among all nodes.
4. The total cost of the paths from a node to all others was a measure of farness: the higher the number, the more it cost a node to reach all other nodes. To create a closeness measure, Newman (2001) followed Freeman (1978) and inverted the numbers (1 divided by the farness). Thus, a high farness was transformed into a low closeness, and a low farness was transformed into a high closeness.

The identification of the shortest paths in weighted networks outlined in the first three steps above can also be used when identifying the nodes which funnel transactions among other nodes in weighted networks. If we assume that transactions in a weighted network follow the shortest paths identified by Dijkstra’s algorithm instead of the one with the least number of intermediate nodes, then the number of shortest paths that pass through a node might change.

Want to test it with your data?

First, you need to download, install, and load tnet in R. Then, you need to load your data accordingly to the tnet standard. The standard is described in detail on tnet’s website along with examples on how to transfer data from other software packages, such as UCINET and Pajek. In addition, you can manually enter the weighted edgelist. For example, this sample network can be loaded using the following command:

net <- cbind(
i=c(1,1,2,2,2,2,3,3,4,5,5,6),
j=c(2,3,1,3,4,5,1,2,2,2,6,5),
w=c(4,2,4,1,4,2,2,1,4,2,1,1))

Freeman’s (1978) binary betweenness measure can be calculated by running the betweenness_w and dichotomise-functions:

betweenness_w(dichotomise(net))[[1]]
     vertex betweenness
[1,]      1           0
[2,]      2           8
[3,]      3           0
[4,]      4           0
[5,]      5           4
[6,]      6           0

To see the outcome of the proposed algorithm in this post, you simply need to run the betweenness_w-function alone:

betweenness_w(net)[[1]]
     vertex betweenness
[1,]      1           4
[2,]      2           8
[3,]      3           0
[4,]      4           0
[5,]      5           4
[6,]      6           0

Now, node 1 (A) has gotten betweenness score of 4 as well. This is because the indirect path from node B to node C through A is used instead of the direct connection.

Note: The betweenness_w-function relies upon the sp.between-function in the RBGL package. The sp.between-function currently does not find more than one shortest path connecting two nodes even if an equally short path exists. This limitation affects the betweenness_w-function.

UPDATE: There is now a boost C++ implementation of Brandes’ (2001) algorithm. I have not tested it, but as far as I can tell, it should be more efficient and without this limitation.

UPDATE: The boost C++ implementation of Brandes’ (2001) algorithm will be included in tnet from version 0.0.6. This algorithm finds multiple paths if they have exactly the same distance. For example, if one path is found over the direct tie with a weight of 1 (distance = 1/1 = 1) and a second path is through an intermediary node with two ties with weights of 2 (distance = 1/2 + 1/2 = 1), the two paths have exactly the same distance. However, if there is a third path through two intermediaries with three ties with weights of 3 (distance = 1/3 + 1/3 + 1/3), it does not exactly equal 1 as computers read these values as 0.3333333 and the sum of these values is 0.9999999. Therefore, this path is considered shorter than the other two paths (distance = 1).

References

Brandes, U., 2001. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25, 163-177.

Dijkstra, E. W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.

Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.

Freeman, L. C., Borgatti, S. P., White, D. R., 1991. Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks 13 (2), 141-154.

Newman, M. E. J., 2001. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E 64, 016132.