Quite a few people have asked for this, so here it is, source code for the trust metric as I'm currently running it. It's nasty and dirty in various ways, but it seems to be getting the job done so far. Improvements welcome!
I have implemented my new trust metric, and applied it (fairly crudely) to LiveJournal friends lists as an experiment. The result is a tool that tells you who is "closest" to your friends list who isn't actually on it, like "popfriends" but more sophisticated.
Let me know how plausible the results seem to you. Note that the top few people are nearly always people you don't have on your friends list "on purpose" - in my case, largely because I've moved away from Edinburgh and so I'm trying to resist the temptation to add even the loveliest Edinburghers to my friends list.
Here's a simple trust metric. As usual, nodes are people and directed arcs denote that A confers trust onto B.
We each have a litre bucket. When the bucket overflows, water runs equally down each outgoing arc into the buckets at the other end. To assess who I trust, I simply start pouring water into my own bucket; the order in which other buckets become full to overflowing is their trust rank.
Update with notes:
Dead Ends: Where water has nowhere to go, it runs off the edge of the graph. This happens to water that flows into a subset of nodes all of which are full, with no arcs leaving the subset; the simplest example is a full bucket with no outgoing arcs.
Determining which nodes are dead ends is like determining "unreachability" in garbage collection. Reverse all the arcs, add a "special" node with an arc to each non-full bucket, determine which nodes are reachable from this special node with a standard depth-first search. Those nodes which are not reachable are dead ends.
Monte Carlo implementation: A bucket contains at most n droplets. Each droplet starts from your own bucket. A droplet hitting a full bucket chooses an outgoing arc at random to follow. Repeat until you have enough trusted people. You can explicitly detect dead end conditions, or you can give each droplet a maximum number of transitions before it "evaporates". The higher n is, the longer it will take to run and the greater the precision of your trust ranking.
Deterministic implementation: If water is pouring into my bucket at a constant rate, the rate at which each non-full bucket is filling up is defined by a set of linear equations. Find the "dead ends", determine the set of linear equations, solve, and determine which bucket(s) is going to fill next and how much water it will take. Add exactly that much water, add the newly filled buckets to the trust list, and iterate.
Incomplete knowledge: This metric is designed to work in a situation where each node advertises its outgoing arc list on a different Web page - you don't need to know the whole graph to answer the question "which node do I trust next", you only need the outgoing arc list of nodes you already trust. This applies to both implementations.
Update: - just got mail from Bram indicating that this isn't the metric he wanted to propose. More to follow.
The metric is very simple - it measures the probability that a person is reachable from the "trust source" if half the nodes at random are removed. It does this simply by marking every node invalid with probability 0.5, finding out which nodes are reachable, incrementing a counter on them all, then re-sampling 1000 times.
It seems to give plausible results, and on the Advogato graph (4000 active nodes, 40000 arcs) it takes 6 seconds to do 1000 iterations (which gives results to a precision of about 1.6%, where 100% is maximum trust). It's a combination of Perl and C.
Bram - I think your ideas about criteria are the Right Thing and I've been thinking some of the same things myself. However I think I can list three desirable criteria and prove you can't have all three.
One is the "Adding Certification Criterion" you define. The second is the "Isomorphism criterion" which states that trust metrication should be a function on graphs, and that isomorphic graphs should get isomorphic trust ratings. The third is attack resistance as raph defines it.
If the attacker has total control over a subgraph, they can duplicate trusted parties, trust links and all. The "Adding Certification Criterion" says that this must not reduce the trust of the duplicated parties, while the "Isomorphism Criterion" means that the duplicates must get the same trust. Thus the attacker has increased the total trust in their part of the graph. They can do this indefinitely for unlimited trust; thus they have violated attack resistance. I'm pretty sure your most recent proposal falls to this attack.
I'll try and write more on this when I get more time...
I've created this community to discuss the idea and revive interest in it.
Examples of trust metric systems include the "karma" system on Slashdot, the kuro5hin points system, and the Advogato trust metric system. All of these systems have their problems. Part of the goal of this community is to discuss what sort of system would be appropriate for LiveJournal.
Just found this entry that relates to LJ trust metrics: