26 Sep 2002 Bram   » (Master)

Trust Metric Criteria

Confidence values in diary ratings are currently surprisingly low. It turns out that this is due to a serious deficiency in the way diary ratings are calculated, which I will now explain.

Consider the case of a single statement. We have a set of nodes, one of which is 'me', and a directed graph of their certifications. Some nodes 'attest to' the statement in question. We will calculate a confidence level of the statement in the range [0, 1] for each node, with special interest in our own confidence. Diary rankings are more complicated, but this simplified model is sufficient for a full exposition of the current problems.

The current advogato way of calculating confidence is as follows. Start with yourself, and repeatedly hop to a new position by randomly selecting one of the nodes the current position certifies. If you get to a node which attests to the statement, halt. If you get to a dead end, give up. Before each hop, have a 5% chance of giving up. Your confidence is the fraction of the time this procedure doesn't give up.

While this technique seems reasonable on its surface, it hase a serious deficiency.

the adding certifications criterion - Adding a certification to any graph must not reduce your confidence.

Advogato fails this criterion in even the simplest case. Consider the case where we only cert one other node, and that node attests to the statement. Our confidence will now be .95. If we add a cert to a node which doesn't attest to the statement and doesn't cert anyone else, our confidence will fall by a factor of 2. This is clearly undesireable behavior.

Here are some more criteria, some of which advogato already passes, but all of which are clearly desireable and none of which (I think) imply each other -

adding nodes - If nodes and certs are added in such a way that you have a path along new nodes which ends in a new node which attests to the statement, your confidence must go up. (This eliminates another technique.)

total strangers - If a node you have no path to certifies someone, that must not change your confidence.

extending chain - If you only have one cert and do not personally attest to the stament, your confidence must be less than the person you certed.

skepticism - If you do not personally attest to the statement your confidence must be less than 1.

terminators - If a node attests to the statement, additional certs from it to other nodes must not raise your confidence level.

redundant backlinks - If all paths from you to node B must go through node A, then B certifying A must not increase your confidence.

unreachability - If you have no path to a node which attests to the statement, your confidence must be zero.

full attestation - All nodes which attest have confidence one.

side show - If all paths through node B which arrive at a node which attests must pass through some node A both before and after B, then B's certifications must have no effect on your confidence.

That's all I can think of for now, there may be others. Ideally, we would like a set of criteria such that for any two graphs we could unambiguously prove which of them should yield a higher confidence.

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!