Simple trust metric
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.
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.