Alternate trust metric algorithm
Raph Levien
1 Apr 2002
The Attack Resistant Trust Metric Metadata HOWTO contains a simple algorithm for computing a trust metric. This page contains an alternate algorithm, which may be more efficient in some cases. As far as I can tell, it will produce very similar or identical results. Intuitively, the main algorithm flows data backwards along trust edges, while this one (like PageRank) flows it forwards.The algorithm
Let R[i,j] be the confidence that user i has in assertion j.In the "step", we compute a new R'[i,j] based on the old R[i,j], the trust graph, and the assertions local to the users i. Initialze R'[i,j] to all zeros.
For each user i:
Find the predecessors of i (ie, the users who have issued a peer certificate for i).Add the vector R[i] to each R'[p] for each predecessor p of i. Store as new R'[p].
For each user i:
Now, copy R'[i,j] to R[i,j] for all i, j.Multiply the vector R'[i] by the damping factor (0.85) divided i's outdegree (if the outdegree is zero, use zero). Store as new R'[i].
For each assertion j:
If i has a local assertion matching j, set R'[i,j] to 1 if it's an exact match, or 0 if it just matches the template for the assertion (ie if the assertion is inconsistent with j).Again, optionally, divide each R'[i,j] by the sum over j of R'[i,j] (if zero, use zero).
