Search Results: "Torsten Marek"

19 September 2008

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 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.