Computing Betweenness Centrality in the Web-of-Trust

The mean-minimum-distance of a key to all other keys in the web-of-trust gives some idea of the connectedness of the key. This is done in Drew Streib and Jason Harris' keyanalyze. But it does not express how the key contributes to the infrastructure of the web-of-trust. It would be nice to have measurement of, e.g., the number of otherwise disjoint communities which are connected only or mainly through a key.

A quantity that expresses something like this is the Betweenness Centrality. In a nutshell, it is the number of shortest paths which lead through a vertex in a graph. The paths are taken from every vertex, to every vertex. If there is more than one shortest path between two vertices, the centrality of the vertices on the paths is increased only by the fraction of paths which they are part of.

Formally, Betweenness Centrality of a vertex v is defined as the sum of [(number of shortest paths from s to t that go through v) divided by (number of shortest paths from s to t)], where s and t run over all pairwise different vertices ≠ v.

The code in Cwot.tar.gz computes the betweenness centrality of all keys of a graph. The graph must be presented in the preprocess.keys format as in keyanalyze.

To compile the code, simply type 'make'. If your system does not have /usr/include/sys/queue.h or /usr/include/sys/tree.h you have to un-comment one line in the Makefile, see there.

The algorithm used to compute the Betweenness Centrality was taken from a paper by Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality” in “Journal of Mathematical Sociology”, 25(5):163-177, 2001. The time-complexity is O(nm), where n is the number of vertices (keys) and m the number of edges (signatures). The space-complexity is O(n + m), but my clumsy implementation might scale worse.

The code is available under the MIT license.

Thu, 09 Dec 2004
[/projects] permanent link