Actually, there's a way you can, but only if you add another restriction. If you allow a free graph - that is, a valid graph is any graph which has valid labels on the arcs - then you can't have it. But if you have some local condition affecting the arcs leaving a given node - such as that no two arcs leaving the same node may carry the same positive integer - then you can still do it.

Incidentally the Advogato algorithm (for people, not for diaries) fails the Isomorphism Criterion.

What sampling algorithm are you proposing? is it (1) make random compromise choices about all nodes (perhaps lazily), (2) see if there's an uncompromised path? The SD of the trust value computed would be 1/(2 * sqrt(n)) for n samples. Also I guess it's pretty cheap to collect trust levels for all nodes - "find all reachable nodes" is a pretty fast algorithm. However, the problem with using randomised algorithms for trust is that if your trust was very near some trust threshold, you would find yourself flapping either side of the threshhold on different days...