19 Sep 2003 Bram   » (Master)

Trust Metric Calculations

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.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!