31 Aug 2002 Bram   » (Master)

Anti-Certs

Raph mentioned that I've been thinking about anti-certs. My thoughts are still very speculative, but I'll explain their current state.

Advagato's engine currently has essentially two ways one person can feel about another - positive, if they've certified, or neutral, if they haven't. Anti-certs add another value, active distrust.

My general approach to using anti-certs is to have two steps. The first one uses all the anti-certs to compute weights for each node which have had the anti-certs taken into effect, and the second uses the plain old eigenvector method to calculate your belief level using the calculated node weightings.

This approach has some practical drawbacks. It can't be calculated in a distributed manner unless you send all data everywhere, which is fortunately probably quite practical for many applications. It also requires greater runtime than the vanilla eignevector method, but all the variants I give here are still polynomial.

The simplest way to use anti-certs is to simply set the weight of everyone I've anti-certed to zero.

Behaviorally this technique works okay, but it suffers from completely ignoring the anti-certs of people you've certed. Adding that behavior in is a tricky issue. Since the strength of an anti-cert is dependent on the strength of the node giving it, the effects are probably inherently non-linear.

As a result, there are some situations which don't have a unique weightings solution. For example, if you cert A and B, and A and B each anti-cert the other one, you've basically got two solutions - one in which A is weighted heavily and B very little, and one in which B is weighted heavily and A very little.

Likewise there are situations which have no stable solution. For example, if you cert A, B, and C, and A certs B, B certs C, and C certs A, but B anti-certs A, C anti-certs B, and A anti-certs C, then no single optimal solution exists.

It is possible that there might be closed form formulas which get the above situations to be 'balanced', in which all nodes wind up being weighted about the same, but I doubt that that's possible or desirable.

So, how to calculate a solution? My best idea is to do it in multiple passes. In each one the weight of each node is calculated without using any second order effects, and in the next pass the weights from the previous pass are used. This both always yields a reasonable solution and does it within a polynomial amount of time. I suspect that in practice four passes works great for almost all applications.

How to calculate weight? A reasonable sounding technique is to calculate your confidence in each other node's certification, then your confidence in its anti-certification, and set the weight to confidence / (confidence + anti-confidence).

All of the above looks reasonable at first blush, but definitely requires experimentation to see how it might behave in practice.

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!