Lucas Nussbaum: 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 VellerIt’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.