[pathfinder] homepgpnotes

analysis of the strong set in the PGP web of trust

author Henk P. Penning
date Sun Dec 3 13:02:06 CET 2006




The size of the strong set is growing ...

... and dived down in 2004-12 ; a massive cleanup removed a lot of revoked/expired keys.


... and the average distance between the points is shrinking!


A possible reason : the average degree (number of signatures per key) is rising.


population change

The population of the strong set changes over time, as keys enter and leave the set.

In the graph below, for a given date

About half of the keys in the first set (april 2003) have disappeared since then.


distribution of degree

The plot below shows the distribution of degree (the number of signatures per key).

The distribution hardly changes with time. The fraction of keys with only one signature is remarkably stable at some 25%.


The graph below shows last month's distribution of degree (number of signatures per key) using a log/log scale.

The graph is very typical for a social network exhibiting the small world phenomenon, a scale-free network.

distribution of degre

distribution of distance

The graph below shows the distribution of the distances between all PGP keys in the strong set.

Since the strong set grows, the number of paths grows too. If you look closely, you can see that the most common distance decreases. In april 2003 it was just below 6, now it is creeping to 5.5.

distribution of degre

normalized distribution of distance

The plot below shows the same data, but the counts are normalized (divided) by the number of paths in the strong set :
#paths = |G| × (|G| - 1), where |G| is the number of points in the graph

The plot is interesting, because it is so boring! The shape of the distribution curves is very stable; over time, the pattern shifts slowly toward smaller distances.

normalized distribution of degre

key ranking by mean shortest distance

Some people are interested in key ranking ... See the top 50 and top 1000.

msds msds top 100

msds bottom 200

Following the footsie idea of Matthew Wilcox, here is the footsie for the strong set :


leaving out keys

What happens to the size of the largest strongly connect component (scc) if we delete points ? The graph will break up and the size of the biggest component will go down. How this happens, depends on which points we remove. Below we will see what happens when we remove core, fringe or random points.

The plots below show what happens if we remove k core keys : the keys with low msd's.

To see how the size of the scc (red line) goes to zero, the second plot shows the same data on a logscale.

The graph crumbles gracefully until some 10.000 keys are removed. After that, only splinters remain. As expected, the amsd shoots up, to over 15. Note that the top-1000 aren't very special. The crumbling is evenly distributed over the entire range, until there is nothing but graph dust, probably local clusters.

removing core keys removing core keys

The plots below show what happens if we remove k fringe keys : the keys with high msd's. To get a better view of the number of components (green line), the second plot shows the same data on a logscale.

The graph remains very much intact, all the way down. The number of components remains low and very stable.
At first, the amsd decreases more than average because the the largest connected component becomes 'rounder'.

removing fringe keys removing fringe keys

What happens if we remove random keys ?

The scc of the graph remains big, almost all the way down. The amsd (blue line) remains very stable, between 5 and 6.
This plot shows the fractal nature of the strong set. A random subgraph has the same structure as the entire graph.

removing random keys removing random keys




glossary, theory


The plots were done by Henk P. Penninghomepgppathfinder and key statistics

The data was kindly provided by Patrick Feisthammel and Jörgen Cederlöf.

Valid HTML 4.01 Transitional