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'
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
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/tree.h you have to un-comment one line
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.