In a previous entry The following problem came up: Is it possible to find in polynomial times all subsets of nodes in a graph containing less than half the nodes such that the number of certs into that subset is less than a tenth the number of nodes marked 'bad' in that subset? (I'm going to assume the amount is ten for simplicity.)

It turns out that a simulation of a process akin to gravity can work. First, imagine all nodes are height zero, and there is a force pulling downwards. For each tick of the clock, first pull each node down one unit for every time it was marked as a spammer. Next, for each node A and B where A certs B, if B is lower than A then raise B by ten units and lower A by ten units (this can cause a lot of overshooting, but that averages out in the end). Finally, find where the median height node is and move all nodes upwards the same amount to leave the median node at height zero. Repeat this process many times (a polynomial function with a low exponent on the number of nodes will suffice, although the exact exponent isn't immediately obvious). Eventually all nodes which are part of spam groups plummet downwards, while all good nodes stay part of the central pack, reasonably close to height zero.

To use this for spam stoppage, apply this algorithm to all nodes, then remove all nodes which plummet downwards. If A sent mail to B, then if there's a path from B to A along cert edges which only covers nodes not removed then B accepts the mail, otherwise it gets rejected.

Interestingly, this algorithm not only approximates the solution well in a hand-wavy sort of way, but actually solves it rigorously. A very strange result for a simulation algorithm.