Looking for cliques in the GPG signatures graph

The strongly connected set of the GPG keys graph contains a bit more than 40000 keys now (yes, that’s a lot of geeks!). I wondered what was the biggest clique (complete subgraph) in that graph, and also of course the biggest clique I was in.

It’s easy to grab the whole web of trust there. Finding the maximum clique in a graph is NP-complete, but there are algorithms that work quite well for small instances (and you don’t need to consider all 40000 keys: to be in a clique of n keys, a key must have at least n-1 signatures, so it’s easy to simplify the graph — if you find a clique with 20 keys, you can remove all keys that have less than 19 signatures).

My first googling result pointed to Ashay Dharwadker’s solver implementation (which also proves P=NP ;). Googling further allowed me to find the solver provided with the DIMACS benchmarks. It’s clearly not the state of the art, but it was enough in my case (allowed to find the result almost immediately).

The biggest clique contains 47 keys. However, it looks like someone had fun, and injected a lot of bogus keys in the keyring. See the clique. So I ignored those keys, and re-ran the solver. And guess what’s the size of the biggest “real” clique? Yes. 42. Here are the winners:

CF3401A9 Elmar Hoffmann 
AF260AB1 Florian Zumbiehl 
454C864C Moritz Lapp 
E6AB2957 Tilman Koschnick 
A0ED982D Christian Brueffer 
5A35FD42 Christoph Ulrich Scholler 
514B3E7C Florian Ernst 
AB0CB8C0 Frank Mohr 
797EBFAB Enrico Zini 
A521F8B5 Manuel Zeise 
57E19B02 Thomas Glanzmann 
3096372C Michael Fladerer 
E63CD6D6 Daniel Hess 
A244C858 Torsten Marek 
82FB4EAD Timo Weingärtner
1EEF26F4 Christoph Ulrich Scholler 
AAE6022E Karlheinz Geyer 
EA2D2C41 Mattia Dongili 
FCC5040F Stephan Beyer 
6B79D401 Giunchedi Filippo 
74B11360 Frank Mohr 
94C09C7F Peter Palfrader
2274C4DA Andreas Priesz 
3B443922 Mathias Rachor 
C54BD798 Helmut Grohne 
9DE1EEB1 Marc Brockschmidt 
41CF0322 Christoph Reeg 
218D18D7 Robert Schiele 
0DCB0431 Daniel Hess 
B84EF12A Mathias Rachor 
FD6A8D9D Andreas Madsack 
67007C30 Bernd Paysan 
9978AF86 Christoph Probst 
BD8B050D Roland Rosenfeld 
E3DB4EA7 Christian Barth 
E263FCD4 Kurt Gramlich 
0E6D09CE Mathias Rachor 
2A623F72 Christoph Probst 
E05C21AF Sebastian Inacker 
5D64F870 Martin Zobel-Helas 
248AEB73 Rene Engelhard 
9C67CD96 Torsten Veller

It’s likely that this happened thanks to a very successful key signing party somewhere in germany (looking at the email addresses). [Update: It was the LinuxTag 2005 KSP.] It might be a nice challenge to beat that clique during next Debconf ;)

And the biggest clique I’m in contains 23 keys. Not too bad.

8 thoughts on “Looking for cliques in the GPG signatures graph

  1. How about duplicates?
    I find “Frank Mohr”, “Christoph Probst” and “Christoph Ulrich Scholler” each two times in this list. They may have multiple keys, but i doubt they’re all different people. So this clique is 42 keys big, but contain less people.

  2. Pingback: Raw Matter

Comments are closed.